Eine mögliche Anwendung für das bipartite Matching-Problem ist die Zuordnung von Studenten und Arbeitsstellen. Das Problem wird mittels eines bipartiten Graphen modelliert.
Die Studenten und Arbeitsstellen werden durch zwei Knotenmengen dargestellt.
Die Kanten repräsentieren mögliche Zuordnungen bzw. Qualifikationen.
Das Ziel ist, möglichst viele passende Zuordnungen zu finden, wobei die Studenten nur eine Stelle annehmen können und die Stellen nur einmal vergeben wird.
Sei ein ungerichteter Graph \( G=(V,E)\) gegeben. Eine Teilmenge \(M \subseteq E\) heißt Matching, falls keine zwei Kanten aus M einen Knoten gemeinsam haben.
Ein Matching M heißt maximal, falls die Kardinalität von M maximal unter allen möglichen Matchings ist.
In vielen Anwendungen müssen häufig Elemente aus verschiedenen Klassen kombiniert werden.
Wenn genau zwei Klassen existieren, so nennt man dieses Problem Bipartites Matching.
Hier wird der Hopcroft-Karp-Algorithmus veranschaulicht, der das Problem der maximalen Matchings auf bipartiten Graphen löst.
Auf welchem Graph soll der Algorithmus ausgeführt werden?
Nimm ein fertiges Beispiel!
Ändere den Graphen nach deinen Vorstellungen:
Der Graph besteht aus zwei Knotenmengen und Kanten zwischen diesen Knotenmengen.
Um einen Knoten in einer Knotenmenge zu erstellen, mache einen Doppelklick in der Nähe dieser Knotenmenge.
Es können maximal 8 Knoten in je einer Knotenmenge erstellt werden.
Um eine Kante zu erstellen, klicke zunächst auf den Ausgangsknoten und dann auf den Zielknoten.
Du kannst nur Kanten zwischen verschiedenen Knotenmengen einfügen.
Bild 2 Einfacher Graph mit einem Augmentationsweg. Links ist ein Augmentationsweg herhorgehoben.
Rechts ist der Graph nach der Augmentation abgebildet.
Bild 3 Graph mit dem dazugehörigen Schichtgraphen. Die knotendisjunkten Augmentationswege sind im Schichtgraphen fett markiert.
Bild 4 Die grauen Knoten kommen in dieser Iteration bereits in anderen kürzesten Augmentationswegen vor.
Der markierte Augmentationsweg ist knotendisjunkt bezüglich der schon verwendeten grauen Knoten.
Matching auf bipartiten Graphen
Zahlreiche Zuordnungsprobleme lassen sich als bipartite Matching-Probleme modellieren.
Ein einfaches Beispiel ist die Zuordnung von Studenten zu den Arbeitsstellen.
Nicht jede Zuordnung ist möglich, da Studenten über unterschiedliche Qualifikationen verfügen.
Das Problem lässt sich besser veranschaulichen, wenn man sich unter Studenten eine Knotenmenge und unter Arbeitsstellen eine weitere Knotenmenge vorstellt.
Die Kanten zwischen diesen Knotenmengen repräsentieren mögliche Zuordnungen bzw. Qualifikationen.
Das Ziel ist möglichst viele passende Zuordnungen zu finden, wobei die Studenten nur eine Stelle annehmen können und die Stellen nur einmal vergeben werden.
Gegeben ist ein bipartiter Graph \(G=(V,E)\). Ein Graph ist bipartit, falls er aus zwei Knotenmengen U und V besteht, sodass zwischen den Knoten innerhalb der Knotenmengen keine Kanten existieren.
Ein Matching ist eine Menge von Kanten, sodass jeder Knoten auf maximal einer Kante liegt. Das erste Bild zeigt ein Matching auf einem bipartiten Graphen.
Das zu untersuchende Problem ist das Bestimmen von kardinalitätsmaximalen (maximale Anzahl von Elementen) Matchings auf bipartiten Graphen.
Idee des Algorithmus
Sei M das aktuelle Matching (am Anfang ist es leer). Kanten in M heißen Matching-Kanten, alle anderen freie Kanten. Die freien Kanten sind auf den Bildern schwarz gekennzeichnet und die Matching-Kanten grün.
Ein Knoten, der auf einer Matching-Kante liegt, heißt besetzt (oder gematcht). Anderenfalls ist der Knoten frei. Die besetzten Knoten besitzen auf den Bildern grüne Farbe und freie Knoten blaue Farbe.
Ein Augmentationsweg im Graphen G ist ein Weg, der
mit einem freien Knoten startet,
mit einem freien Knoten endet und
abwechselnd freie Kanten und Matching-Kanten benutzt.
Das zweite Bild zeigt einen Graphen, in dem ein Augmentationsweg markiert ist.
Wenn man die Matching-Kanten eines Augmentationsweges aus M entfernt und stattdessen die freien Kanten des Augmentationsweges zu dem Matching hinzufügt, wird die Kardinalität des Matchings genau um 1 erhöht.
Alle Knoten auf dem Augmentationswegs liegen maximal auf einer Matching-Kante. Die Endknoten liegen auf keiner Matching-Kante, sodass nach dem Augmentationsschritt ein gültiges Matching entsteht.
Die Anzahl der freien Kanten ist in einem Augmentationsweg genau um 1 größer als die Anzahl der Matching-Kanten. Nach der Augmentation wird das Matching also vergrößert.
Ein Theorem aus der Graphentheorie besagt: Ein Matching M in G(V,E) ist genau dann kardinalitäts-maximal, wenn es keinen Augmentationsweg gibt.
Ein einfacher Algorithmus zur Bestimmung von maximalen Matchings besteht darin, immer nach einem Augmentationsweg zu suchen und das Matching zu vergrößern. Existiert kein Augmentationsweg mehr, so ist das Matching optimal.
Allerdings kann die Laufzeit dieses Algorithmus in bestimmten Fällen lang sein.
Der Algorithmus von Hopcroft und Karp verbessert die Laufzeit im Vergleich zu dem einfachen Algorithmus.
In jeder Iteration des Algorithmus werden nur die kürzesten Augmentationswege betrachtet. Es wird nach einer Menge von knotendisjunkten Augmentationswegen gesucht.
Das heißt, jeweils zwei Wege dürfen keinen gemeinsamen Knoten enthalten.
Die Menge von kürzesten knotendisjunkten Augmentationswegen sollte inklusions-maximal sein. Das bedeutet, dass es keinen weiteren kürzesten Augmentationsweg existiert, der knotendisjunkt bezüglich der bereits gefundenen ist.
Nachdem die gesuchte inklusions-maximale Menge von Augmentationswegen bestimmt wurde, wird das Matching augmentiert und es beginnt eine neue Iteration.
Nach jeder Iteration erhöht sich die Länge des kürzesten Augmentationsweges. Der Beweis dafür ist etwas kompliziert und wird deswegen ausgelassen.
Es ist aber intuitiv, dass die Länge der Augmentationswege nach einer Augmentation nicht kürzer wird. Falls keine Augmentationswege mehr existieren, terminiert der Algorithmus.
Finden von kürzesten Augmentationswegen
Die kürzesten Augmentationswege können mit Breiten- und Tiefensuche gefunden werden.
Man startet mit allen freien Knoten einer Knotenmenge (egal welcher) und fügt diese in die erste Schicht eines Schichtgraphen ein, der eine Zerlegung von V in mehrere Schichten darstellt und im Folgenden genauer erklärt wird. Schrittweise erzeugt man den Schichtgraphen, bis ein freier Knoten gefunden wurde oder alle Knoten bereits untersucht wurden.
Der Schichtgraph wird mit der folgenden Prozedur aufgebaut:
Von den Knoten der aktuellen Schicht folgt man den Kanten zu allen noch nicht untersuchten Nachbarn dieser Knoten, die jetzt die nächste Schicht darstellen.
Befindet sich ein freier Knoten in der neuen Schicht, so wird die Prozedur beendet. Ist die Schicht leer, so wird die Prozedur ebenfalls gestoppt und es wird ausgegeben, dass keine Augmentationswege existieren.
Anderenfalls erweitert man den so erstellten Schichtgraphen um eine weitere Schicht mit den Matching-Partnern der letzten Schicht.
Die Schicht mit den Matching-Partnern wird zur aktuellen Schicht und die Prozedur wird wiederholt. Am Ende entsteht ein Schichtgraph, der alle kürzesten (und nur die kürzesten) Augmentationswege enthält, falls Augmentationswege existieren.
Das dritte Bild zeigt den Schichtgraphen mit vier Schichten. Die erste Schicht besteht aus zwei freien Knoten der oberen Knotenmenge. Ihre Nachbarn werden zur zweiten Schicht hinzugefügt.
Da kein freier Knoten unter den Knoten der zweiten Schicht existiert, wird eine dritte Schicht mit den Matching-Partnern der zweiten Schicht erstellt.
Alle noch nicht betrachteten Nachbarn der dritten Schicht werden zur vierten Schicht hinzugefügt. Unter ihnen existieren zwei freie Knoten. Also endet die Prozedur.
Um eine inklusions-maximale Menge von knotendisjunkten Augmentationswegen zu finden, benutzt man den Schichtgraphen aus dem letzten Schritt. Man startet mit den freien Knoten der ersten Schicht und wendet die Tiefensuche darauf an.
Falls es einen Augmentationsweg gibt, der mit einem von diesen Knoten anfängt, wird er gefunden. Alle Knoten, die auf diesem Weg vorkommen, werden aus dem Schichtgraphen entfernt oder markiert.
Während der Ausführung des Algorithmus werden diese Knoten grau markiert. Wendet man diese Prozedur auf alle Knoten der
ersten Schicht an, so ist die gefundene Menge der kürzesten Augmentationswege knotendisjunkt und nach dem Ende dieser Prozedur existiert kein kürzester Augmentationsweg, der bezüglich der bereits gefundenen knotendisjunkt ist.
Auf dem dritten Bild sind die knotendisjunkten Augmentationswege durch dicke Pfeile hervorgehoben. In dieser Iteration würde also das Matching mit diesen beiden Augmentationswegen augmentiert werden.
Danach würde eine neue Iteration anfangen und ein neuer Schichtgraph erstellt werden.
Der Vorteil des Schichtgraphen ist, dass alle kürzesten Augmentationswege auf einmal gefunden werden.
Für die Bestimmung der inklusions-maximalen Menge von kürzesten knotendisjunkten Augmentationswegen müssen im schlimmsten Fall alle Kanten untersucht werden.
Was nun?
Einen Graph erstellen und den Algorithmus durchspielen
Der Hopcroft-Karp-Algorithmus nutzt Augmentationswege, um ein maximales Matching zu finden. In dieser Aufgabe kannst du selbst mit Augmentationswegen experimentieren.
Der Algorithmus stoppt an einigen Stellen, an denen du einen Augmentationsweg einzeichnen musst.
Dabei ist es nicht notwendig den kürzesten Augmentationsweg einzuzeichnen. Du kannst selbst entscheiden, welchen Augmentationsweg du nutzen möchtest.
Beim Wechsel des Tabs wird die Aufgabe abgebrochen.
Eingabe: Bipartiter ungewichteter Graph G=(U ∪ V, E)
Ausgabe: Matching M ⊆ E
BEGIN
M := ∅
REPEAT
l := Länge des kürzesten Augmentationsweges
Ρ := {P1,...,Pk} inklusions-maximale Menge
knotendisjunkter Augmentationswege der Länge l
M := M ⊕ (P1 ∪ P2 ∪ ... ∪ Pk)
UNTIL Ρ = ∅
RETURN M
END
Wie schnell ist der Algorithmus?
Geschwindigkeit von Algorithmen
Die Geschwindigkeit von Algorithmen wird üblicherweise in der Anzahl an Einzelschritten gemessen, die der Algorithmus bei der Ausführung benötigt.
Einzelschritte sind beispielsweise:
Zuweisungen – Weise Knoten 1 den Wert 20 zu.
Vergleiche – Ist 20 größer als 23?
Vergleich und Zuweisung – Falls 20 größer als 15 ist, setze Variable n auf 20.
Einfache Arithmetische Operationen – Was ist 5 + 5 ?
Da es sehr schwierig sein kann, diese Einzelschritte exakt zu zählen, möchte man nur die ungefähre Größenordnung der Anzahl Schritte wissen.
Man spricht auch von der Laufzeit des Algorithmus.
Meistens ist es besonders interessant, zu wissen, wie die Geschwindigkeit des Algorithmus von der Größe der Eingabe (hier: Anzahl Kanten und Knoten im Graph) abhängt.
Laufzeit des Hopcroft-Karp-Algorithmus
Angenommen der Graph enthält n Knoten und m Kanten.
In jeder Iteration des Algorithmus wird eine inklusions-maximale Menge von kürzesten knotendisjunkten Augmentationswegen gefunden.
Sei M ein Matching und M* das optimale Matching. Dann existieren \( |M^*|-|M| \) knotendisjunkte Augmentationswege bzgl. M. Untersuche die symmetrische Differenz M* ⊕ M = M*\M ∪ M\M*.
Ein Knoten kann hier maximal auf zwei Kanten liegen (eine aus M* und eine aus M). Dann enthält die symmetrische Differenz nur knotendisjunkte alternierende Kreise und Wege. In einem Kreis ist die Anzahl der Kanten aus M gleich der Anzahl der Kanten aus M*.
Dann aber müssen \( |M^*|-|M| \) knotendisjunkte alternierende Wege existieren, die mehr Kanten aus M* enthalten als aus M. Diese sind genau die Augmentationswege bezüglich M.
Sei M ein Matching und l die Länge des kürzesten Augmentationsweges bezüglich M. Dann ist die Kardinalität des optimalen Matchings maximal \( |M| + \frac{n}{(l+1)}\).
Es existieren \( |M^*|-|M| \) knotendisjunkte Augmentationswege bezüglich M. Jeder Augmentationsweg enthält mindestens l+1 Knoten, da die Länge des kürzesten Augmantationsweges l ist.
Dann gilt: \( (|M^*|-|M|)*(l+1) \leq n \), da die Wege knotendisjunkt sind und die Anzahl der Knoten im Graph n ist. Deshalb ist \( |M^*|-|M| \leq \frac{n}{(l+1)}\)
Das heißt, es gibt maximal \( \frac{n}{(l+1)}\) Augmentationen bezüglich M.
Die Länge des kürzesten Augmentationsweges wird mit jeder Iteration länger. Dies wird hier nicht bewiesen. Den Beweis kann der interessierte Leser in der geeigneten Literatur nachlesen.
Intuitiv ist es jedoch klar, dass die Augmentationswege nicht kürzer werden können.
Dann muss aber nach der \(\sqrt{n}\) Iteration des Algorithmus die Länge des kürzesten Augmentationsweges mindestens \(\sqrt{n}\) betragen.
Dann existieren maximal \(\frac{n}{\sqrt{n}+1} \leq \sqrt{n}\) zusätzliche Augmentationen. In jeder Iteration wird mindestens ein Augmentationsweg gefunden.
Daraus geht hervor, dass es maximal \(2\sqrt{n}\) Iterationen geben kann.
Jede Kante wird im Laufe einer Iteration nur konstant viele Male betrachtet und verarbeitet. Es wird die Breitensuche und die Tiefensuche ausgeführt, wo jede Kante nur einmal betrachtet wird.
Außerdem wird das Matching aktualisiert. Wir können also die Verarbeitung einer Kante während einer Iteration als einen einzigen Verarbeitungsschritt zusammenfassen.
Dann kann jede Iteration in \(m\) Schritten durchgeführt werden. Wie das genau funktioniert, kann der Leser unter "Beschreibung des Algorithmus" nachlesen.
Die Gesamtlaufzeit des Algorithmus ist in der Größenordnung \(m\sqrt{n}\).
Wie beweist man, dass der Algorithmus stets ein korrekt arbeitet?
In jeder Iteration des Algorithmus wird nach Augmentationswegen gesucht und das Matching wird verbessert. Es können nur endlich viele Verbesserungen durchgeführt werden, sodass der
Algorithmus terminiert.
Ein Theorem aus der Graphentheorie besagt: Ein Matching M in G(V,E) ist genau dann kardinalitäts-maximal, wenn es keinen Augmentationsweg gibt.(Berge´s Lemma)
Nach der letzten Iteration des Hopcroft-Karp-Algorithmus existieren keine Augmentationswege mehr. Dann ist das gefundene Matching optimal und der Hopcroft-Karp-Algorithmus berechnet das richtige Ergebnis.
Wo finde ich noch mehr Informationen zu Graphalgorithmen?
Ein letzter Hinweis zum Ziel und Inhalt dieser Seite und zu Zitationen
Der Lehrstuhl M9 der TU München beschäftigt sich mit diskreter Mathematik, angewandter Geometrie und der mathematischen Optimierung von angewandten Problemen. Die hier dargestellten Algorithmen sind sehr grundlegende Beispiele für Verfahren der diskreten Mathematik (die tägliche Forschung des Lehrstuhls geht weit darüber hinaus). Die vorliegenden Seiten sollen SchülerInnen und Studierenden dabei helfen, diese auch im realen Leben sehr wichtigen Verfahren (besser) zu verstehen und durch Ausprobieren zu durchdringen. Aus diesem Grund konzentriert sich die Darstellung bewusst auf die Ideen der Algorithmen, und präsentiert diese oftmals unter weitestgehendem Verzicht auf mathematische Notation.
Bitte beachten Sie, dass diese Seiten im Rahmen von studentischen Arbeiten unter Betreuung des Lehrstuhls M9 erstellt wurden. Den dabei entstandenen Code und die zugehörige Darstellung können wir nur punktuell überprüfen, und können deshalb keine Garantie für die vollständige Korrektheit der Seiten und der implementierten Algorithmen übernehmen.
Selbstverständlich freuen wir uns über jegliches (auch kritisches) Feedback bezüglich der Anwendungen sowie eventuellen Ungenauigkeiten und Fehlern der Darstellung und der Algorithmen. Bitte nutzen Sie hierzu den Anregungen-Link, welcher auch rechts in der Fußleiste zu finden ist.
Um diese Seite zu zitieren, nutze bitte die folgenden Angaben:
Titel: Der Hopcroft-Karp - Algorithmus
Autoren: Wolfgang F. Riedl, Ruslan Zabrodin; Technische Universität München
