Kőnig-tétel

Magyar

(matematika, gráfelmélet) A Kőnig-tétel a gráfelméletben egy páros gráf maximális párosítása és a minimális lefogó ponthalmaza közötti ekvivalenciát mondja ki. A tétel Kőnig Dénestől származik. Legyen $G$ egy páros gráf. Ekkor a tétel szerint $\nu (G)=\tau (G)$ (azaz a legnagyobb független élhalmaznak ugyanannyi eleme van, mint a legkisebb lefogó ponthalmaznak), és ha G-ben nincs izolált pont, akkor $\rho (G)=\alpha (G)$ (azaz a legkisebb lefogó élhalmaz azonos méretű a legnagyobb független ponthalmazzal).