Kőnig-tétel (gráfelmélet)

Ez a szócikk a gráfelméleti tételről szól. Az azonos nevű halmazelméleti tételről a Kőnig-tétel (halmazelmélet) szócikkben olvashatsz.

Példa egy páros gráfra. A kék szín egy maximális párosítást, a piros minimális lefogó ponthalmazt jelöl, mindkettő hat elemű.

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

Bizonyítás

Segédtétel:

$\nu(G)$ $\leq$ $\tau(G)$ minden $G$ gráfra. Bizonyítása: Ha $M$ egy maximális független élhalmaz, akkor csak ahhoz hogy $M$ éleit lefogjuk, $\nu(G)$ = $|M|$ pontra van szükségünk, vagyis, $\tau(G)$ $\geq$ $|M|$

Először azt mutatjuk meg, hogy $\nu(G)$ = $\tau(G)$. Tekintsuk a következo ábrát:

Legyen $M$ egy olyan párosítás, amely javító utakkal már nem bővíthető. Legyen $Y = A - Z$ azoknak az $X'$-beli pontoknak a halmaza, melyek $Y$-ból elérhetőek alternáló úton. Értelemszerűen, $X$ az $X'$ párjainak halmaza. Legyen $W = X'$ $\cup$ $(Z - X)$. $W$-nek pontosan $|M|$ pontja van, melyek minden élet lefognak, ugyanis $N(X$ $\cup$ $Y) = X'$ ($N(X)$ jelöli az $X$ halmaz szomszédjait egy páros gráfban). Ebből: $\tau(G)$ $\leq$ $|M|$ $\leq$ $\nu(G)$, és a segédtételből adódik az állítás.

Gallai tételei miatt $\nu(G) + \rho(G) = \tau(G) + \alpha(G)$, és mivel $\nu(G) = \tau(G)$, $\alpha(G) = \rho(G)$ -nek is teljesülnie kell.

Kapcsolat a perfekt gráfokkal

Egy gráf perfekt, ha minden feszített részgráfjában a kromatikus szám megegyezik az abban levő maximális klikk méretével. Minden páros gráf perfekt, mivel minden részgráfja páros, esetleg független pontokból áll. Ha a részgráf tartalmaz éleket, akkor mindkét szám kettő; ha nem tartalmaz, akkor egy.

Lovász László egy eredménye szerint gráf akkor és csak akkor perfekt, ha komplementere is perfekt, és a Kőnig-tétel ekvivalens azzal, hogy a páros gráfok komplementere perfekt. A tétel az élgráfokkal is kapcsolatba hozható. Az élgráf kromatikus száma megegyezik az eredeti gráf kromatikus indexével. Kőnig élszínezési tétele szerint a páros gráfok élgráfjai perfektek. A kettőt összetéve kapjuk, hogy a páros gráfok élgráfjainak komplementere is perfekt. Tehát a Kőnig-tétel így is értelmezhető.

Lásd még

• Magyar módszer
• Tutte-tétel
• Hall-tétel
• Frobenius-tétel

Hivatkozások

• Katona, Recski, Szabó "A Számítástudomány alapjai." Typotex. Budapest, 2006. p. 60,61.
• Frank András: Gráfelmélet