Matching (Graphentheorie)

Definitionen

Sei G=(V,E) ein ungerichteter Graph ohne Mehrfachkanten und M eine Teilmenge von E. Man bezeichnet E als Paarung oder Matching von G, wenn für je zwei beliebige verschiedene Kanten e₁ und e₂ disjunkt sind, d.h. mit verschiedenen Knoten inzident sind.

Eine Paarung M von G nennt man maximal, wenn man keine weitere Kante e aus E zu M hinzufügen kann, so dass M zusammen mit v eine Paarung ist. Gibt es in G keine Paarung, die mehr Elemente als M enthält, so nennt man M größte Paarung. Die Anzahl Elemente einer größten Paarung nennt man Paarungszahl bzw. Matchingzahl.

In kantengewichteten Graphen definiert man die Größe einer Paarung über die Summe ihrer Kantengewichte. Als größte gewichtete Paarung eines Graphen G bezeichnet man dann eine Paarung, die diesen Wert maximiert.

Beispiele

kommen noch

wichtige Aussagen und Sätze

Das Problem in einem Graphen eine größte Paarung zu finden ist polynomiell, d.h. es gibt einen, aus Sicht der Komplexitätstheorie effizienten, Algorithmus, der dieses Problem in angemessener Zeit löst. Dieser basiert im wesentlichen auf der Erkenntnis, dass eine Paarung in einem Graphen genau dann größtmöglich ist, wenn es keinen augmentierenden Pfad gibt (Satz von Berge, 1957).

In bipartiten Graphen läßt sich mit dem Algorithmus von Hopcroft und Karp in O(√nm) eine größte Paarung finden.

Wichtige Sätze stammen von König, Hall (Heiratsatz) und Tutte ((Defektformel)).