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

A Wikipédiából, a szabad enciklopédiából
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 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[szerkesztés | forrásszöveg szerkesztése]

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:

Ktsk.jpg

Legyen M egy olyan párosítás, amely javító utakkal már nem bővíthető. Legyen Y = A - Z, X' azoknak az B-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[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

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