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

Glej tudi[uredi | uredi kodo]

Opombe in sklici[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]