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}=\emptyset \;$ a $\forall e=\left\{u,v\right\}\;,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.