Augmenting Path Search in Bipartite Graphs

Moderator: Effiziente Graphenalgorithmen

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Augmenting Path Search in Bipartite Graphs

Beitrag von Dreamdancer »

Ich durchsteige den Algorithmus auf Folie 271 nicht, mit dem augmentierenden Pfad in einem bipartiten Graphen. Ich komme auch nicht auf die Beispielgraphen. Weiß da jemand eine gute Alternativbeschreibung? :oops:

Benutzeravatar
bender
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 7. Apr 2008 20:20

Re: Augmenting Path Search in Bipartite Graphs

Beitrag von bender »

Da saß ich auch ein bisschen dran :-(
Mit Hilfe eines Kommilitonen kammen wir auf folgendes:

Also man hat ein Matching M (wie auf Seite 272) und den alternierenden Wald F. In dem Wald sind bisher nur einzelne Knoten (einzelne Knoten sind ja auch Bäume ;-) ), die exposed sind. Dies wäre jetzt in dem Beispiel, die Knoten 1,5,6,9. Diese Knoten haben auch die Eigenschaft, dass sie "even" sind, da due Wurzel eines Baumes even ist. Man führt jetzt den Algorithmus aus und bekommt fast den Graphen, der auf Seite 273 zusehen ist. Der Unterschied ist, dass 1, 6 und 9 immer noch einzelne Knoten/Bäume sind.
Bis dahin hat der Algo nur "grow" ausgeführt. Jetzt gibt es zwei Möglichkeiten, entweder die 6 oder die 9 als \(v\) zu wählen. Machen wir es so wie im Beispiel. Wir wählen \(v=6\) und \(u=3\). In diesem Fall würde der Algorithmus "augment" ausführen und einen augmentierenden Pfad \((5, 8, 3, 6)\) zusammenstellen und zurückgeben.

Mit dem aufmentierenden Pfad wird ein neues Matching erstellt (seite 274) und der Algorithmus wird auf dem neuen Matching nochmals aufgerufen und dieser erstellt dann den ungarischen Wald (Seite 275).

Ich hoffe das hilft dir weiter.

Gruß
Bender

Antworten

Zurück zu „Effiziente Graphenalgorithmen“