Tutte-tétel

A Wikipédiából, a szabad enciklopédiából

A Tutte-tétel arról szól, hogy mikor van egy nem feltétlenül páros gráfban teljes párosítás. Először Tutte bizonyította be 1947-ben, majd Gallai Tibor adott rá elemi bizonyítást.

Teljes párosításra tétel még a Frobenius-tétel.

Tétel[szerkesztés | forrásszöveg szerkesztése]

Egy gráfban akkor és csakis akkor létezik teljes párosítás, ha akárhogy hagyunk el a gráfból néhány pontot, a maradékban a páratlan komponensek száma ennél nem több.

A tétel bizonyítása[szerkesztés | forrásszöveg szerkesztése]

Legyen G=(V,E) (irányítatlan) gráf. Ha van a gráfban teljes párosítás, akkor egyszerű a helyzet. Elég ugyanis az élek elhagyása után megszámolni a páratlan pontszámú komponenseket. Az egyenlőtlenségnek teljesülnie kell, mert a leszűkített párosításban minden komponensben kimarad egy pont, tehát ezek az elhagyott pontokkal vannak párban a teljes párosítás szerint.

A másik irány nehezebb. Ehhez szükséges néhány jelölés és definíció.

Legyen H részgráfja G-nek. Ekkor cp(H) jelölje a H-beli páratlan elemszámú komponensek számát.

Definíció: X gát, ha cp(G-X)=|X|. Van gát, mert az üres halmaz gát.

Most feltesszük, hogy |V|=n páros. Ekkor, ha X nem gát, akkor cp(G-X)=|X|-2 n páros volta miatt. Legyen a legnagyobb gát X0.

Lemma: G\X0-ban nincsenek páros pontszámú komponensek.

Ha ugyanis lenne, akkor az egyikből kivéve egy pontot, és X0-hoz hozzávéve nagyobb gátat lehetne létrehozni, mivel cp(G\X0\p)=|X0|+1.

Lemma: Ha K páratlan elemszámú komponens G\X0-ban, és a p pont K-beli, akkor K\p -nek van teljes párosítása.

Ha ugyanis nem teljesülne, akkor lenne egy X halmaz K\p-ben,
hogy cp(K\p\X)>|X|
Ekkor X0-t kibővítve p-vel és x-szel nagyobb gátat lehetne létrehozni, ami 2-vel nagyobb.

Most már rá lehet térni a tétel másik irányának bizonyítására.

Tekintsük G\X0-t. Ebben nincsenek páros méretű komponensek, és annyi páratlan méretű komponens van, ahány elem X0-ban. Készítünk egy segédgráfot, ahol nem vesszük figyelembe a gát pontjai között futó éleket. Ebben akkor és csak akkor van teljes párosítás, ha teljesül a Hall-feltétel. Márpedig ez teljesül, különben a tétel feltétele megsérül.

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

  • Katona-Recski-Szabó Csaba: Véges matematika
  • Lovász László: Combinatorical Problems and Exercises
  • Hajnal Péter: Gráfelmélet