Dvodelni graf

Zgled dvodelnega grafa.

Dvodelni graf (tudi bipartitni graf ali bigraf) je v teoriji grafov graf, ki mu lahko vozlišča razdelimo v dve disjunktni množici $U \,$ in $V \,$ tako, da vsaka povezava povezuje vozlišče iz množice $U \,$ z vozliščem v množici $V \,$ (tudi obratno velja: vsaka povezava povezuje tudi vozlišče iz $V \,$ z vozliščem v $U \,$). Tako dobimo dve neodvisni množici. Iz tega sledi, da dvodelni graf ne vsebuje povezave, ki bi povezovala dve vozlišči iste množice. Lahko pa množico vozlišč razdelimo v dve skupini.

Dvodelni graf ima cikle z neparno dolžino. Enostavni dvodelni graf označujemo z $G = (V, E) \,$ kjer je

• $V \,$ število vozlišč
• $E \,$ število povezav

Značilnosti

• graf, ki nima neparnih (lihih) ciklov, je dvodelen. Dvodelni graf tako nima klik, ki bi imele velikost 3 ali več.
• ciklični graf s parnim številom vozlišč je dvodelen
• vsak ravninski graf (povezave se ne sekajo), kjer je vsako lice v ravninskem prikazu sestavljeno iz parnega števila povezav, je dvodelen
• graf je dvodelen, če ga lahko obarvamo z dvema barvama (kromatsko število je manjše ali enako 2)
• najmanjša velikost pokritja vozlišč je enaka velikosti največjega ujemanja
• največja velikost neodvisne množice sešteta z največjim ujemanjem je enaka številu vozlišč
• za povezan dvodelni graf je najmanjša velikost pokritja povezav enaka največji velikosti neodvisnih množic
• za povezani dvodelni graf je velikost velikost najmanjšega pokritja povezav prišteta k velikosti najmanjši pokritosti vozlišč, enaka številu vozlišč
• vsak dvodelni graf je perfektni 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 vozlišč .

Če dve množici $U \,$ in $V \,$ barvamo z dvema barvama tako, da so vsa vozlišča v $U \,$ pobarvana z modro barvo in vsa vozlišča v $V \,$ z zeleno barvo, potem se vsako vozlišče konča in začne z različno barvo. Pogosto dvodelni graf označujemo z

Določanje dvodelnosti z uporabo parnosti.
Modre in rdeče številke pomenijo število povezav do vozlišča, ki je označeno z 0.

Ugotavljanje dvodelnosti

Dvodelni graf je povezan graf. Njegovo dvodelnost lahko definiramo s parnostjo ali neparnostjo razdalje od poljubno izbranega vozlišča. Ena podmnožica vozlišč ima to razdaljo parno, druga podmnožica pa neparno.

Dvodelnost grafa torej ugotavljamo tako, da določimo dve podmnožici $U \,$ in $V \,$ za vsako povezano komponento grafa in potem za vsako vozlišče posebej ugotovimo, če končne točke pripadajo različnim podmnožicam.

Zunanje povezave

• Teorija grafov-dvodelni graf (v slovenščini)
• Dvodelni graf na MathWorld (v angleščini)
• Lekcije iz teorije grafov s simulacijo (v angleščini)
• Dvodelni graf na PlanetMath (v angleščini)
• Razredi grafov (v angleščini)