852 4 Ford Fulkerson

Gunnar,

ich habe den Algorithmus zwar verstanden, aber wenn ich jetzt hier versuche, ihn komplett zu erklären, wird's wahrscheinlich genauso unverständlich wie im Skript. Ich versuche es mal ganz grob (und nicht ganz komplett) zum Verständnis:
1. Du beginnst mit einem leicht ersichtlichen zulässigen Fluss - das ist in den allermeisten Fällen ein "Nullfluss"
2. Jetzt fängst Du am Startknoten an und markierst alle "mit dem Startknoten verbundenen Knoten" (am besten in einer Tabelle). Die Markierung besteht aus zwei "Teilen" (a,b). Für das "a" schreibst Du die Nummer des Startknotens - zusätzlich versehen mit einem "+", wenn der Fluss vom Startknoten zum aktuellen Knoten geht, oder mit einem "-", wenn der Fluss vom aktuellen Knoten zum Startknoten geht. Hast Du ein "+" gesetzt (also anschaulich, wenn es sich um einen "Vorwärtsfluss"von Start in Richtung Ziel handelt), dann musst Du für das "b" die maximal noch mögliche Flussvergrößerung auf dieser Strecke (Startknoten-->aktueller Knoten) einsetzen. Dabei muss man zwei Dinge berücksichtigen: a) Wieviel darf auf der Strecke noch zusätzlich transportiert werden? UND b) Wieviel kann denn überhaupt vom Startknoten zusätzlich "losgeschickt" werden? Der kleinere von diesen beiden Werten ist die maximal mögliche Flussvergrößerung (im Skript bezeichnet mit Epsilonj). Wenn Du ein "-" gesetzt hast, passiert prinzipiell genau das Gleiche, nur dass entsprechend die maximal mögliche Flussverringerung gesucht wird. Markiert werden allerdings nur solche Knoten, bei denen noch eine Flussvergrößerung (bzw. bei "umgekehrter" Pfeilrichtung: Flussverkleinerung) möglich ist.
3. Wenn Du vom Startknoten ausgehend alle mit dem Startknoten verbundenen Knoten durchgegangen bist und gegebenenfalls markiert hast, dann suchst Du Dir einen beliebigen dieser markierten Knoten aus und wiederholst im Prinzip Schritt 2.) - nur dass jetzt Dein neu ausgesuchter Knoten prinzipiell dem Startknoten entspricht. Das wiederholst Du solange, bis Du am Zielknoten angekommen bist und diesen markiert hast.
4. Du hast jetzt also einen Weg über lauter markierte Knoten vom Start bis zum Ziel gefunden. Wahrscheinlich hast Du auch noch einige weitere Knoten markiert, die nicht auf diesem Weg liegen. Diese Knoten und deren Markierungen interessieren Dich jetzt nicht mehr. Auf dem gefundenen Weg vergleichst Du jetzt alle Werte für die maximal möglichen Flussvergrößerungen (oder eben - wenn auch ein "Rückwärtsstück" drin ist - die maximal möglichen Flussverkleinerungen) suchst Dir das Minimum aus und zählst dieses Minimum zu den bisherigen Flüssen auf der gefundenen Strecke dazu (bzw. ziehst es von den "Rückwärtsflüssen" ab).
5. Jetzt hast Du also einen neuen zulässigen Fluss, der größer ist als der Startfluss. Mit diesem Fluss (am besten malst Du Dir ein neues Bild) fängst Du den Algorithmus wieder ganz von vorne an.
6. Das Ganze wiederholst Du solange, bis Du keine Flussvergrößerung mehr finden kannst, d.h. Du keine Strecke mit markierten Knoten von Start bis zum Ziel finden kannst. Dein bisher gefundener Fluss ist maximal,

Ich weiß jetzt nicht wirklich, ob das jetzt verständlicher als im Skript war...
Vielleicht kannst Du auch genauer beschreiben, an welcher Stelle des Algorithmus Du noch Probleme hast?

Gruß Petra

ich sitze gerade auch an der Übungsaufgabe 4.4 und versuche diese Werte in der Lösung nachzuvollziehen. Ich bekomme immer andere Werte, als die in der Lösung.
Wie ermittel ich diesen Anfangsfluss mit der Stärke 16?
Ich habe schon eine Übungsaufgabe vom Lehrstuhl gerechnet, dort hatte ich keine Probleme, aber hier komme ich einfach nicht weiter.
VG Taja

Taja,

ich verstehe zwar Ford und Fulkerson nicht wirklich, aber ich habe so eine Vermutung, daß man mit den 16 anfangen muß, da ja in Abb. 4.14 auf Seite 83 der Anfangsfluss angegeben ist und in der Summe von W1 und W2 16 Einheiten wegfließen.
Ich hoffe, das hilft Dir weiter ...?

LG
Evalotto

Taja schrieb:

Hallo,

ich sitze gerade auch an der Übungsaufgabe 4.4 und versuche diese Werte in der Lösung nachzuvollziehen. Ich bekomme immer andere Werte, als die in der Lösung.
Wie ermittel ich diesen Anfangsfluss mit der Stärke 16?
Ich habe schon eine Übungsaufgabe vom Lehrstuhl gerechnet, dort hatte ich keine Probleme, aber hier komme ich einfach nicht weiter.
VG Taja

Zum Vergrößern anklicken....

äh, bei mir ist der Anfangsfluss in der Aufgabenstellung, Teil a), vorgegeben. Zählt man da die Flussstärken, die von den zwei Quellen W1 und W2 ausgehen, zusammen, kommt man auf 6 + 1 + 2 + 7 = 16. Entspricht der Summe der Flussstärken, die in der Senke B münden, also 0 + 10 +6 = 16...

Zur Klarstellung: für den Ford-Fulkerson-Algorithmus muss man lediglich mit irgendeinem beliebigen, zulässigen(!) Fluss beginnen. Nur für diese Übungsaufgabe sollte man zwingend mit dem vorgegebenen Anfangsfluss starten, um auf die selbe oder eine ähnliche Markierungsreihenfolge zu kommen. Das Endergebnis sollte aber stets das selbe sein 😉

An welcher Stelle stimmen denn deine Ergebnisse nicht mehr? Sonst wird das Helfen etwas schwierig...

Der Anfang lautet so: W1 wird als Quelle mit (+,∞) markiert, ebenso W2. Das besagt lediglich, dass es sich um Quellen handelt, die von keinem anderen Knoten gespeist werden und unendliche Kapazitäten besitzen.

Geht man nun systematisch vor, überprüft man zunächst den markierten Knoten W1. Dazu sind zunächst alle unmarkierten Nachfolger und Vorgänger von W1 zu ermitteln, hier P1 und P2. Zu untersuchen ist nun, ob von W1 nach P1 und von W1 nach P2 der Fluss erhöht werden kann. Erst, wenn beide Alternativen überprüft sind, darf man sich einen neuen Knoten aussuchen... (das habe ich immer falsch gemacht)
W1P1: Anfangsfluss der Stärke 6 (Abb. 4.14); Maximalfluss der Stärke 8 möglich (Abb. 4.13); keine Beschränkung seitens W1. Deswegen wird P1 mit der Marke (W1+, 2) versehen. Das bedeutet, der Fluss von W1 nach P1 kann um 8-6=2 Einheiten erhöht werden.
W1P2: Anfangsfluss der Stärke 1; Maximalfluss der Stärke 5 möglich; keine Beschränkung seitens W1. Deswegen wird P2 mit der Marke (W1+, 4) versehen. Der Fluss von W1 nach P2 kann um 5-1=4 Einheiten erhöht werden.
Nachdem nun alle(!) unmarkierten Nachfolger und Vorgänger (es gab keine) von W1 markiert worden sind, darf man sich einen neuen Knoten zur Überprüfung aussuchen.

Man kann nun frei aus W2,P1,P2 wählen - aber erst jetzt! (s.o.)
Wir gehen einfach mal der Reihe nach vor und wählen P1. Zunächst wieder alle unmarkierten Nachfolger und Vorgänger ermitteln. W1 ist zwar Vorgänger, aber bereits markiert, P2 ist Nachfolger, aber ebenfalls schon markiert, bleibt nur noch P3 als unmarkierter Nachfolger. Von P1 nach P3 fließen bereits 5 Einheiten, was der Maximalkapazität dieses Pfeils entspricht. Der Fluss von P1 nach P3 kann also nicht weiter erhöht werden, eine Markierung des Knotens P3 ist jetzt nicht möglich. Damit ist P1 vollständig überprüft, ohne dass eine Markierung gesetzt wurde. Es verbleiben noch zwei markiert, noch nicht überprüfte Knoten übrig: W2, P2.

Wir wählen P2. Vorgänger W1, W2 und P1 sind bereits markiert und daher uninteressant. Die Nachfolger P3 und P4 sind unmarkiert und müssen beide(!, s.o.) untersucht werden.
P2P3: aktueller Fluss = 0; max. = 3; P2 mit 4 markiert; P3 erhält die Markierung (P2+, 3). Das bedeutet, der Fluss von P2 nach P3 kann um 3 Einheiten erhöht werden.
P2P4: keine Erhöhung möglich, da max. bereits erreicht.
Überprüfung von P2 abgeschlossen.
Markierte, noch zu überprüfende Knoten: W2,P3. Die Musterlösung hat mit W2 weitergemacht und von dort aus Knoten P5 markiert. Dann P5 überprüft und von dort aus P4 markiert. Das kann man aber getrost überspringen, da man zwischen W2 und P3 frei wählen darf.
Überprüfung von P3: Vorgänger P1, P2 bereits markiert und daher uninteressant. Nachfolger B, P4.
P3B: aktuell 0; max. 7; P3 nur mit 3 markiert; d.h. B erhält die Marke (P3+, 3). Das bedeutet, zwar könnte theoretisch der Fluss von P3 nach B um 7 erhöht werden, in P3 stehen aber bei dieser Flusserhöhung maximal 3 zusätzliche Einheiten zur Verfügung...

Da nun die Senke B markiert ist, bricht der Markierungsprozess ab. Die Flusserhöhung wird von B rückwärts anhand der Markierungen vorgenommen.
B hat die Marke (P3+, 3). P3 hat die Marke (P2+, 3). P2 hat die Marke (W1+, 3). D.h. der Fluss kann von W1 über P2, P3 nach B um 3 Einheiten erhöht werden. 🙂

Erste Iteration beendet, es folgt die zweite.... 🙁

Hoffe, das war halbwegs verständlich. Zu beachten ist noch, dass bei der Markierung eines Vorgängers die Marke mit einem Minus versehen wird, was für eine Flussverringerung auf dem entsprechenden Pfeil steht (um so den Gesamtfluss erhöhen zu können).

Oh Mann...
Ich hätte vielleicht bis zu a) lesen sollen🙁.
Ich habe nämlich sofort mit Abb. 4.13 begonnen, ohne weiterzulesen.
Werde jetzt nochmal die Aufgabe versuchen, wenn ich's immer noch nicht haben sollte, dann melde ich mich wieder.
Trotzdem Danke!
VG Taja