Programmieraufgabe WS14/15: garantierter saturierter Schnitt

[Mathematics]

Hallo Herr Prof. Weihe,
in der Aufgabenstellung heißt es, dass in der graphischen Darstellung des Preflow-Push-Algorithmus u.a. stets der "zu jedem Zeitpunkt garantierte saturierte Schnitt" herausgehoben werden soll. Wie genau soll man diesen ausfindig machen (im gerichteten Fall mit Hin- und Rückkante wie in unserer Aufgabe)? Im Wiki kann ich dazu keinen Algorithmus finden und auch Google war bisher nicht sehr hilfreich.

[Prof. Karsten Weihe]

in der Aufgabenstellung heißt es, dass in der graphischen Darstellung des Preflow-Push-Algorithmus u.a. stets der "zu jedem Zeitpunkt garantierte saturierte Schnitt" herausgehoben werden soll. Wie genau soll man diesen ausfindig machen (im gerichteten Fall mit Hin- und Rückkante wie in unserer Aufgabe)?

Siehe Beweis zu Max-Flow Min-Cut Theorem: Sie suchen mit Graph Traversal alle Knoten, die von \(s\) aus über flusserhöhende Pfade erreichbar sind. Diese Knotenmenge ist \(S\) und dann ist \(T:=V\setminus S\). Konkret nutzt Graph Traversal zum Vorwärtsgehen also eine Kante in Vorwärtsrichtung, wenn der Flusswert kleiner als die Kapazität ist, und in Rückwärtsrichtung, wenn der Flusswert positiv ist.

Geklärt?

KW

[Mathematics]

Ja, damit ist alles geklärt. Vielen Dank! Tatsächlich hatte ich den Algorithmus sogar in dieser Art implementiert und mich gewundert, dass über lange Zeit nur der Startknoten die Knotenmenge S bildet, was durch die Initialisierung des Algorithmus eigentlich verständlich ist. Weitere Knoten können erst dann zu S hinzukommen, wenn wieder irgendwo etwas zu S zurückfließt. Je nach Auswahl des aktiven Knotens kann dies aber durchaus erst recht spät oder je nach Ausgangsgraph nie der Fall sein (wenn min-cut tatsächlich aus den aus s herausführenden Kanten besteht). Vielleicht hilft diese kurze Erläuterung noch jemandem...