💞 Bipartites Matching
Augmentierende Pfade (Hopcroft–Karp)
Steuerung
Statistik
Matching-Größe
0
Maximal möglich
6
Status
Bereit
Hintergrund & Theorie

Bipartites Matching verbindet Knoten aus zwei disjunkten Mengen — L (Bewerber) und R (Stellen) — mit Kanten, die nur zwischen diesen Mengen verlaufen. Ein Matching ist eine Menge von Kanten ohne gemeinsame Endpunkte; das Ziel ist ein Matching von maximaler Größe zu finden.

Augmentierende Pfade

Ein augmentierender Pfad beginnt und endet an nicht zugeordneten Knoten und alterniert: nicht zugeordnete Kante, zugeordnete Kante, nicht zugeordnete Kante, … Da er mit einer nicht zugeordneten Kante beginnt und endet, hat er immer genau eine nicht zugeordnete Kante mehr als zugeordnete.

Warum das Umschalten hilft

Das Umschalten des Zustands zugeordnet/nicht zugeordnet für jede Kante auf dem augmentierenden Pfad verwandelt beide Endpunkte in zugeordnete Knoten, während jeder innere Knoten zugeordnet bleibt (nur mit einem anderen Nachbarn). Der Nettoeffekt ist +1 zur Matching-Größe. Ein Matching ist genau dann maximal, wenn kein augmentierender Pfad mehr existiert — dies ist das Lemma von Berge.

Komplexität von Hopcroft–Karp

Die Suche nach einem einzigen augmentierenden Pfad mit einem DFS von jedem nicht zugeordneten Knoten kostet O(E), und es können bis zu V Suchen nötig sein, was insgesamt O(V·E) ergibt. Hopcroft–Karp findet stattdessen pro Phase eine maximale Menge kürzester, knotendisjunkter augmentierender Pfade (ein BFS zur Bestimmung der kürzesten Pfadlänge, dann DFS zur Extraktion disjunkter Pfade), wodurch nur O(√V) Phasen nötig sind — insgesamt O(E√V).

Satz von König

In jedem bipartiten Graphen entspricht die Größe des maximalen Matchings der Größe der minimalen Knotenüberdeckung (der kleinsten Knotenmenge, die jede Kante berührt). Diese Dualität, bekannt als Satz von König, verbindet Matching und Überdeckung direkt und liegt vielen Ergebnissen der kombinatorischen Optimierung zugrunde.

Über bipartites Matching

Autor: MySimulator-Team · Redaktionelle Prüfung: MySimulator-Redaktion

Aktualisiert: 11. Juli 2026

Ein bipartiter Graph teilt seine Knoten in zwei disjunkte Mengen — hier Bewerber links und Stellen rechts —, wobei Kanten nur zwischen den beiden Mengen verlaufen, niemals innerhalb einer Menge. Ein Matching ist eine Teilmenge von Kanten, in der kein Knoten mehr als einmal vorkommt; ein maximales Matching ist die größte für einen gegebenen Graphen erreichbare solche Teilmenge. Der klassische Weg, ein Matching zu vergrößern, besteht darin, wiederholt nach einem augmentierenden Pfad zu suchen: einer Route, die an nicht zugeordneten Knoten beginnt und endet und zwischen nicht zugeordneten und zugeordneten Kanten alterniert. Das Umschalten jeder Kante entlang dieses Pfads erhöht die Matching-Größe um genau eins, und ein Matching ist nachweislich genau dann maximal, wenn kein augmentierender Pfad mehr übrig bleibt. Diese Suche einmal von jedem nicht zugeordneten Knoten aus durchzuführen, benötigt O(V·E) Zeit; der Hopcroft–Karp-Algorithmus verbessert dies auf O(E√V), indem er pro Phase mehrere kürzeste augmentierende Pfade statt nur einen findet. Über die Graphentheorie hinaus modelliert bipartites Matching die Zuweisung von Aufgaben, die Vergabe von Studienplätzen und die Probleme des stabilen Matchings, die Zulassungssystemen für Schulen und Facharztstellen zugrunde liegen.

Häufig gestellte Fragen

Was ist ein augmentierender Pfad beim bipartiten Matching?

Ein augmentierender Pfad ist eine Folge von Kanten, die an nicht zugeordneten Knoten beginnt und endet und zwischen Kanten außerhalb des aktuellen Matchings und Kanten darin alterniert. Findet man einen solchen Pfad und kehrt den Status jeder Kante entlang des Pfads um — zugeordnet wird nicht zugeordnet und umgekehrt —, erhöht sich die Gesamtgröße des Matchings immer um genau eins.

Warum erhöht das Umschalten eines augmentierenden Pfads die Matching-Größe um eins?

Ein augmentierender Pfad hat immer eine nicht zugeordnete Kante mehr als zugeordnete, weil er an nicht zugeordneten Knoten beginnt und endet. Das Umschalten des Status jeder Kante auf dem Pfad verwandelt daher k nicht zugeordnete Kanten in zugeordnete und k−1 zugeordnete Kanten in nicht zugeordnete — ein Nettogewinn von genau einer zugeordneten Kante, während jeder Knoten auf dem Pfad weiterhin von genau einer zugeordneten Kante abgedeckt bleibt.

Wie viel schneller ist der Hopcroft–Karp-Algorithmus im Vergleich zu einem naiven Ansatz?

Der naive Ansatz — wiederholtes Ausführen einer einzigen Tiefensuche nach einem augmentierenden Pfad von jedem nicht zugeordneten Knoten aus — benötigt im schlimmsten Fall O(V·E) Zeit, da bis zu V augmentierende Pfade nötig sein können und jede Suche O(E) kostet. Hopcroft–Karp findet stattdessen pro Phase mit einem einzigen BFS+DFS-Durchlauf eine maximale Menge kürzester, knotendisjunkter augmentierender Pfade und benötigt daher nur O(√V) Phasen — insgesamt O(E√V), was auf großen Graphen eine erhebliche Beschleunigung bedeutet.

Welche realen Probleme werden mit bipartitem Matching gelöst?

Bipartites Matching liegt der Zuweisung von Jobs und Aufgaben zugrunde (Zuordnung von Arbeitskräften zu passenden Rollen), der Universitätszulassung und der Vergabe von Facharztstellen (ein Vorläufer des stabilen Matching-Algorithmus von Gale–Shapley) sowie Netzwerkflussproblemen wie Planung und Ressourcenzuweisung, bei denen die Maximierung der Anzahl zugeordneter Paare direkt die effiziente Nutzung begrenzter Ressourcen maximiert.