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.
Programmieraufgabe WS14/15: garantierter saturierter Schnitt
Moderator: Effiziente Graphenalgorithmen
-
- Erstie
- Beiträge: 17
- Registriert: 23. Sep 2013 12:12
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Programmieraufgabe WS14/15: garantierter saturierter Sch
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.Mathematics hat geschrieben: 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)?
Geklärt?
KW
-
- Erstie
- Beiträge: 17
- Registriert: 23. Sep 2013 12:12
Re: Programmieraufgabe WS14/15: garantierter saturierter Sch
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...