Programmieraufgabe WS14/15: garantierter saturierter Schnitt

Moderator: Effiziente Graphenalgorithmen

Mathematics
Erstie
Erstie
Beiträge: 17
Registriert: 23. Sep 2013 12:12

Programmieraufgabe WS14/15: garantierter saturierter Schnitt

Beitrag von Mathematics » 13. Jan 2015 12:40

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
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Programmieraufgabe WS14/15: garantierter saturierter Sch

Beitrag von Prof. Karsten Weihe » 16. Jan 2015 16:23

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)?
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
Erstie
Erstie
Beiträge: 17
Registriert: 23. Sep 2013 12:12

Re: Programmieraufgabe WS14/15: garantierter saturierter Sch

Beitrag von Mathematics » 17. Jan 2015 10:58

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...

Antworten

Zurück zu „Effiziente Graphenalgorithmen“