Der Blossom Algorithmus von Edmonds

Einführung
Graph erstellen
Algorithmus ausführen
Beschreibung des Algorithmus
Weiteres

Größte Matchings in allgemeinen Graphen

Größtes Matching in einem Graphen.
Kanten des Matchings sind blau markiert.

Ein oft genutztes und intensiv erforschtes Problem der Graphentheorie ist die Berechnung eines größten Matchings in einem Graph \( G=(V,E)\). Ein Matching M ist dabei eine Teilmenge der Kanten, so dass jeder Knoten von maximal einer Kante des Matchings getroffen wird. M ist ein größtes Matching, falls kein anderes Matching in G mehr Kanten als M hat.

Diese Seite stellt den Blossom Algorithmus von Edmonds vor, welcher ein größtes Matching in einem ungerichteten Graphen berechnet. Im Gegensatz zu anderen Matching-Algorithmen muss der Graph hierbei nicht bipartit sein. Der Algorithmus wurde 1965 von Jack Edmonds vorgestellt und wurde seither noch auf verschiedene Arten weiterentwickelt und verbessert. Viele moderne Verfahren zur Berechnung von größten Matchings in allgemeinen Graphen basieren auch heute noch auf der Grundidee des Blossom Algorithmus.

Der Blossom Algorithmus von Edmonds nutzt und erweitert die grundsätzliche Idee des Hopcroft-Karp Algorithmus, welcher größte Matchings auf bipartiten Graphen berechnet. Falls du den Algorithmus noch nicht kennst, empfehlen wir dir ihn vorher kurz anzusehen: Hopcroft-Karp Algorithmus

Weiterhin nehmen wir an, dass grundlegende Methoden der Graphsuche wie die Breitensuche bekannt sind.

Dieses Applet gibt eine Visualisierung und detaillierte Erklärung des Blossom Algorithmus wieder. Du kannst einen beliebigen Graphen erstellen, auf diesem Graphen ein größtes Matching berechnen und mehr über die theoretischen Hintergründe des Algorithmus lernen.

Was möchtest du zuerst tun?

SVG Download

Legende

	Knoten
	ungerichtete Kante

Legende

Auf welchem Graph soll der Algorithmus ausgeführt werden?

Nimm ein fertiges Beispiel!

Wähle aus

Ändere den Graphen nach deinen Vorstellungen:

Um einen Knoten zu erstellen, mache einen Doppelklick in das Zeichenfeld.
Um eine Kante zu erstellen, klicke zunächst auf den Ausgangsknoten und dann auf den Zielknoten.
Ein Rechtsklick löscht Kanten und Knoten.

Lade den veränderten Graphen herunter:

Download

Lade einen existierenden Graphen hoch:

Ein

trat auf beim Lesen der Datei:

Fehlerbeschreibung:

Was nun?

SVG Download

Legende

	gelb: freier Knoten
	rot umrandet: Wurzel der BFS
	rot: aktuell aktiver Knoten der BFS
	orange: aktuell betrachteter Nachbar in BFS
	grün: Knoten auf augmentierendem Pfad
	großer Knoten: kontrahierter Knoten
	orange: aktuell betrachtete Kante der BFS
	blau: Kante in Matching
	grau hinterlegt: Kante in BFS Baum
	grün hinterlegt: Kante in augmentierendem Pfad

Legend

Status des Algorithmus

rewind Vorspulen

Erklärung
Pseudocode

Blossom Algorithmus von Edmonds

Der Algorithmus kann nun beginnen. Klicke auf "Nächster Schritt", um den nächsten Schritt des Algorithmus auszuführen. Klicke auf "Zurück", um den letzten Schritt rückgängig zu machen, und auf "Vorspulen", um den Algorithmus schnell auszuführen.

Breitensuche fertig

Die BFS Liste ist leer. Die modifizierte Breitensuche hat keinen augmentierenden Pfad gefunden.

Verbessertes Matching

Der augmentierende Pfad wird invertiert, um das Matching zu vergrößern. Dies bedeutet, dass alle nicht im Matching enthaltenen Kanten des augmentierenden Pfades ins Matching aufgenommen werden, und die vorher im Matching enthaltenen Kanten des Pfades aus dem Matching entfernt werden. Dadurch erhöhrt sich die Anzahl der Kanten im Matching um 1. Das neue Matching ist blau markiert.

Freie Knoten vorhanden

Es gibt noch vom Matching nicht überdeckte Knoten (gelb). Wir nennen sie freie Knoten. Wir versuchen nun, einen augmentierenden Pfad zu finden und damit das Matching zu vergrößern. Ein augmentierender Pfad beginnt und endet an einem freien Knoten und nutzt dazwischen abwechselnd im Matching und nicht im Matching enthaltene Kanten.

Beginne Breitensuche

Wir wählen einen der freien Knoten als Wurzel der modifizierten Breitensuche (BFS). Er wird für die Dauer der Breitensuche rot umrandet. Ausgehend von der gewählten Wurzel konstruieren wir einen Baum bestehend aus alternierenden Pfaden (den BFS Baum), bis wir einen anderen freien Knoten erreichen.

Nehme nächsten Knoten der BFS Liste

Ausgehend vom aktuellen Knoten können wir keine weiteren Nachbarn überprüfen. Deshalb führen wir die Breitensuche beim nächsten Knoten in der Liste fort.

Kontrahiere Blossom

Der gefundene Kreis ungerader Länge wird zu einem Pseudoknoten kontrahiert. Pseudoknoten werden im Graphen größer dargestellt. Wir fügen den neuen Pseudoknoten zusätzlich in die BFS Liste ein.

Führe Breitensuche mit nächstem Knoten fort

Nehme den nächsten Knoten aus der BFS Liste. Wir nennen diesen Knoten unseren aktiven Knoten und markieren ihn rot. Ausgehend von diesem Knoten werden wir die Nachbarn betrachten und einen freien Knoten suchen.

Erweitere BFS Baum

Wir fügen den Nachbarn und seinen Matchingpartner in den BFS Baum ein. Der Matchingpartner wird zudem in die BFS Liste eingefügt und wird eventuell später wieder betrachtet. Die Kanten im BFS Baum werden grau hervorgehoben.

Ignoriere Kreis gerader Länge

Wir können Kreise gerader Länge ignorieren. In dem Fall geschieht deshalb nichts Weiteres.

Betrachte nächsten Nachbarn

Wir überprüfen den nächsten Nachbarn (orange) und sehen, dass er bereits vom Matching überdeckt ist.

Betrachte nächsten Nachbarn

Wir überprüfen den nächsten Nachbarn (orange) und sehen, dass er ein freier Knoten ist (gelb). Wir haben deshalb einen augmentierenden Pfad zwischen der Wurzel der Suche und diesem Nachbarn gefunden.

Betrachte nächsten Nachbarn

Wir überprüfen den nächsten Nachbarn (orange) und sehen, dass er bereits in der BFS Liste enthalten ist. Wir wissen deshalb, dass ein Kreis existiert, welcher zudem eine ungerade Kantenzahl hat. Wir nennen solch einen Kreis eine Blüte (Blossom).

Betrachte nächsten Nachbarn

Wir überprüfen den nächsten Nachbarn (orange) und sehen, dass er bereits in der BFS Liste enthalten ist. Wir wissen deshalb, dass ein Kreis existiert, welcher zudem eine gerade Kantenzahl hat.

Rekonstruiere den augmentierenden Pfad

Der augmentierende Pfad ist grün markiert. Bevor wir das Matching vergrößern, müssen wir die kontrahierten Pseudoknoten wieder expandieren.

Expandiere Pseudoknoten

Einer der Pseudoknoten wurde expandiert und der augmentierende Pfad entsprechend angepasst. Es gibt noch weitrere Pseudoknoten, welche expandiert werden müssen.

Rekonstruiere den augmentierenden Pfad

Der augmentierende Pfad von der Wurzel der Breitensuche zum freien Knoten wurde vollständig rekonstruiert und ist grün markiert.

Rekonstruktion des augmentierenden Pfades fertig

Nach der Expansion aller Pseudoknoten ist der augmentierende Pfad vollständig rekonstruiert und grün markiert.

Algorithmus abgeschlossen

Im Graph sind keine freien Knoten mehr vorhanden, wir haben also ein größtes Matching gefunden. Es ist blau markiert.

BEGIN

WHILE F != ∅ DO (*freie Knoten F*)

wähle r ∈ F

queue.push(r) (*BFS Liste*)

T ← ∅ (*BFS Baum T*)

T.add(r)

WHILE queue != ∅

v ← queue.pop()

FOR ALL Nachbarn w von v DO

IF w ∉ T AND w in Matching THEN

T.add(w)

T.add(Matchingpartner(w))

queue.push(Matchingpartner(w))

ELSE IF w ∈ T AND gerader Kreis THEN

CONTINUE

ELSE IF w ∈ T AND ungerader Kreis THEN

kontrahiere Kreis

ELSE IF w ∈ F THEN

expandiere alle kontrahierten Knoten

rekonstruiere augm. Pfad

invertiere augm. Pfad

END

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.

Matchings in Graphen

Figure 1.
Matching in einem nicht-bipartiten Graphen, welches nicht größtmöglich ist. 3 und 5 sind freie Knoten.

Figure 2.
Augmentierender Pfad von freiem Knoten 3 zu freiem Knoten 5.

Figure 3.
Matching nach Invertierung des augmentierenden Pfads. Da keine freien Knoten mehr existieren, muss das Matching größtmöglich sein.

Figure 4.
BFS Baum in Schichtstruktur (in grau) mit Wurzel 8 und aktuellen Knoten 3. Schicht 0: 8, Schicht 1: 0 und 2, Schicht 2: 1 und 3, ...

Wir betrachten einen ungerichteten Graphen \( G=(V,E)\) mit Knotenmenge V und Kantenmenge E. Ein Matching \(M \subseteq E\) ist eine Teilmenge der Kanten, so dass jeder Knoten von maximal einer Kante des Matching M überdeckt ist. In Figure 1 sieht man ein zulässiges Matching in einem Graphen. Die Matchingkanten sind blau markiert. Jeder Knoten ist mit maximal einer Matchingkante verbunden. Würden wir beispielsweise die Kante zwischen 0 und 3 zum Matching hinzufügen, wäre es kein Matching mehr da 0 mit zwei Kanten verbunden wäre.

Ein Knoten welcher nicht vom Matching überdeckt ist nennen wir einen freien Knoten. Für eine Kante \( e = \{v, w\} ∈ M\) ist v der Matchingpartner von w und andersherum. In unserem Beispiel sind 3 und 5 freie Knoten, da keine der blauen Matchingkanten sie überdeckt. 0 und 1 sind Matchingpartner, 2 und 4 ebenso.

Ein Matching M ist ein größtes Matching falls die Anzahl an Matchingkanten maximal ist, d.h. falls kein anderes Matching M' in G existiert mit |M'|>|M|. Das Matching in Figure 1 ist nicht größtmöglich. Wir können offensichtlich die Kante zwischen den beiden freien Knoten 3 und 5 einfügen und damit die Anzahl der Matchingkanten auf 3 erhöhen.

Ein Graph wird bipartit genannt, wenn man seine Knoten so in zwei Mengen V₁ und V₂ aufteilen kann, dass jede Kante einen Endknoten in V₁ und den anderen Endknoten in V₂ hat. Wir wissen, dass ein Graph genau dann bipartit ist, wenn er keinen Kreis ungerader Länge besitzt. Offensichtlich ist der Graph in unserem Beispiel nicht bipartit, da er Dreiecke enthält.

Der Blossom Algorithmus von Edmonds berechnet ein größtes Matching in allgemeinen Graphen. Im Gegensatz zu vielen anderen Algorithmen muss der Graph nicht bipartit sein. Der Algorithmus erweitert die Idee des Hopcroft-Karp Algorithmus (welcher ein größtes Matching auf einem bipartiten Graphen berechnet) indem er Kreise ungerader Länge entsprechend behandelt.

Algorithmus für bipartite Graphen

Wir wiederholen zuerst kurz die Grundidee des Hopcroft-Karp Algorithmus, welche ebenfalls für den Blossom Algorithmus von Edmonds wichtig ist. Um ein gegebenen Matching zu vergrößern suchen wir einen augmentierenden Pfad. Ein augmentierender Pfad ist ein Pfad welcher an einem freien Knoten beginnt, an einem freien Knoten endet und dazwischen abwechselnd Matchingkanten und nicht im Matching enthaltene Kanten nutzt. Ein Beispiel eines augmentierenden Pfades (markiert in grün) ist in Figure 2 zu sehen. Der Pfad beginnt am freien Knoten 3 und endet am freien Knoten 5 und nutzt dazwischen abwechselnd entsprechende Kanten. Ein anderes (sehr einfaches) Beispiel eines augmentierenden Pfades ist die Kante zwischen 3 und 5, welche wir schon im ersten Abschnitt erwähnt haben.

Sobald wir einen augmentierenden Pfad gefunden haben, können wir das Matching durch Invertierung des Pfades vergrößern: Matchingkanten des Pfades werden aus dem Matching entfernt, bisher nicht im Matching enthaltene Kanten des Pfades werden hinzugefügt. Hierdurch erhöht sich die Anzahl der Matchingkanten um 1. Das Ergebnis dieses Vorgehens (ein Matching mit drei statt zwei Kanten) kann in Figure 3 gesehen werden.

Der folgende Satz von C. Berge ist essentiell für den Algorithmus: Ein Matching M ist nicht größtmöglich genau dann, wenn in G ein augmentierender Pfad existiert. Können wir also in G keinen augmentierenden Pfad mehr finden ist das vorhandene Matching größtmöglich.

Aber wie findet man einen augmentierenden Pfad im Graph? Wir nehmen einen beliebigen freien Knoten r und beginnen von ihm eine angepasste Breitensuche (BFS). Während wir den Graph nach und nach durchsuche, konstruieren wir einen Baum mit Schichtstruktur mit Wurzel r. Kanten von geraden zu ungeraden Schichten sind nicht im Matching, Kanten von ungeraden zu geraden Schichten sind Matchingkanten. Solch ein Baum mit Schichtstruktur ist in Figure 4 zu sehen.

Wenn wir während der Ausführung der Breitensuche einen neuen Knoten v besuchen, kann einer der folgenden Fälle auftreten:

Fall 1: v ist ein freier Knoten
Wir haben einen augmentierenden Pfad von r nach v gefunden. Wir invertieren den Pfad und sind mit der Breitensuche fertig.
Fall 2: v ist bereits im Matching überdeckt und bisher noch nicht im Baum enthalten
Dann fügen wir v und seinen Matchingpartner zum Baum hinzu und fügen den Matchingpartner zusätzlich in die BFS Liste ein, um später die Suche von dort aus fortzuführen.
Fall 3: v ist bereits im Baum enthalten und wir haben einen Kreis gerader Länge gefunden
In diesem Fall müssen wir nichts tun, wir ignorieren v einfach und machen mit der Breitensuche weiter.
Fall 4: v ist bereits im Baum enthalten und wir haben einen Kreis ungerader Länge gefunden
Da unser Graph bipartit ist, kann dieser Fall nicht auftreten. Wenn wir den Blossom Algorithmus auf einem allgemeinen Graphen ausführen, müssen wir mit diesem Fall umgehen können.

Allgemeine Graphen: Wir behandelt man Kreise ungerader Länge?

In allgemeinen Graphen nutzen wir auch die oben erklärte Methode zum Finden augmentierender Pfade. Dann können wir allerdings auf Kreise ungerader Länge stoßen (Fall 4) und müssen wissen, wie wir mit ihnen umgehen müssen. Hierzu wird folgende Idee genutzt: Wir ignorieren den gesamten Kreis, indem wir ihn zu einem einzelnen Pseudoknoten kontrahieren und führen im Anschluss die Breitensuche auf dem resultierenden Graphen fort. Wenn wir irgendwann später einen augmentierenden Pfad gefunden haben, müssen wir alle Pseudoknoten (in umgekehrter Reihenfolge) wieder expandieren, bevor wir das Matching mit Hilfe des augmentierenden Pfades vergrößern. Wir nennen solche Kreise ungerader Länge Blüten (Blossoms), woher der Name des Algorithmus stammt.

Wir veranschaulichen die Kontraktion eines Kreises ungerader Länge zu einem Pseudoknoten und die anschließende Expansion am folgenden kleinen Beispiel. Im Bild auf der linken Seite ist ein BFS Baum mit Schichtstruktur und Wurzel 4 zu sehen. Der aktive Knoten ist aktuell 1, und wir betrachten die Kante zwischen Knoten 1 und 3. Da 3 bereits im Baum enthalten ist, muss ein Kreis existieren. Dieser Kreis hat ungerade Länge, weshalb wir in Fall 4 sind und den gesamten Kreis (1, 0, 4, 2, 3) zu einem neuen Pseudoknoten 7 kontrahieren (auf der rechten Seite).

Wir setzen die Breitensuche von 7 aus fort und finden einen augmentierenden Pfad zwischen 7 und 5. Wenn wir einen augmentierenden Pfad gefunden haben, müssen wir überprüfen, ob kontrahierte Pseudoknoten existieren welche wieder expandiert werden müssen. Wir expandieren deshalb Pseudoknoten 7 und erhalten den ursprünglichen Kreis wieder (1, 0, 4, 2, 3) (Bild rechts). Zusätzlich müssen wir den augmentierenden Pfad korrekt durch den Kreis ungerader Länge rekonstruieren. Da keine Pseudoknoten mehr vorhanden sind, können wir den augmentierenden Pfad invertieren.

Warum funktioniert die Kontraktion von Blüten?

Wir illustrieren die Idee hinter der Kontraktion von Kreisen ungerader Länge am folgenden Beispiel. Das Bild zeigt eine Momentaufnahme des Algorithmus: Wir haben bereits einen BFS Baum mit Schichtstruktur und Wurzel 8 und entdecken nun den Kreis (3,3,4,5,6), als wir die Kante zwischen 5 und 6 betrachten. Wir nennen die Pfad von der Wurzel zur Blüte (d.h. hier 8 nach 3) den Stängel und den zentralen Knoten 3 die Spitze des Stängels.

Hierzu kann man feststellen, dass die letzte Kante des Stängels immer eine Matchingkante sein muss (im Beispiel die Kante von 2 nach 3). Zudem gibt es für jeden Knoten der Blüte (ausgenommen die Spitze) zwei verschiedene Pfade von der Spitze zum Knoten. Um beispielsweise Knoten 6 von der Spitze aus zu erreichen, können wir die Blüte entweder im Uhrzeigersinn durchlaufen und den Pfad (3,4,5,6) nutzen, oder wir laufen gegen den Uhrzeigersinn und nutzen den Pfad (3,7,6). Einer der Pfade endet immer mit einer Matchingkante, der andere mit einer nicht im Matching enthaltenen Kante. Deshalb wird uns später einer der beiden Pfade dabei helfen können, den augmentierenden Pfad korrekt zu rekonstruieren. Im Moment können wir im Algorithmus diese Entscheidung nicht treffen, da wir noch nicht wissen wohin der augmentierende Pfad (wenn einer existiert) führend wird. Deshalb verschieben wir die Entscheidung, wie genau wir durch die Blüte laufen, indem wir die gesamte Blüte zu einem Pseudoknoten kontrahieren. Falls wir einen freien Knoten finden, expandieren wir den Pseudoknoten wieder und können dann im Anschluss den augmentierenden Pfad korrekt rekonstruieren.
Betrachte dazu die beiden oben aufgeführten Beispiele. In beiden Graphen finden wir den freien Knoten 9 und müssen den augmentierenden Pfad durch die Blüte rekonstruieren. Die Kante von 9 zur Blüte ist in beiden Fällen keine Matchingkante, weshalb wir jeweils die Überquerung der Blüte mit einer Matchingkante beginnen müssen (zwischen 6 und 7). Deshalb gehen wir im ersten Graphen im Uhrzeigersinn, bis wir die Spitze 3 erreichen, und im zweiten Graphen gegen den Uhrzeigersinn. Suche

Was nun?

Einen Graph erstellen und den Algorithmus durchspielen

Wie sieht der (Pseudo-)Code des Algorithmus aus?


                    BEGIN
                      WHILE F != ∅ DO   (*Freie Knoten F*)
                        wähle r ∈ F
                        queue.push(r)             (*BFS Liste*)
                        T ← ∅                    (*BFS Baum T*)
                        T.add(r)
                        WHILE queue != ∅
                          v ← queue.pop()
                          FOR ALL Nachbarn w von v DO
                            IF w ∉ T AND w in Matching THEN
                              T.add(w)
                              T.add(Matchingpartner(w))
                              queue.push(Matchingpartner(w))
                            ELSE IF w ∈ T AND gerader Kreis THEN
                              CONTINUE
                            ELSE IF w ∈ T AND ungerader Kreis THEN
                              kontrahiere Kreis
                            ELSE IF w ∈ F THEN
                              expandiere alle kontrahierten Knoten
                              rekonstruiere augm. Pfad
                              invertiere augm. Pfad
                    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, Vergleiche oder einfache arithmetische Operationen.

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.

Um die ungefähre Laufzeit eines Algorithmus anzugeben, nutzt man die sogenannte Groß-Oh Notation. Diese erlaubt es, konstante Faktoren und Terme geringerer Ordnung zu ignorieren. Anstelle einer genauen Laufzeit von \( 2.5n^2 + 5n\log{n} - 1.5n + 8\) sagt man beispielsweise einfach, dass die Laufzeit in \( \mathcal{O} (n^2) \) ist, da \( n^2 \) der im Ausdruck dominierende Faktor ist. Für eine genauere Erkärung und eine formatle Definition der Groß-Oh Notation wie auch einige einfache Techniken zur Analyse von Codestücken siehe beispielsweise hier.

Laufzeit des Blossom Algorithmus von Edmonds

Zuerst muss man hier erwähnen, dass es viele verschiedene Implementierungen des Blossom Algorithmus gibt, welche sich stark in ihrer Laufzeit unterscheiden können. Sei n die Anzahl der Knoten und m die Anzahl der Kanten im Graphen. Der im ursprünglichen Paper von Jack Edmonds [1] beschriebene Algorithmus hat eine Laufzeit von \(\mathcal{O}(n^4)\). Im folgenden Abschnitt analysieren wir die Laufzeit der hier vorgestellten, auf Breitensuche basierenden Implementierung. Die Laufzeit wird \(\mathcal{O}(n^2 m)\) sein. Durch die Nutzung von fortgeschritteneren Implementierungstechniken (siehe Micali und Vazirani, [3]) kann die Laufzeit weiterhin auf \(\mathcal{O}(\sqrt{n} m)\) reduziert werden.

Analyse der Laufzeit

Es gibt maximal n freie Knoten. Für jeden dieser Knoten führen wir eine Breitensuche durch, um einen augmentierenden Pfad zu finden. Diese Breitensuche läuft in \( \mathcal{O} (n+m) = \mathcal{O} (m) \) auf zusammenhängenden Graphen. Zusätzlich zur Breitensuche müssen wir höchstens n Kontraktionen (und dementsprechend maximal n Expansionen) durchführen. Eine einzelne Kontraktion kann in \( \mathcal{O} (m)\) durchgeführt werden, da im schlimmst Fall alle Knoten zu einem Pseudoknoten kontrahiert werden müssen. Nachdem wir einen augmentierenden Pfad gefunden haben, müssen wir ihn invertieren, was \( \mathcal{O} (n) \) Operationen in Anspruch nimmt (im schlimmsten Fall). Zusammengenommen führt das zu einer gesamten Laufzeit von \( \mathcal{O} (n \cdot (m + nm + n)) = \mathcal{O} (n^2 m)\).

Wie kann der Algorithmus verbessert werden?

Der Algorithmus dieser Homepage wurde so implementiert, dass die grundlegenden Ideen einfach verstanden und dargestellt werden können. Natürlich gibt es viele Möglichkeiten, die Performanz des Algorithmus zu verbessern. Wir stellen einige Ideen von Micali's und Vazirani's Algorithmus [3] vor, welche die Laufzeit weiter auf \(\mathcal{O}(\sqrt{n} m)\) reduzieren:

Anstatt die Breitensuche von einem einzelnen freien Knoten aus auszuführen, könnten wir sie an allen freien Knoten gleichzeitig starten. Hierdurch könnten wir mehrere separate augmentierende Pfade finden und die Größe des Matchings mit einer einzigen Breitensuche um mehr als 1 erhöhen.
Nicht alle Blüten müssen sofort kontrahiert werden. Es gibt hierfür eine Bedingung, welche angibt, ob wir einen Kreis ungerader Länge kontrahieren müssen oder ob wir den Prozess aufschieben können.
Eine spezielle Benennungstechnik erlaubt eine schnelle Expansion der Blüten.

Weiterhin können gemäß Edmonds unter bestimmten Bedingungen Pseudoknoten kontrahiert bleiben, bis ihre Expansion wirklich benötigt wird. In unserer Implementierung expandieren wir alle Pseudoknoten im Graph, sobald ein augmentierender Pfad gefunden wurde. In vielen Fällen wäre dies nicht nötig.

Literatur

Veröffentlichungen

[1] Edmonds, Jack. "Paths, trees, and flowers." Canadian Journal of mathematics 17.3 (1965): 449-467.

[2] Edmonds, Jack. "Maximum matching and a polyhedron with 0, l-vertices." J. Res. Nat. Bur. Standards B 69.1965 (1965): 125-130.

[3] Micali, Silvio, and Vijay V. Vazirani. "An \(\mathcal{O}(\sqrt{|V|} |E|)\) algorithm for finding maximum matching in general graphs." Foundations of Computer Science, 1980., 21st Annual Symposium on. IEEE, 1980.

Web resources

[4] A Compendium of Applications of the Graph Matching Problem. http://www.cs.odu.edu/~mhalappa/matching/applications.html (accessed on June 6, 2016)

Wo finde ich noch mehr Informationen zu Graphalgorithmen?

Weitere Graphalgorithmen werden auf der Webseite des Lehrstuhls M9 der TU München erklärt.

Außerdem gibt es ein interessantes Buch zu kürzesten Wegen: Das Geheimnis des kürzesten Weges

Ein Mathematikstudium an der TU München beantwortet alle Fragen zur Graphentheorie (falls eine Lösung bekannt ist).

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 Blossom Algorithmus von Edmonds
Autoren: Johannes Feil, Wolfgang F. Riedl; Technische Universität München
Link: https://www-m9.ma.tum.de/graph-algorithms/-blossom-algorithm

Größte Matchings in allgemeinen Graphen

Dieses Applet gibt eine Visualisierung und detaillierte Erklärung des Blossom Algorithmus wieder. Du kannst einen beliebigen Graphen erstellen, auf diesem Graphen ein größtes Matching berechnen und mehr über die theoretischen Hintergründe des Algorithmus lernen.

Was möchtest du zuerst tun?

Legende

Legende

Auf welchem Graph soll der Algorithmus ausgeführt werden?

Nimm ein fertiges Beispiel!

Ändere den Graphen nach deinen Vorstellungen:

Lade den veränderten Graphen herunter:

Lade einen existierenden Graphen hoch:

Was nun?

Legende

Legend

Status des Algorithmus

Blossom Algorithmus von Edmonds

Breitensuche fertig

Verbessertes Matching

Freie Knoten vorhanden

Beginne Breitensuche

Nehme nächsten Knoten der BFS Liste

Kontrahiere Blossom

Führe Breitensuche mit nächstem Knoten fort

Erweitere BFS Baum

Ignoriere Kreis gerader Länge

Betrachte nächsten Nachbarn

Betrachte nächsten Nachbarn

Betrachte nächsten Nachbarn

Betrachte nächsten Nachbarn

Rekonstruiere den augmentierenden Pfad

Expandiere Pseudoknoten

Rekonstruiere den augmentierenden Pfad

Rekonstruktion des augmentierenden Pfades fertig

Algorithmus abgeschlossen

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Matchings in Graphen

Algorithmus für bipartite Graphen

Allgemeine Graphen: Wir behandelt man Kreise ungerader Länge?

Warum funktioniert die Kontraktion von Blüten?

Was nun?

Einen Graph erstellen und den Algorithmus durchspielen

Wie sieht der (Pseudo-)Code des Algorithmus aus?

Wie schnell ist der Algorithmus?

Geschwindigkeit von Algorithmen

Laufzeit des Blossom Algorithmus von Edmonds

Analyse der Laufzeit

Wie kann der Algorithmus verbessert werden?

Verwandte Probleme und Algorithmen

Literatur

Veröffentlichungen

Web resources

Wo finde ich noch mehr Informationen zu Graphalgorithmen?

Ein letzter Hinweis zum Ziel und Inhalt dieser Seite und zu Zitationen