https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Satz_von_Tutte 2026-06-25T14:20:33Z Versionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale Kopie MediaWiki 1.43.8 https://wiki-de.moshellshocker.dns64.de/index.php?title=Satz_von_Tutte&diff=1305792&oldid=prev 2022-05-20T07:41:03Z

<p></p> <p><b>Neue Seite</b></p><div>{{Dieser Artikel|behandelt den Satz nach William Thomas Tutte. Zum Hamiltonkreisproblem siehe [[Satz von Tutte (Hamiltonkreisproblem)]].}}<br /> <br /> Der &#039;&#039;&#039;Satz von Tutte&#039;&#039;&#039; (nach [[William Thomas Tutte]])&lt;ref&gt;Tutte, &#039;&#039;The factorization of locally finite graphs&#039;&#039;, Canadian Journal of Mathematics, Band 2, 1950, S. 44–49.&lt;/ref&gt; ist ein [[Satz (Mathematik)|mathematischer Satz]] aus der [[Graphentheorie]]. Er lautet:<br /> <br /> Ein [[Graph (Graphentheorie)|Graph]] &#039;&#039;G&#039;&#039;=(&#039;&#039;V&#039;&#039;,&#039;&#039;E&#039;&#039;) hat genau dann ein [[Paarung (Graphentheorie)|perfektes Matching]], wenn für jede Teilmenge &#039;&#039;S&#039;&#039; der Knotenmenge &#039;&#039;V&#039;&#039; die Anzahl der Zusammenhangskomponenten ungerader Mächtigkeit von &#039;&#039;G&#039;&#039;-&#039;&#039;S&#039;&#039; höchstens gleich |&#039;&#039;S&#039;&#039;|, der Anzahl der Knoten in &#039;&#039;S&#039;&#039;, ist.<br /> <br /> &#039;&#039;G&#039;&#039;-&#039;&#039;S&#039;&#039; bezeichnet dabei den Graphen, der entsteht, wenn man die Knoten von &#039;&#039;S&#039;&#039; und ihre [[Nachbarschaft (Graphentheorie)|inzidenten]] Kanten aus &#039;&#039;G&#039;&#039; löscht. Bezeichnet man mit &#039;&#039;q&#039;&#039;(&#039;&#039;G&#039;&#039;) die Anzahl der Zusammenhangskomponenten mit ungerader Anzahl Knoten in einem Graphen &#039;&#039;G&#039;&#039;=(&#039;&#039;V&#039;&#039;,&#039;&#039;E&#039;&#039;), so lässt sich die zweite Bedingung kurz schreiben als |&#039;&#039;S&#039;&#039;| ≥ &#039;&#039;q&#039;&#039;(&#039;&#039;G&#039;&#039;-&#039;&#039;S&#039;&#039;) für alle Teilmengen &#039;&#039;S&#039;&#039; von&amp;nbsp;&#039;&#039;V&#039;&#039;.<br /> <br /> Ein einfacherer Beweis als der von Tutte stammt von [[Tibor Gallai]] (1963).<br /> == Literatur ==<br /> * Lutz Volkmann: &#039;&#039;Fundamente der Graphentheorie&#039;&#039;. Springer, (Wien) 1996, ISBN 3-211-82774-9, S. 137, Satz 7.2<br /> <br /> == Weblinks ==<br /> * {{MathWorld |id=TuttesTheorem |title=1-Faktorsatz von Tutte}} (englisch)<br /> * Lutz Volkmann: [https://www.math2.rwth-aachen.de/files/gt/buch/graphen_an_allen_ecken_und_kanten.pdf &#039;&#039;Graphen an allen Ecken und Kanten&#039;&#039;.] (PDF; 3,5&amp;nbsp;MB) 2006, S. 114, Satz 7.1 (nicht als Buch erschienen)<br /> ==Einzelnachweise==<br /> &lt;references /&gt;<br /> [[Kategorie:Satz (Graphentheorie)|Tutte, Satz von]]</div>

imported>Claude J