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 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).

Príklad párneho grafu

Graf ${\displaystyle G}$ je bipartitný vtedy a len vtedy ak obsahuje len párne cykly.^[1]

Defínicia

Graf ${\displaystyle G=(V,E)}$ je bipartitný, ak platí ${\displaystyle V=V_{1}\cup V_{2},V_{1}\cap V_{2}=\emptyset \;}$ a ${\displaystyle \forall e=\left\{u,v\right\}\;,e\in E:u\in V_{1}\wedge v\in V_{2}}$. Naviac ak platí ${\displaystyle 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 ${\displaystyle K_{m,n}}$, kde m a n sú velikosti oboch partít.