Tutte-tétel

• IPA:

Tutte-tétel

1. (matematika, gráfelmélet) 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 **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.

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

$${\displaystyle o(G-S)\leq |S|,}$$

ahol:

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

---

A tétel azt mondja ki, hogy ha egy gráfból ${\displaystyle 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.

---

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

1. Vegyünk egy ${\displaystyle S\subseteq V}$ csúcshalmazt, és jelöljük az eltávolított csúcsok után maradó gráfot ${\displaystyle G-S}$-vel.
2. Mivel ${\displaystyle G}$-ben létezik tökéletes párosítás, minden páratlan komponensnek legalább egy csúcsa párba van rendelve ${\displaystyle S}$ valamelyik csúcsával.
3. Egy páratlan komponens minden esetben igényel legalább egy csúcsot ${\displaystyle 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 (${\displaystyle o(G-S)}$) nem lehet nagyobb, mint az ${\displaystyle S}$-beli csúcsok száma (${\displaystyle |S|}$).

---

Most mutassuk meg, hogy ha minden ${\displaystyle S\subseteq V}$-re ${\displaystyle o(G-S)\leq |S|}$, akkor ${\displaystyle 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 ${\displaystyle S\subseteq V}$ létezne, amelyre ${\displaystyle o(G-S)>|S|}$.
3. Ez ellentmond a feltételnek, miszerint ${\displaystyle o(G-S)\leq |S|}$ minden ${\displaystyle S}$-re.
4. Ezért ${\displaystyle G}$-ben kell léteznie tökéletes párosításnak.

---

1. Speciális esetek:

• Ha ${\displaystyle G}$ teljes gráf (pl. ${\displaystyle K_{2n}}$), akkor mindig létezik tökéletes párosítás.
• Ha ${\displaystyle 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.

---

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

• Tutte-tétel - Értelmező szótár (MEK)
• Tutte-tétel - Etimológiai szótár (UMIL)
• Tutte-tétel - Szótár.net (hu-hu)
• Tutte-tétel - DeepL (hu-de)
• Tutte-tétel - Яндекс (hu-ru)
• Tutte-tétel - Google (hu-en)
• Tutte-tétel - Helyesírási szótár (MTA)
• Tutte-tétel - Wikidata
• Tutte-tétel - Wikipédia (magyar)