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 se mu lahko točke razdeli v dve disjunktni množici in tako, da vsaka povezava povezuje točko iz množice s točko v množici (tudi obratno velja: vsaka povezava povezuje tudi točko iz s točko v ). 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 ima cikle z liho dolžino. Enostavni dvodelni graf se označuje z kjer je:

  • število točk
  • š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 in barva z dvema barvama tako, da so vse točke v pobarvane z modro barvo in vse točke 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 in 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[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]