Dvodelni graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
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 in tako, da vsaka povezava povezuje vozlišče iz množice z vozliščem v množici (tudi obratno velja: vsaka povezava povezuje tudi vozlišče iz z vozliščem v ). 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 kjer je

  • število vozlišč
  • število povezav

Značilnosti[uredi | uredi kodo]

  • 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šč [1].

Če dve množici in barvamo z dvema barvama tako, da so vsa vozlišča v pobarvana z modro barvo in vsa vozlišča 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[uredi | uredi kodo]

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 in za vsako povezano komponento grafa in potem za vsako vozlišče posebej ugotovimo, če končne točke pripadajo različnim podmnožicam.

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]