Dvodelni graf

Dvodelni graf (tudi bipartitni graf ali bigraf) je v teoriji grafov graf, ki se mu lahko točke razdeli v dve disjunktni množici $U\,$ in $V\,$ tako, da vsaka povezava povezuje točko iz množice $U\,$ s točko v množici $V\,$ (tudi obratno velja: vsaka povezava povezuje tudi točko iz $V\,$ s točko v $U\,$ ). Tako se dobita dve neodvisni množici. Iz tega sledi, da dvodelni graf ne vsebuje povezave, ki bi povezovala dve točki iste množice. Lahko pa se množico točk razdeli v dve skupini.

Dvodelni graf nima cikle z liho dolžino. Enostavni dvodelni graf se označuje z $G=(V,E)\,$ kjer je:

$V\,$ število točk
$E\,$ število povezav

Značilnosti[uredi | uredi kodo]

graf, ki nima lihih ciklov, je dvodelen. Dvodelni graf tako nima klik, ki bi imele velikost 3 ali več.
ciklični graf s sodim številom točk je dvodelen
vsak ravninski graf (povezave se ne sekajo), kjer je vsako lice v ravninskem prikazu sestavljeno iz sodega števila povezav, je dvodelen
graf je dvodelen, če se ga lahko obarva z dvema barvama (kromatično število je manjše ali enako 2)
najmanjša velikost pokritja točk je enaka velikosti največjega ujemanja
največja velikost neodvisne množice sešteta z največjim ujemanjem je enaka številu točk
za povezani dvodelni graf je najmanjša velikost pokritja povezav enaka največji velikosti neodvisnih množic
za povezani dvodelni graf je velikost najmanjšega pokritja povezav prišteta k velikosti najmanjši pokritosti točk, enaka številu točk
vsak dvodelni graf je popolni graf
spekter grafa je simetričen, če in samo če je graf dvodelen.

Zgledi dvodelnih grafov so tudi drevesa, hiperkocke in cikli s sodim številom točk.^[1]

Če se dve množici $U\,$ in $V\,$ barva z dvema barvama tako, da so vse točke v $U\,$ pobarvane z modro barvo in vse točke v $V\,$ z zeleno barvo, potem se vsaka točka konča in začne z različno barvo. Pogosto se dvodelni graf označuje z

Določanje dvodelnosti z uporabo parnosti.
Modre in rdeče številke pomenijo število povezav do točke, ki je označena z 0.

Ugotavljanje dvodelnosti[uredi | uredi kodo]

Dvodelni graf je povezani graf. Njegovo dvodelnost se lahko definira s sodostjo ali lihostjo razdalje od poljubno izbrane točke. Ena podmnožica točk ima to razdaljo sodo, druga podmnožica pa liho.

Dvodelnost grafa se torej ugotavlja tako, da se določi dve podmnožici $U\,$ in $V\,$ za vsako povezano komponento grafa in potem se za vsako točko posebej ugotovi, če končne točke pripadajo različnim podmnožicam.