Satz von Tutte

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel behandelt den Satz nach William Thomas Tutte. Zum Hamiltonkreisproblem siehe Satz von Tutte (Hamiltonkreisproblem).

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 |S| ≥ q(G-S) für alle Teilmengen S von V.

Literatur[Bearbeiten | Quelltext bearbeiten]

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

Weblinks[Bearbeiten | Quelltext bearbeiten]