Satz von Tutte

{{#if: behandelt den Satz nach William Thomas Tutte. Zum Hamiltonkreisproblem siehe Satz von Tutte (Hamiltonkreisproblem).

 | Vorlage:Hinweisbaustein 
 | {{#ifeq: 0 | 0 |}}

}}

Der Satz von Tutte (nach William Thomas Tutte)<ref>Tutte, The factorization of locally finite graphs, Canadian Journal of Mathematics, Band 2, 1950, S. 44–49.</ref> 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 |S| ≥ q(G-S) für alle Teilmengen S von V.

Ein einfacherer Beweis als der von Tutte stammt von Tibor Gallai (1963).

Literatur

Lutz Volkmann: Fundamente der Graphentheorie. Springer, (Wien) 1996, ISBN 3-211-82774-9, S. 137, Satz 7.2

Weblinks

{{#if: | {{{author}}} | Eric W. Weisstein }}: 1-Faktorsatz von Tutte. In: MathWorld (englisch). {{#if: TuttesTheorem | {{#ifeq: {{#property:P2812}} | TuttesTheorem | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }} (englisch)
Lutz Volkmann: Graphen an allen Ecken und Kanten. (PDF; 3,5 MB) 2006, S. 114, Satz 7.1 (nicht als Buch erschienen)

Einzelnachweise