Ford und Fulkerson

freakC++

Hallo zusammen,

ich versuche gerade vergebens den "Ford und FulkersoN" Algorithmus zu verstehen. Bei Wikipedia werden immer Rückkanten eingezeichenet. Doch warum? Es wird plötzlich angenommen, dass der Fluss in die andere Richtung fließt, obwohl die Kantenrichtung dies verbietet. Kann mir das jemand erklären?

Vielen Dank
LG, freakC++

icarus2

Im Algorithmus waehlst du jeweils einen Pfad von der Quelle zur Senke entlang dessen du den Fluss vergroesserst. Diesen Pfad kannst du frei waehlen, d.h. du kannst eine schlechte Wahl getroffen haben. Du findest leicht ein Beispiel, bei dem du je nach Wahl des Pfades den Fluss nicht mehr vergroessern kannst, obwohl er noch nicht maximal ist.

Deswegen willst du so eine Pfadwahl in einem gewissen Sinne ruckgaengig machen koennen, d.h. du willst den Fluss an einer gewissen Stelle zuruecknehmen koennen.

Indem du Ruckwaertskanten einfuehrst passiert dies im Algorithmus automatisch.

Die Erklaerung ist etwas ungenau, sollte dir aber die Intuition geben. Wende den Algorithmus einmal auf ein paar kleine Beispiele mit und ohne Rueckwaertskanten an, dann siehst du relativ schnell, warum du die Rueckwaertskanten brauchst.

freakC++

Aha...also die Rückwertskanten sind also meine Versicherung dafür, dass ich noch einmal einen Schritt zurückgehen kann, falls es noch eine bessere Lösung gibt. Bei Wikipedia werden diese Rückkanten nämlich wie normale Kanten benutzt, also der Fluss fließt plötzlich in die andere Richtung, obwohl dies verboten ist.

Naja, mit der "Rückversicherung" kann ich schon besser leben.

edit: Im zweiten Punkt des zweiten Schritts des Algorithmus auf Wikipedia (http://de.wikipedia.org/wiki/Algorithmus_von_Ford_und_Fulkerson#Der_Algorithmus) steht folgendes:

$e \in E_{w} \cap E ...$

Doch gilt nicht $E_{w} \subseteq E$ ? Man könnte also nur $E_{w}$ schreiben!

$E_{w}$ sind doch die Kanten des aktuellen Weges von s nach t und $E$ enthält alle Kanten des ganzen Graphen.

Vielen Dank für die Antwort

freakC++

edit2: und warum gibt es für die Rückkanten keinen Durchfluss, sondern nur eine Kapazität?

freakC++ schrieb:

Doch gilt nicht Ew⊆E ? Man könnte also nur Ew schreiben!

In E_W kommen im Allgemeinen noch Kanten des Residualgraphen vor, in E nicht.

freakC++ schrieb:

edit2: und warum gibt es für die Rückkanten keinen Durchfluss, sondern nur eine Kapazität?

Unter der Annahme, dass du mit Durchfluss einer Kante e nur f(e) meinst (oft wird darunter die Differenz zw. Ein- und Ausfluss verstanden, die hier aber eh 0 ist):
Der Fluss auf der Kante ist, wenn man so will, implizit. Über die Kante, zu der die Rückkante gehört, fließt ja schon etwas. Und das willst du mit deiner Rückkante in der Zukunft auch irgendwie wieder ausgleichen können. Mir fällt jetzt auf die Schnelle auch kein Grund ein, was schief gehen sollte, wenn man die Kapazität der Rückkante gleich der der zugehörigen Vorwärtskante setzt und über die Rückkante von Haus aus die Restkapazität fließen lässt. Das Ergebnis sollte (könnte...) das gleiche sein.

Die Idee hinter den Rückkanten ist folgende: Du willst den Wert des Flusses maximieren. Dabei kann es dir irgendwann passieren (schreibt ja icarus2 schon), dass du merkst: "Hoppla, das hier ist ja gar nicht so optimal, wenn ich über eine andere Kante gehe, bin ich viel besser!". Anstatt jetzt den Fluss auf deiner nicht-ganz-so-optimalen Kante wieder zu verringern, erhöhst du einfach den Fluss über die Rückkante.

Michael E.

JFB schrieb:

Mir fällt jetzt auf die Schnelle auch kein Grund ein, was schief gehen sollte, wenn man die Kapazität der Rückkante gleich der der zugehörigen Vorwärtskante setzt und über die Rückkante von Haus aus die Restkapazität fließen lässt.

Die Flusserhaltung. Aber stimmt schon, dem Algorithmus würde das nichts ausmachen.