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′ = G − u 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 k ∈ K(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 K_n,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 = {x₁, x₂, …, x_n}, Y = {y₁, y₂, …,y_n}, und jede Kante x_iy_j des vollständigen bipartiten Graphen G besitze eine nicht-negative Bewertung ϱ(x_iy_j). Eine Eckenbewertung l : X ∪ Y → ℝ nennt man zulässig, wenn \begin{eqnarray}l(x)+l(y)\ge \varrho (xy)\end{eqnarray} für alle x ∈ X und alle y ∈ Y gilt. Durch \begin{eqnarray}l(x)=\mathop{\max}\limits_{y\in Y}\varrho (xy)\end{eqnarray} für x ∈ X, und l(y) = 0 für y ∈ Y ist die Existenz einer zulässige Eckenbewertung von G gesichert.

Ist l eine zulässige Eckenbewertung von G, so bestehe K_l aus den Kanten xy ∈ K(G), für die \begin{eqnarray}l(x)+l(y)=\varrho (xy)\end{eqnarray} gilt. Derjenige Faktor von G, der genau die Kantenmenge K_l besitzt, heißt Gleichheitsfaktor und wird mit G_l 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 G_l 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 G_l. Danach wende man die oben für den unbewerteten Fall angegebene Methode auf G_l solange an, bis man zum 4. Schritt gelangt.

Hat man bis dahin ein perfektes Matching in G_l gefunden, so ist man nach obigem Satz am Ziel. Im anderen Fall gelangt man zu einem alternierenden Wurzelbaum H bzgl. eines Matchings M in G_l mit einer Wurzel u, den man durch keine Kante aus G_l vergrößern kann, und in dem kein Verbesserungsweg mit der Anfangsecke u existiert. Ist S ⊆ E(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 G_l sind, die in G_l 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) − d_l für v ∈ S, l′(v) = l(v) + d_l für v ∈ T, 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 G_l) 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.