Kurs 852 - Übungsaufgabe 4.4

Kurs 852 - Übungsaufgabe 4.4

Frage zum Ford/Fulkerson:

Warum beträgt auf S.135 im 1.Iterationsschritt der Wert von Knoten B (P3+,3) ?
B könnte doch vom P3 maximal sieben vertragen (oberes Diagr. Seite 134) und hat derzeit noch 0 (unteres Diagr. Seite 134) !?

D.h. B (P3+,7) ?????:confused

Das Epsilon(B) berechnet sich nach Tabelle 4.1 als:

Epsilon(B) = min(Epsilon(P3), 7-0) = min(3,7) = 3

Von P3 nach B können zwar zusätzlich 7 fließen, in P3 hinein (von P2 kommend) aber nur zusätzlich 3. Von daher ist das Minimum dieser beiden Werte ausschlaggebend.

Ahh - stimmt !! Vielen Dank !

Da muß ich die Chance nutzen und gleich noch ne Frage loswerden, die vielleicht schwer zu verstehen ist:
Wieder auf Seite 135: In welcher Bearbeitungsreihenfolge gehe ich vor ?
a) Fülle ich zuerst den 1.Iterationsschritt für alle Knoten aus und bestimme dann einen (im Bild darunter fett gedruckt) Weg meiner Wahl.
oder
b) Bestimme ich vorher bereits einen Weg und ergänze die nicht auf dem Weg liegenden Knoten nur noch ?

O.k. das Ergebnis ist das Gleiche, aber wie geht man den praktischerweise vor ? Welchen Sinn haben die Markierung (und damit die Tabelle) überhaupt, wenn ich auf dem dargestellten Graphen die Ergebnisse viel besser sehe ?

Naja, ich gebe zu, das war mehr als eine Frage...

LG,
Evalotto

Bearbeitungsreihenfolge b), da sie für das MANUELLE Lösen sicher effizienter ist.

Einige der Algorithmen sind ja in einer sehr "DV-nahen" Weise beschrieben, wo gewisse Dinge im Gegensatz zum manuellen Lösen zusätzlich erforderlich sind. Der Computer hätte z. B. im Falle Ford-Fulkerson zumindest ncht direkt die Möglichkeit, Semiwege zwischen Quelle und Senke zu sehen. Also wird das entsprechende Rechenprogramm alle Knoten berechnen und erst am Ende feststellen können, welches in dem jeweiligen Iterationsschritt nun der flußvergrößernde Semiweg ist.

All right ! - Vielen Dank Loddar ! 🙂
Das gibt mir das beruhigende Gefühl, dass ich mich nicht gänzlich allein durch dieses gewöhnungsbedürftige Fach/Skrpit schlage muss !

LG,
Evalotto