- Satz von Tutte
-
Der Satz von Tutte (nach William Thomas Tutte) ist ein mathematischer Satz aus der Graphentheorie. Er lautet:
Ein Graph G = (V,E) hat genau dann ein perfektes Matching, wenn für jede Teilmenge S der Knotenmenge V die Anzahl der Zusammenhangskomponenten ungerader Mächtigkeit von G-S höchstens gleich |S|, der Anzahl der Knoten in S, ist.
G-S bezeichnet dabei den Graphen, der entsteht, wenn man die Knoten von S und ihre inzidenten Kanten aus G löscht. Bezeichnet man mit q(G) die Anzahl der Zusammenhangskomponenten mit ungerader Anzahl Knoten in einem Graphen G = (V,E), so lässt sich die zweite Bedingung kurz schreiben als
für alle Teilmengen S von V.
Literatur
- Lutz Volkmann: Fundamente der Graphentheorie, Springer (Wien) 1996, ISBN 3-211-82774-9, S. 137, Satz 7.2
Weblinks
- Eric W. Weisstein: 1-Faktorsatz von Tutte (engl.). In: MathWorld. (englisch)
- Lutz Volkmann: Graphen an allen Ecken und Kanten, 2006, nicht als Buch erschienen, S. 114, Satz 7.1
Wikimedia Foundation.