Párny 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).

Graf  je bipartitný vtedy a len vtedy ak obsahuje len párne cykly.DIESTEL R., Graph Theory, Springer-Verlag New York 1997, 2000, ISBN 0-387-98976-5

 Defínicia 
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.

 Referencie 

Kategória:Teória grafov