Tutteova věta

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)

Aktuální verze z 29. 7. 2025, 19:59

Tutteho věta v matematické teorii grafů charakterizuje grafy s perfektním párováním. Je pojmenována po Williamu Thomasovi Tutteovi. Jedná se o zobecnění Hallovy věty.

Znění

Graf \(G= \left( V, E \right)\) má perfektní párování právě tehdy, když pro každou podmnožinu vrcholů \(U \subseteq V\) platí, že počet komponent souvislosti s lichým počtem vrcholů v indukovaném podgrafu \(G'= \left( V \setminus U, E \right) \) je menší nebo roven kardinalitě \(U\).

Důkaz

Implikace "doprava"

Vyberme si nějakou podmnožinu vrcholů \(U\) a odstraňme ji z \(G\) spolu se všemi hranami, které mají alespoň jeden konec v \(U\). Nyní se podívejme na všechny vzniklé komponenty souvislosti s lichým počtem vrcholů. Jelikož před odebráním \(U\) měl \(G\) perfektní párování, musela z každé této komponenty vést alespoň jedna hrana k nějakému vrcholu v \(U\) (zřejmé z definice perfektního párování).
A protože v párování musíme propojit vždy právě dva vrcholy, musí \(U\) obsahovat alespoň tolik vrcholů, kolik existuje lichých komponent (všimněte si, že počítáme jenom s hranami obsaženými v nějakém perfektním párování - jiné nás nezajímají).
Čímž máme první část důkazu za sebou, neboť pro \(K\) – počet lichých komponent podgrafu \(G' \left( V \setminus U, E \right)\) vztah \(K \le |U|\) zřejmě musí platit.

Externí odkazy

Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii

@@ Řádka 7: / Řádka 7: @@
 ; Implikace "doprava"
 Vyberme si nějakou podmnožinu vrcholů <big>\(U\)</big> a odstraňme ji z <big>\(G\)</big> spolu se všemi hranami, které mají alespoň jeden konec v <big>\(U\)</big>.
-Nyní se podívejme na všechny vzniklé komponenty souvislosti s lichým počtem vrcholů. Jelikož před odebráním <big>\(U\)</big> měl <big>\(G\)</big> perfektní párování, musela z&nbsp;každé této komponenty vést alespoň jedna hrana k nějakému vrcholu v <big>\(U\)</big> (zřejmé z definice perfektního párování).<br />A protože v párování musíme propojit vždy právě dva vrcholy, musí <big>\(U\)</big> obsahovat alespoň tolik vrcholů, kolik existuje lichých komponent (všimněte si, že počítáme jenom s hranami obsaženými v nějakém perfektním párování - jiné nás nezajímají).<br />
+Nyní se podívejme na všechny vzniklé komponenty souvislosti s lichým počtem vrcholů. Jelikož před odebráním <big>\(U\)</big> měl <big>\(G\)</big> perfektní párování, musela z&nbsp;každé této komponenty vést alespoň jedna hrana k nějakému vrcholu v <big>\(U\)</big> (zřejmé z definice perfektního párování).<br />A protože v párování musíme propojit vždy právě dva vrcholy, musí <big>\(U\)</big> obsahovat alespoň tolik vrcholů, kolik existuje lichých komponent (všimněte si, že počítáme jenom s hranami obsaženými v nějakém perfektním párování - jiné nás nezajímají).<br />Čímž máme první část důkazu za sebou, neboť pro <big>\(K\)</big> – počet lichých komponent podgrafu <big>\(G' \left( V \setminus U, E \right)\)</big> vztah <big>\(K \le |U|\)</big> zřejmě musí platit.
-Čímž máme první část důkazu za sebou, neboť pro <big>\(K\)</big> - počet lichých komponent podgrafu <big>\(G' \left( V \setminus U, E \right)\)</big> vztah <big>\(K \le |U|\)</big> zřejmě musí platit.
 == Externí odkazy ==