Direkt zum Inhalt

Lexikon der Mathematik: Edmonds, Algorithmus von

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}

so ist M maximal.

Im anderen Fall gilt für die Eckenmenge SE(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 Wald H 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 MK(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 yE(H) adjazent ist, so existiert eine Kante l = ywM mit wE(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}

die Identität |M′| = |M| + 1. Mit dem größeren Matching M′ beginne man die Prozedur von neuem.

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 aE(C)). Tauscht man in W die Kanten von M gegen die Kanten von K(G) \M aus, so erhält man erneut ein Matching M1 mit |M1| = |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 M1 \ 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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos