Hledat:

Invia.cz Last minute Tunisko Dovolená v Chorvatsku Pojeďte do Egypta Bulharsko Last minute Kréta
 

Tutteova věta

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 perfektní párování právě tehdy, když pro každou podmnožinu vrcholů platí, že počet komponent souvislosti s lichým počtem vrcholů v indukovaném podgrafu je menší nebo roven kardinalitě .

Důkaz[editovat | editovat zdroj]

Implikace "doprava"[editovat | editovat zdroj]

Vyberme si nějakou podmnožinu vrcholů a odstraňme ji z spolu se všemi hranami, které mají alespoň jeden konec v . Nyní se podívejme na všechny vzniklé komponenty souvislosti s lichým počtem vrcholů. Jelikož před odebráním měl perfektní párování, musela z každé této komponenty vést alespoň jedna hrana k nějakému vrcholu v (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í 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 - počet lichých komponent podgrafu vztah zřejmě musí platit.

Implikace "doleva"[editovat | editovat zdroj]

  • TODO: dukaz
 
Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „https://cs.wikipedia.org/w/index.php?title=Tutteova_věta&oldid=10096754
Stránka byla naposledy upravena 4. 4. 2013 v 17:53. Editovat celý článek Tutteova věta.
Text je dostupný pod licencí Creative Commons Uveďte autora – Zachovejte licenci 3.0 Unported, případně za dalších podmínek. Podrobnosti naleznete na stránce Podmínky užití.
Další služby: Portál | Katalog | Hledej | Zprávy | Počasí | Kurzy | Práce | Slovník | TV | Online hry | Java hry | SMS | Loga a melodie | Chat | Fórum | Kontakt | Set-top-boxy