Ford Fulkerson Kurseinheit 1 Beispiel 4.5 Seite 82

View all featured content
N

NERD

Dr Franke Ghostwriter
Ford Fulkerson KE1 Beispiel 4.5 Seite 82

Hallo,

ich habe versucht mir den Ford Fulkerson Algortihmus an Hand des Beispiels 4.5 KE 1 auf Seite 81/82 zu verinnerlichen. Der erste Iterationschritt ist mir noch klar, bei Iteration 2 hackt es dann: Ist (1+,3) bei Knoten 3 nun eine Erhöhung, oder Erniedrigung der Flusses um 3? Oder der tats Fluss (wovon ich mal ausgehe). Wieso fliessen dann nach Knoten 2 (3+,3). Oder das quasi die verwertbare Restkapazität? Ich komm einfach nicht drauf.

Danke für die Hilfe

Grüße
NERD
 
Nach Datum sortieren Nach Stimmen sortieren
Nerd,

die Markierung (1+, 3) bei Knoten 3 entstand, weil es möglich ist, von Knoten 1 aus 3 Einheiten mehr zum Knoten 3 zu transportieren als dies nach Iteration 1 der Fall war.

Die Markierungen musst du nach Abschluss der Iteration, also wenn der Knoten s = 6 markiert werden konnte, rückwärts lesen und den Fluss dann jeweils erhöhen.

Gruß,
Sabine.
 
Positive Stimme 0 Negative Stimme
Antworten
Oben