Foreground plně podporuje – RWD, HTML 5.0, Super Galerii a YouTube 2.0 !
Tutteova věta
Z Multimediaexpo.cz
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. |