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

gráfelméleti állítás

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.

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

Legyen egy páros gráf. Ekkor a tétel szerint (azaz a legnagyobb független élhalmaznak ugyanannyi eleme van, mint a legkisebb lefogó ponthalmaznak), és ha G-ben nincs izolált pont, akkor (azaz a legkisebb lefogó élhalmaz azonos méretű a legnagyobb független ponthalmazzal).

Bizonyítás szerkesztés

Segédtétel:

      minden   gráfra. Bizonyítása: Ha   egy maximális független élhalmaz, akkor csak ahhoz hogy   éleit lefogjuk,   =   pontra van szükségünk, vagyis,      

Először azt mutatjuk meg, hogy   =  . Tekintsük a következő ábrát:

 

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

Gallai tételei miatt  , és mivel  ,   -nek is teljesülnie kell.

Kapcsolat a perfekt gráfokkal szerkesztés

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 szerkesztés

Hivatkozások szerkesztés

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