Matchings, Satz von Tutte

1. Matchings:

Eine Menge M von Kanten eines Graphen G heißt Matching in wenn M keine Schlingen enthält und je zwei verschiedene Kanten aus M keinen gemeinsamen Endpunkt besitzen.

a) Gesättigtes Matching:

Ein Matching M^* von G heißt gesättigt, wenn es in G kein Matching M mit gibt.

b) Maximales Matching:

Ein Matching M^** von G nennt man maximal, wenn es in G kein Matching M mit |M|> |M^**| gibt.

c) Perfektes Matching:

Ist M ein Matching in G mit der Eigenschaft, daß jeder Knoten von G mit einer Kante aus M inzidiert, dann wird M perfektes Matching genannt.

Beispiel

Im Graphen der folgenden Abbildung ist M₁={{2,3},{5,6}} ein gesättigtes Matching und M₂={{1,2},{3,4},{5,6}} ein maximales Matching, das außerdem perfekt ist.

d) Hinweis:

In Graphen mit ungerader Knotenzahl gibt es keine perfekten Matchings.

2. Satz von Tutte:

1. Ein Graph G=(V,E) besitzt genau dann ein perfektes Matching, wenn |V| gerade ist und für jede Teilmenge S der Knotenmenge ist. Dabei ist G-S der Graph, der aus G durch Löschen aller Knoten von S und der mit diesen Knoten inzidierenden Kanten entsteht. Mit q(G-S) wird die Anzahl der Komponenten von G-S mit ungerader Knotenzahl bezeichnet.
2. Perfekte Matchings haben z.B. vollständige Graphen mit gerader Knotenzahl, vollständige paare Graphen K_n,n und beliebige reguläre paare Graphen vom Regularitätsgrad