Párny graf

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 V₁ a V₂, tak, že každá koncová hrana má jeden vrchol vo V₁ a druhý vo V₂. Zvykne sa označovať G=(V₁, V₂,E).

Graf $G$ je bipartitný vtedy a len vtedy ak obsahuje len párne cykly.

Defínicia

Graf $G=(V,E)$ je bipartitný, ak platí $V=V_1\cup V_2,V_1\cap V_2=\mathrm{\varnothing }$ a $\mathrm{\forall }e=\{u,v\},e\in E:u\in V_1\wedge v\in V_2$. Naviac ak platí $E=V_1\times V_2$ (teda v grafe existujú všetky hrany s touto vlastnostou), nazýva sa tento graf úplný bipartitný graf. Značí sa $K_{m,n}$, kde m a n sú velikosti oboch partít.