Direkt zum Inhalt

Lexikon der Mathematik: Ungarischer Algorithmus

Ungarische Methode, liefert in polynomialer Zeit ein Matching maximaler Bewertung in einem bewerteten bipartiten Graphen G.

Dieser Algorithmus geht auf H.W. Kuhn (1955) und J. Munkres (1957) zurück und wird daher auch Kuhn-Munkres-Algorithmus genannt.

Wir beginnen zunächst mit dem verhältnismäßig einfachen Fall, daß wir in einem nicht bewerteten bipartiten Graphen G ein maximales Matching suchen.

  1. Es sei M ein Matching in einem bipartiten Graphen G. Ist 2|M| ≥ |E(G)| − 1, so istM maximal.
  2. Im anderen Fall wähle man eine Ecke u aus G, die mit keiner Kante aus M inzidiert. Von u ausgehend, konstruiere man einen alternierenden Wurzelbaum H bzgl. M in G mit der Wurzel u, den man durch keine Kante aus G vergrößern kann.
  3. 3. Gibt es in H einen Verbesserungsweg W ( alternierender Weg) mit der Anfangsecke u, so gilt für das neue Matching \begin{eqnarray}{M}^{\prime}=(M\backslash K(W))\cup (K(W)\backslash M)\end{eqnarray} in G die Identität |M|′ = |M| + 1. Mit dem größeren Matching M′ gehe man zu 1.
  4. Gibt es in H keinen Verbesserungsweg mit der Anfangsecke u, so kann man die Ecke u aus dem Graphen G entfernen, denn sie spielt bei diesem Verfahren keine Rolle mehr. Mit anderen Worten: Man gehe nun mit G′ = Gu und M zurück zu 1.

Nun kommen wir zu dem schwierigen Fall, daß G eine Bewertung ϱ : K(G) → ℝ besitzt. Offenbar enthält ein Matching maximaler Bewertung keine Kanten negativer Bewertung. Daher können wir uns auf den Fall ϱ(k) ≥ 0 für alle kK(G) zurückziehen. SindX und Y die Partitionsmengen von G, so können wir auch noch |X| = |Y| = n erreichen und uns darauf beschränken, ein perfektes Matching maximaler Bewertung in einem vollständigen bipartiten Graphen Kn,n aufzuspüren. Denn im Fall |X| ≠ |Y| können wir die kleinere der beiden Partitionsmengen durch eine geeignete Anzahl von Ecken ergänzen, und danach alle nicht adjazenten Ecken aus X und Y durch Kanten der Bewertung Null verbinden. Um den Ungarischen Algorithmus für diesen Fall zu beschreiben, benötigen wir noch einige Voraussetzungen. Es sei X = {x1, x2, …, xn}, Y = {y1, y2, …,yn}, und jede Kante xiyj des vollständigen bipartiten Graphen G besitze eine nicht-negative Bewertung ϱ(xiyj). Eine Eckenbewertung l : XY → ℝ nennt man zulässig, wenn \begin{eqnarray}l(x)+l(y)\ge \varrho (xy)\end{eqnarray} für alle xX und alle yY gilt. Durch \begin{eqnarray}l(x)=\mathop{\max}\limits_{y\in Y}\varrho (xy)\end{eqnarray} für xX, und l(y) = 0 für yY ist die Existenz einer zulässige Eckenbewertung von G gesichert.

Ist l eine zulässige Eckenbewertung von G, so bestehe Kl aus den Kanten xyK(G), für die \begin{eqnarray}l(x)+l(y)=\varrho (xy)\end{eqnarray} gilt. Derjenige Faktor von G, der genau die Kantenmenge Kl besitzt, heißt Gleichheitsfaktor und wird mit Gl bezeichnet.

Der folgende Satz bildet die Basis des Ungarischen Algorithmus.

Es sei l eine zulässige Eckenbewertung für den bewerteten vollständigen bipartiten Graphen G.

Besitzt der Gleichheitsfaktor Gl ein perfektes Matching M*, so ist M* ein Matching maximaler Bewertung in G.

Nun kommen wir zur Beschreibung des gewünschten Algorithmus.

Man beginne mit einer beliebigen zulässigen Eckenbewertung l von G und bestimme den Gleichheitsfaktor Gl. Danach wende man die oben für den unbewerteten Fall angegebene Methode auf Gl solange an, bis man zum 4. Schritt gelangt.

Hat man bis dahin ein perfektes Matching in Gl gefunden, so ist man nach obigem Satz am Ziel. Im anderen Fall gelangt man zu einem alternierenden Wurzelbaum H bzgl. eines Matchings M in Gl mit einer Wurzel u, den man durch keine Kante aus Gl vergrößern kann, und in dem kein Verbesserungsweg mit der Anfangsecke u existiert. Ist SE(H) diejenige Eckenmenge von H, die in H geraden Abstand von u (einschließlich u) besitzt und T = E(H) \ S, so gilt notwendig \({N}_{{G}_{l}}(S)=T\), wobei \({N}_{{G}_{l}}(S)\) die Ecken aus Gl sind, die in Gl zu einer Ecke aus S adjazent sind. Dann ist aber \begin{eqnarray}{d}_{l}=\mathop{\min}\limits_{x\in S,\ y\notin T}\{l(x)+l(y)-\varrho (xy)\}\end{eqnarray} eine positive Zahl, und durch l′(v) = l(v) − dl für vS, l′(v) = l(v) + dl für vT, und l′(v) = l(v) für alle anderen Ecken aus G, wird eine neue zulässige Eckenbewertung von G definiert.

Nun überzeugt man sich leicht davon, daß der neue Gleichheitsfaktor \({G}_{l^{\prime}}\) von G sowohl die Kanten von H als auch die Kanten des Matchings M enthält. Aber in \({G}_{l^{\prime}}\) kann man den Baum H durch weitere Kanten vergrößern.

Man kehre daher zum Anfang zurück und führe die Prozedur mit \({G}_{l^{\prime}}\) (an Stelle von Gl) durch. Bei der Wiederholung des Verfahrens ändert man, immer wenn es nötig ist, die Eckenbewertung ab, bis man schließlich ein perfektes Matching in einem Gleichheitsfaktor ermittelt hat.

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

Partnerinhalte