Tutteova věta - Historie editací

http://www.multimediaexpo.cz/mmecz/index.php?action=history&feed=atom&title=Tutteova_v%C4%9Bta Tutteova věta - Historie editací 2026-05-25T15:23:57Z Historie editací této stránky MediaWiki 1.16.5 http://www.multimediaexpo.cz/mmecz/index.php?title=Tutteova_v%C4%9Bta&diff=3058292&oldid=prev Sysop: ++ 2025-07-29T19:59:27Z

<p>++</p> <table style="background-color: white; color:black;"> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr valign='top'> <td colspan='2' style="background-color: white; color:black;">← Starší verze</td> <td colspan='2' style="background-color: white; color:black;">Verze z 29. 7. 2025, 19:59</td> </tr><tr><td colspan="2" class="diff-lineno">Řádka 7:</td> <td colspan="2" class="diff-lineno">Řádka 7:</td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>; Implikace "doprava"</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>; Implikace "doprava"</div></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>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>.</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>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>.</div></td></tr> <tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>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 /></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div>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> <ins class="diffchange diffchange-inline">– </ins>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.</div></td></tr> <tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div>Čímž máme první část důkazu za sebou, neboť pro <big>\(K\)</big> <del class="diffchange diffchange-inline">- </del>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.</div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div></div></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>== Externí odkazy ==</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>== Externí odkazy ==</div></td></tr> </table>

Sysop http://www.multimediaexpo.cz/mmecz/index.php?title=Tutteova_v%C4%9Bta&diff=3058291&oldid=prev Sysop: + Aktualizace 2025-07-29T19:57:12Z

<p>+ Aktualizace</p> <table style="background-color: white; color:black;"> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr valign='top'> <td colspan='2' style="background-color: white; color:black;">← Starší verze</td> <td colspan='2' style="background-color: white; color:black;">Verze z 29. 7. 2025, 19:57</td> </tr><tr><td colspan="2" class="diff-lineno">Řádka 1:</td> <td colspan="2" class="diff-lineno">Řádka 1:</td></tr> <tr><td class='diff-marker'>-</td><td style="background: #ffa; color:black; font-size: smaller;"><div><del class="diffchange diffchange-inline">{{Wikipedia-cs</del>|<del class="diffchange diffchange-inline">Tutteova </del>věta|<del class="diffchange diffchange-inline">700}}</del></div></td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins class="diffchange diffchange-inline">'''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</ins>|<ins class="diffchange diffchange-inline">Williamu Thomasovi Tutteovi]]. Jedná se o zobecnění [[Hallova </ins>věta|<ins class="diffchange diffchange-inline">Hallovy věty]].</ins></div></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">== Znění ==</ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">[[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>.</ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">== Důkaz ==</ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">; Implikace "doprava"</ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">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>.</ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">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 /></ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">Čí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.</ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">== Externí odkazy ==</ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;"></ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">{{Článek z Wikipedie}}</ins></div></td></tr> <tr><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[Kategorie:Grafové pojmy]]</div></td><td class='diff-marker'> </td><td style="background: #eee; color:black; font-size: smaller;"><div>[[Kategorie:Grafové pojmy]]</div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="background: #cfc; color:black; font-size: smaller;"><div><ins style="color: red; font-weight: bold; text-decoration: none;">[[Kategorie:Matematické věty a důkazy]]</ins></div></td></tr> </table>

Sysop http://www.multimediaexpo.cz/mmecz/index.php?title=Tutteova_v%C4%9Bta&diff=371191&oldid=prev Sysop: 1 revizi 2013-10-16T10:01:11Z

<p>1 revizi</p> <table style="background-color: white; color:black;"> <tr valign='top'> <td colspan='1' style="background-color: white; color:black;">← Starší verze</td> <td colspan='1' style="background-color: white; color:black;">Verze z 16. 10. 2013, 10:01</td> </tr></table>

Sysop http://www.multimediaexpo.cz/mmecz/index.php?title=Tutteova_v%C4%9Bta&diff=371190&oldid=prev Sysop: + Nový článek 2012-10-22T01:15:38Z

<p>+ Nový článek</p> <p><b>Nová stránka</b></p><div>{{Wikipedia-cs|Tutteova věta|700}}<br /> <br /> [[Kategorie:Grafové pojmy]]</div>

Sysop