Zurückblättern Weiterblättern Übergeordnetes Thema Sachgebiet Hauptinhaltsverzeichnis Stichwortverzeichnis Hilfeseiten        


Matchings, Satz von Tutte


1. Matchings: Eine Menge von Kanten eines Graphen heißt Matching in wenn keine Schlingen enthält und je zwei verschiedene Kanten aus keinen gemeinsamen Endpunkt besitzen.
a) Gesättigtes Matching: Ein Matching von heißt gesättigt , wenn es in kein Matching mit gibt.
b) Maximales Matching: Ein Matching von nennt man maximal , wenn es in kein Matching mit gibt.
c) Perfektes Matching: Ist ein Matching in mit der Eigenschaft, daß jeder Knoten von mit einer Kante aus inzidiert, dann wird perfektes Matching genannt.

Beispiel

Im Graphen der folgenden Abbildung ist ein gesättigtes Matching und ein maximales Matching, das außerdem perfekt ist.




d) Hinweis: In Graphen mit ungerader Knotenzahl gibt es keine perfekten Matchings.

2. Satz von Tutte:
a) Ein Graph besitzt genau dann ein perfektes Matching, wenn gerade ist und für jede Teilmenge der Knotenmenge ist. Dabei ist der Graph, der aus durch Löschen aller Knoten von und der mit diesen Knoten inzidierenden Kanten entsteht. Mit wird die Anzahl der Komponenten von mit ungerader Knotenzahl bezeichnet.
b) Perfekte Matchings haben z.B. vollständige Graphen mit gerader Knotenzahl, vollständige paare Graphen und beliebige reguläre paare Graphen vom Regularitätsgrad