Tutteova věta

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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í[editovat | editovat zdroj]

Graf G= \left( V, E \right)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[editovat | editovat zdroj]

Implikace "doprava"[editovat | editovat zdroj]

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.

Implikace "doleva"[editovat | editovat zdroj]

  • TODO: dukaz