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ő hatelemű.

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 ${\displaystyle G}$ egy páros gráf. Ekkor a tétel szerint ${\displaystyle \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 ${\displaystyle \rho (G)=\alpha (G)}$ (azaz a legkisebb lefogó élhalmaz azonos méretű a legnagyobb független ponthalmazzal).

Bizonyítás

Segédtétel:

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

Először azt mutatjuk meg, hogy ${\displaystyle \nu (G)}$ = ${\displaystyle \tau (G)}$. Tekintsük a következő ábrát:

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

Gallai tételei miatt ${\displaystyle \nu (G)+\rho (G)=\tau (G)+\alpha (G)}$, és mivel ${\displaystyle \nu (G)=\tau (G)}$, ${\displaystyle \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