Dvodelni graf
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 nima cikle z liho dolžino. Enostavni dvodelni graf se označuje z 
kjer je:
  število točk
  š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  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

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

 polni dvodelni graf

Sklici

Zunanje povezave 

 Teorija grafov-dvodelni graf 
 
 Lekcije iz teorije grafov s simulacijo  
 Dvodelni graf  na PlanetMath 
 Razredi grafov  

Družine grafov
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 nima cikle z liho dolžino . Enostavni dvodelni graf se označuje z kjer je : število točk število povezav Značilnosti graf , ki nima lihih ciklov , je dvodelen . Dvodelni graf tako nima klik , ki bi imele velikostali 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 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 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 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 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 polni dvodelni graf Sklici Zunanje povezave Teorija grafov - dvodelni graf Lekcije iz teorije grafov s simulacijo Dvodelni graf na PlanetMath Razredi grafov Družine grafov