Dvodelni graf

Zgled dvodelnega grafa.

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

• 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.

Č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

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.

Glej tudi

• polni dvodelni graf

Zunanje povezave

• Teorija grafov-dvodelni graf Predloga:Ikona sl
• Predloga:MathWorld
• Lekcije iz teorije grafov s simulacijo Predloga:Webarchive Predloga:Ikona en
• Dvodelni graf Predloga:Webarchive na PlanetMath Predloga:Ikona en
• Razredi grafov Predloga:Webarchive Predloga:Ikona en