Párny graf

(Presmerované z Biparitný graf)

Párny graf alebo bipartitný graf je graf, ktorého množina vrcholov V môže byť rozdelená do dvoch množín V1 a V2, tak, že každá koncová hrana má jeden vrchol vo V1 a druhý vo V2. Zvykne sa označovať G=(V1, V2,E).

Príklad párneho grafu

Graf je bipartitný vtedy a len vtedy ak obsahuje len párne cykly.[1]

DefíniciaUpraviť

Graf   je bipartitný, ak platí   a  . Naviac ak platí   (teda v grafe existujú všetky hrany s touto vlastnostou), nazýva sa tento graf úplný bipartitný graf. Značí sa  , kde m a n sú velikosti oboch partít.

ReferencieUpraviť

  1. DIESTEL R., Graph Theory, Springer-Verlag New York 1997, 2000, ISBN 0-387-98976-5