Párny graf

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
Príklad párneho grafu

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

Defínicia[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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