Foreground plně podporuje – RWD, HTML 5.0, Super Galerii a YouTube 2.0 !
Tutteova věta
Z Multimediaexpo.cz
m (1 revizi) |
(+ Aktualizace) |
||
| Řádka 1: | Řádka 1: | ||
| - | + | '''Tutteho věta''' v [[Matematika|matematické]] [[teorie grafů|teorii grafů]] charakterizuje grafy s perfektním párováním. Je pojmenována po [[William Thomas Tutte|Williamu Thomasovi Tutteovi]]. Jedná se o zobecnění [[Hallova věta|Hallovy věty]]. | |
| + | == Znění == | ||
| + | [[Graf (teorie grafů)|Graf]] <big>\(G= \left( V, E \right)\)</big> má [[Párování grafu|perfektní párování]] právě tehdy, když pro každou [[Podmnožina|podmnožinu]] vrcholů <big>\(U \subseteq V\)</big> platí, že počet komponent souvislosti s lichým počtem vrcholů v [[Podgraf|indukovaném podgrafu]] <big>\(G'= \left( V \setminus U, E \right) \)</big> je menší nebo roven [[Mohutnost|kardinalitě]] <big>\(U\)</big>. | ||
| + | |||
| + | == Důkaz == | ||
| + | ; 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 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. | ||
| + | |||
| + | == Externí odkazy == | ||
| + | |||
| + | {{Článek z Wikipedie}} | ||
[[Kategorie:Grafové pojmy]] | [[Kategorie:Grafové pojmy]] | ||
| + | [[Kategorie:Matematické věty a důkazy]] | ||
Verze z 29. 7. 2025, 19:57
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. |