Tutte-tétel

1. Sablon:Label 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.

---

Tutte-tétel

A **Tutte-tétel** a gráfelmélet egyik alapvető tétele, amely egy gráf tökéletes párosításának létezésére ad feltételt. A tétel kimondja, hogy egy adott gráf pontosan akkor tartalmaz tökéletes párosítást, ha bizonyos feltételek teljesülnek a gráf részhalmazaira nézve.

Tétel

Legyen $G=(V,E)$ egy gráf. $G$-ben pontosan akkor létezik tökéletes párosítás, ha minden $S\subseteq V$ esetén:

$$o(G-S)\le |S|,$$

ahol:

• $G-S$: az a gráf, amelyet úgy kapunk, hogy $S$ csúcsait és az azokhoz kapcsolódó éleket eltávolítjuk $G$-ből,
• $o(G-S)$: az $G-S$-ben lévő páratlan komponensek (összefüggő részgráfok) száma.

---

Értelemezés

A tétel azt mondja ki, hogy ha egy gráfból $S$ csúcsot eltávolítunk, akkor a megmaradó részgráf páratlan összefüggő komponenseinek száma nem haladhatja meg az eltávolított csúcsok számát.

---

Bizonyítás

1. Szükséges feltétel

Tegyük fel, hogy $G$-nek van tökéletes párosítása, azaz létezik $M\subseteq E$, ahol minden csúcs pontosan egy élhez van rendelve. Mutassuk meg, hogy ekkor $o(G-S)\le |S|$ minden $S\subseteq V$-re.

1. Vegyünk egy $S\subseteq V$ csúcshalmazt, és jelöljük az eltávolított csúcsok után maradó gráfot $G-S$-vel.
2. Mivel $G$-ben létezik tökéletes párosítás, minden páratlan komponensnek legalább egy csúcsa párba van rendelve $S$ valamelyik csúcsával.
3. Egy páratlan komponens minden esetben igényel legalább egy csúcsot $S$-ből ahhoz, hogy az ott lévő csúcsok párosíthatók legyenek.
4. Ezért a páratlan komponensek száma ($o(G-S)$) nem lehet nagyobb, mint az $S$-beli csúcsok száma ($|S|$).

---

2. Elégséges feltétel

Most mutassuk meg, hogy ha minden $S\subseteq V$-re $o(G-S)\le |S|$, akkor $G$-ben létezik tökéletes párosítás.

1. Indirekt bizonyítás: Tegyük fel, hogy nem létezik tökéletes párosítás. Az Edmonds-féle párosítási polinóm szerint egy olyan minimális kontrakció létezése igazolható, amely sérti a feltételt.
2. Ha nem létezne tökéletes párosítás, akkor egy olyan $S\subseteq V$ létezne, amelyre $o(G-S)>|S|$.
3. Ez ellentmond a feltételnek, miszerint $o(G-S)\le |S|$ minden $S$-re.
4. Ezért $G$-ben kell léteznie tökéletes párosításnak.

---

Következmények

1. Speciális esetek:

• Ha $G$ teljes gráf (pl. $K_{2n}$), akkor mindig létezik tökéletes párosítás.
• Ha $G$ kétpartit gráf, akkor a tétel a Hall-féle házasítási tétel általánosítása.

1. Párosítási algoritmusok:

A tétel alapján kidolgozott algoritmusok segítségével eldönthető, hogy egy gráfban létezik-e tökéletes párosítás.

---

Összefoglalás

A **Tutte-tétel** a gráfok tökéletes párosításának feltételeit fogalmazza meg, és alapvető szerepet játszik a párosításelméletben. Ez a tétel nemcsak elméleti szempontból fontos, hanem gyakorlati algoritmusok kidolgozásában is alkalmazható.

Sablon:-ford- Sablon:Trans-top

• Sablon:En: Sablon:T