liefert in polynomialer Zeit ein maximales Matching in einem Graphen.

Dieser recht aufwendige und schwierige Algorithmus von J.Edmonds aus dem Jahre 1965 läßt sich etwa wie folgt beschreiben.

Es sei M ein Matching eines Graphen G. Ist

\begin{eqnarray}2|M|\,\ge \,|E(G)|-1,\end{eqnarray}

Im anderen Fall gilt für die Eckenmenge S ⊆ E(G), die aus den Ecken besteht, die mit keiner Kante aus dem Matching M inzidieren, die Ungleichung |S| ≥ 2.

Ausgehend von S konstruiert man einen alternierenden WaldH in G bzgl. M mit folgenden Eigenschaften. Jede Zusammenhangskomponente von H enthält genau eine Ecke aus S, jede Ecke aus S gehört zu genau einer Komponente von H, und jede Komponente von H ist ein alternierender Wurzelbaum bzgl. M mit einer Wurzel aus S. Darüber hinaus soll jede Ecke aus E(H) \ S mit einer Kante aus M ∩ K(H) inzidieren. Unter diesen Voraussetzungen haben alle Ecken aus H, die einen ungeraden Abstand von ihrer Wurzel aus S besitzen, den Grad 2 in H, und man nennt sie innere Ecken von H, während die verbleibenden Ecken äußere Ecken von H heißen.

Gibt es in H eine äußere Ecke x, die zu einer Ecke y ∉ E(H) adjazent ist, so existiert eine Kante l = yw ∈ M mit w ∉ E(H). Ist k = xy, so können wir den Wald H durch Hinzufügen der Ecken y, w und der Kanten l, k vergrößern.

Gibt es in H zwei äußere Ecken x und y, die zu zwei verschiedenen Komponenten von H gehören, die aber in G adjazent sind, so sind die beiden Wurzeln dieser Komponenten durch einen Verbesserungsweg W verbunden. Dann gilt aber für das Matching

\begin{eqnarray}{M}^{\prime}=(M\backslash K(W))\cup (K(W)\backslash M)\end{eqnarray}

Existieren in einer Komponente T von H mit der Wurzel a zwei äußere Ecken x und y, die in G durch eine Kante k verbunden sind, so sei C der Kreis ungerader Länge, der sich aus dem eindeutigen Weg von x nach y in T und der Kante k zusammensetzt.

Ist W der kürzeste Weg in T von a nach E(C), so ist W alternierend bzgl. M (wenn a ∉ E(C)). Tauscht man in W die Kanten von M gegen die Kanten von K(G) \M aus, so erhält man erneut ein Matching M₁ mit |M₁| = |M|. Nun darf man nach einem Ergebnis von Edmonds den Kreis C zu einer Ecke zusammenziehen (alle auftretenden Schlingen löschen, alle auftretenden parallelen Kanten zu einer Kante vereinigen), und in dem daraus entstandenen kleineren Graphen G′ nach einem Matching suchen, das mehr Kanten als M₁ \ K(C) enthält.

Im verbleibenden Fall, daß im Graphen G die äußeren Ecken von H nur zu inneren Ecken von H adjazent sind, kann man nachweisen, daß das Matching M maximal ist.

Zusammenfassend wird bei dem Algorithmus von Edmonds immer einer der folgenden Schritte durchgeführt:

• Der alternierende Wald H wird vergrößert.
• Das Matching M wird vergrößert.
• Die Eckenzahl |E(G)| wird verkleinert.
• Der Algorithmus stoppt mit einem maximalen Matching.