Übungsaufgabe WS 2014/15

Moderator: Effiziente Graphenalgorithmen

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: Übungsaufgabe WS 2014/15

Beitrag von philipp_m » 18. Mär 2015 14:03

Danke für die rasche Antwort erst einmal. Nur kurz der Verständnis halber:
Prof. Karsten Weihe hat geschrieben:Auf anti-symmetrischen Graphen ist der Residualgraph einfacher zu implementieren, aber dann gibt es nicht unbedingt Pfade von s nach t, dieses Problem muss man nicht lösen, wenn der Graph symmetrisch ist. Bei einem symmetrischen Graphen müssten Sie so vorgehen: Für zwei Kanten (v,w) und (w,v), die residuale Kapazität von (v,w) wäre die Summe aus den aus (v,w) selbst und aus (w,v) induzierten residualen Kapazitäten: c(v,w)-f(v,w)+f(w,v). Klar
Die Berechnung wäre ja Prinzipiell die selbe wie bei anti-symmetrischen Graphen nur dass pro Knotenpaar durch die zwei Kanten dann jeweils bis zu zwei Hin- und Rückkanten entstehen würden, wobei man die residualen Kapazitäten der Kanten in die selbe Richtung dann einfach zusammenfasst, d.h. aufaddiert (der von ihnen genannte Schritt), korrekt?

Gruß
Philipp

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 18. Mär 2015 14:06

philipp_m hat geschrieben: Die Berechnung wäre ja Prinzipiell die selbe wie bei anti-symmetrischen Graphen nur dass pro Knotenpaar durch die zwei Kanten dann bis zu zwei Hin- und Rückkanten entstehen würden, wobei man die residualen Kapazitäten der Kanten in die selbe Richtung dann einfach zusammenfasst, d.h. aufaddiert (der von ihnen genannte Schritt), korrekt?
Yep.

KW

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: Übungsaufgabe WS 2014/15

Beitrag von philipp_m » 19. Mär 2015 04:41

Noch eine kurze Frage zur Visualisierung: Was muss genau beim Graphen erkennbar sein? Müssen Hin- und Rückkante voneinander getrennt sein (überlagern sich bei mir nämlich)? Sollen u und f für jede Hin- und Rückkante immer ersichtlich sein (d.h. bei einer kombinierten Hin- und Rückkante wären das vier Werte)?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 19. Mär 2015 06:06

philipp_m hat geschrieben:Noch eine kurze Frage zur Visualisierung: Was muss genau beim Graphen erkennbar sein? Müssen Hin- und Rückkante voneinander getrennt sein (überlagern sich bei mir nämlich)? Sollen u und f für jede Hin- und Rückkante immer ersichtlich sein (d.h. bei einer kombinierten Hin- und Rückkante wären das vier Werte)?
die numerischen Werte müssen nicht unbedingt erkennbar sein. Erkennbar muss als Minimum sein, was gerade passiert, also welcher Pfad gerade "dran" ist und wo schon Fluss drauf ist.

KW

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: Übungsaufgabe WS 2014/15

Beitrag von philipp_m » 20. Mär 2015 04:33

Jeder Algorithmus wird auf jede Instanz angewandt, und jede Nichtübereinstimmung der von den einzelnen Algorithmen berechneten Flusswerte wird für die Fehlersuche geeignet mitprotokolliert.
Hierbei ist nur der Gesamtfluss durch den Graphen gemeint, oder? Die Flusswerte der einzelnen Kanten können ja bei verschiedenen Algorithmen problemlos voneinander abweichen.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 20. Mär 2015 07:17

philipp_m hat geschrieben:
Jeder Algorithmus wird auf jede Instanz angewandt, und jede Nichtübereinstimmung der von den einzelnen Algorithmen berechneten Flusswerte wird für die Fehlersuche geeignet mitprotokolliert.
Hierbei ist nur der Gesamtfluss durch den Graphen gemeint, oder? Die Flusswerte der einzelnen Kanten können ja bei verschiedenen Algorithmen problemlos voneinander abweichen.
Yep.

KW

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: Übungsaufgabe WS 2014/15

Beitrag von philipp_m » 20. Mär 2015 20:00

Da bei mir ansonsten alles funktioniert, eine letzte Frage:

Bekommt man aus dem Preflow-Push-Algorithmus irgendwie direkt einen saturierten Schnitt? Wenn ja, wie? Ich konnte dazu im Wiki und in den Aufzeichnungen nichts finden, was mir groß weiterhilft und ich komme auch so direkt nicht darauf.

Ansonsten müsste man ja per DFS/BFS auf dem residualen Graphen von s aus ein S erzeugen können, das einen minimalen saturierten Schnitt ergibt. Dieser würde jedoch beim Preflow-Push-Algorithmus oftmals nur den Knoten s enthalten, da von diesem ausgehend ja alle Kanten saturiert werden und sich, falls die Summe der eingehenden Kapazitäten von t größer als die Summe der ausgehenden Kapazitäten von s ist, das Ganze auch nie ändern dürfte. Eventuell könnte man alle Kanten umdrehen und von t aus eine DFS/BFS für den maximalen saturierten Schnitt (genauer genommen: das Kompliment T zur Menge S des Schnittes) durchführen?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 21. Mär 2015 06:50

philipp_m hat geschrieben: Bekommt man aus dem Preflow-Push-Algorithmus irgendwie direkt einen saturierten Schnitt? Wenn ja, wie? Ich konnte dazu im Wiki und in den Aufzeichnungen nichts finden, was mir groß weiterhilft und ich komme auch so direkt nicht darauf.
Ist ja auch nicht Teil des Algorithmus selbst, sondern der Analyse: Wir wissen, wenn der Algo korrekt implementiert ist, dass dann immer ein saturierter Schnitt existiert, und daher auch, dass der (dann zulässige) Fluss bei Terminierung maximal ist.

philipp_m hat geschrieben: Ansonsten müsste man ja per DFS/BFS auf dem residualen Graphen von s aus ein S erzeugen können, das einen minimalen saturierten Schnitt ergibt. Dieser würde jedoch beim Preflow-Push-Algorithmus oftmals nur den Knoten s enthalten, da von diesem ausgehend ja alle Kanten saturiert werden und sich, falls die Summe der eingehenden Kapazitäten von t größer als die Summe der ausgehenden Kapazitäten von s ist, das Ganze auch nie ändern dürfte.
Wenn \((s,V\setminus\{s\})\) nicht der Schnitt minimaler Kapazität ist, muss der saturierte Schnitt irgendwann beginnen, "vorwärts zu wandern", nämlich genau in dem Moment, wenn erstmals Fluss zurück in \(s\) hinein gepusht wird.

KW

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: Übungsaufgabe WS 2014/15

Beitrag von philipp_m » 21. Mär 2015 15:57

Wenn \((s,V\setminus\{s\})\) nicht der Schnitt minimaler Kapazität ist, muss der saturierte Schnitt irgendwann beginnen, "vorwärts zu wandern", nämlich genau in dem Moment, wenn erstmals Fluss zurück in \(s\) hinein gepusht wird.
D.h. es ist korrekt, wenn der saturierte Schnitt im Falle, dass die Gesamtkapazität der aus s herausgehenden Kanten größer ist als die Gesamtkapazität der in t hineingehenden Kanten, einfach bei (s,V\s) bleibt? Im Zusammenhang mit ihrer zweiten Aussage langt es ja, dass ein solcher Schnitt existiert, um zu garantieren, dass bei Terminierung ein maximaler Fluss entstanden ist, so lange bei Terminierung zusätzlich alle arc weightings feasible flows sind.

Sollte das so korrekt sein, dürfte mein erster Ansatz mit der Suche aller erreichbaren Knoten im residualen Netzwerk dann wohl auch so passen und ich bin fertig. Also bedanke ich mich schon einmal für den Support :)

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 21. Mär 2015 16:46

philipp_m hat geschrieben: D.h. es ist korrekt, wenn der saturierte Schnitt im Falle, dass die Gesamtkapazität der aus s herausgehenden Kanten größer ist als die Gesamtkapazität der in t hineingehenden Kanten, einfach bei (s,V\s) bleibt?
Nein :!:

Der Schnitt minimaler Kapazität muss weder (s,V\s) noch (V\t,t) sein.

KW

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: Übungsaufgabe WS 2014/15

Beitrag von philipp_m » 22. Mär 2015 23:47

Prof. Karsten Weihe hat geschrieben:
philipp_m hat geschrieben: D.h. es ist korrekt, wenn der saturierte Schnitt im Falle, dass die Gesamtkapazität der aus s herausgehenden Kanten größer ist als die Gesamtkapazität der in t hineingehenden Kanten, einfach bei (s,V\s) bleibt?
Nein :!:

Der Schnitt minimaler Kapazität muss weder (s,V\s) noch (V\t,t) sein.

KW
Ich bin bei einer Google-Suche ironischerweise direkt auf https://www.d120.de/forum/viewtopic.php?f=312&t=31429 aus genau diesem Forum gestoßen (hatte zuvor nur auf englisch gesucht). Laut Ihrer letzten Aussage wäre doch dieser Thread dann auch nicht geklärt ("[...], dass über lange Zeit nur der Startknoten die Knotenmenge S bildet [...]")?

Im Beispiel auf Wikipedia (http://en.wikipedia.org/wiki/Max-flow_m ... xample.svg) ist sogar genau das der Fall, dass S nur aus s besteht, was in diesem Zusammenhang dann noch weiter zu meiner Verwirrung beiträgt.

Spezieller würde Ihre Aussage doch auch direkt bedeuten, dass es keinen saturierten Schnitt gibt, wenn V=[s,t] ist oder kein Pfad mit mindestens einer Kante zwischen zwei Knoten, die nicht s oder t sind, existiert. Das würde doch dann dem Max-Flow Min-Cut Theorem (http://wiki.algo.informatik.tu-darmstad ... ow_min-cut) widersprechen, da Aussage 1 und 3 auch für solche Graphen beweisbar wären (mit ensprechenden Flusswerten natürlich), Aussage 2 jedoch nicht gelten soll?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 23. Mär 2015 07:04

philipp_m hat geschrieben:Laut Ihrer letzten Aussage wäre doch dieser Thread dann auch nicht geklärt ("[...], dass über lange Zeit nur der Startknoten die Knotenmenge S bildet [...]")?
Was ist in jenem Thread ungeklärt?

Der Fragesteller hatte zumindest in seinem letzten Posting geschrieben, dass alles geklärt sei.

philipp_m hat geschrieben: Im Beispiel auf Wikipedia (http://en.wikipedia.org/wiki/Max-flow_m ... xample.svg) ist sogar genau das der Fall, dass S nur aus s besteht, was in diesem Zusammenhang dann noch weiter zu meiner Verwirrung beiträgt.
Bestätigt wieder meine generelle Meinung: Beispiele sind teuflisch. :twisted:

philipp_m hat geschrieben: Spezieller würde Ihre Aussage doch auch direkt bedeuten, dass es keinen saturierten Schnitt gibt, wenn V=[s,t] ist oder kein Pfad mit mindestens einer Kante zwischen zwei Knoten, die nicht s oder t sind, existiert.
Meine Aussage, die Sie zitieren, war, dass der saturierte Schnitt nicht unbedingt immer (s,V\s) oder (V\t,t) sein muss. In dem Einzelfall, den Sie nennen, ist (s,V\s)=(V\t,t) der einzige Schnitt und daher immer der saturierte. Das wird durch meine "nicht unbedingt"-Aussage nicht ausgeschlossen.

Der momentane Dissens zwischen uns scheint eher etwas mit Sprachlogik als mit saturierten Schnitten zu tun zu haben. Daraus, dass (s,V\s) nicht der saturierte Schnitt ist, haben Sie zuerst geschlossen, dass dann (V\t,t) der Schnitt sein muss, und daraus, dass es beide nicht unbedingt sein müssen, schließen sie jetzt, dass es in gewissen Fällen gar keinen gibt? Das sind beides keine validen Schlüsse.

KW

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: Übungsaufgabe WS 2014/15

Beitrag von philipp_m » 23. Mär 2015 14:06

Ich glaube, hier gibt es direkt zwei sprachbasierte Missverständnisse, wobei das eine aus dem anderen folgt:
Daraus, dass (s,V\s) nicht der saturierte Schnitt ist, haben Sie zuerst geschlossen, dass dann (V\t,t) der Schnitt sein muss
Nein, die Idee war bei mir, dass, wenn (s,V\s) ein saturierter Schnitt wäre und es noch einen saturierten Schnitt irgendwo im Graphen gäbe (schließt sich ja nicht aus, beispielsweise in einem großen Graphen, bei dem jede Kante saturiert ist, gäbe es häufig eine große Menge an validen saturierten Schnitten), man eventuell alle Kanten des Residualgraphen umdrehen könnte um den saturierten Schnitt mit maximalem S (und minimalem T) zu bekommen. Inzwischen ist mir jedoch auch klar, dass das im Sinne der Aufgabenstellung jedoch nicht gefordert ist, da es ja zum Beweis der Optimalität langt, wenn es in jedem Schritt (und damit auch im letzten Schritt) irgendeinen saturierten Schnitt gibt.
und daraus, dass es beide nicht unbedingt sein müssen, schließen sie jetzt, dass es in gewissen Fällen gar keinen gibt?
Hier liegt das Problem darin, dass Sie auf die Frage "D.h. es ist korrekt, wenn der saturierte Schnitt im Falle, dass die Gesamtkapazität der aus s herausgehenden Kanten größer ist als die Gesamtkapazität der in t hineingehenden Kanten, einfach bei (s,V\s) bleibt?" mit nein geantwortet haben (was auch korrekt ist ohne meine folgende Ergänzung, bei der ich dachte, ich hätte sie erwähnt, aber wohl dann doch vergessen hatte). Ich meinte jedoch den Fall, dass es auch einen gültigen Fluss von s nach t gibt, der der ausgehenden Gesamtkapazität aus s entspricht. In diesem Fall würde der Algorithmus nie nach s zurück pushen und damit wäre (s,V\s) immer der gefundene saturierte Schnitt.

Wegen des Neins kam ich dann auf die Fehlinterpretation Ihrer Aussage "Der Schnitt minimaler Kapazität muss weder (s,V\s) noch (V\t,t) sein." im englischen Sinne "The cut of minimal capacity must neither be (s,V\s) nor (V\t,t)." (was aber im deutschen eigentlich "darf weder" heißen würde da "must not" = "darf nicht"), was ja dann wiederum falsch gewesen wäre - daher mein letzter Post.

Noch kurz des Verständnisses halber: Mit ihrer Aussage meinten sie einfach nur, dass ein saturierter Schnitt sich auch irgendwo anders im Graph befinden kann (nicht muss!). Bildlich würde das bedeuten, dass der maximale Fluss von s nach t dann durch diesen Schnitt gedrosselt werden würde (auf den aufsummierten Fluss aller Kanten von S nach T). Korrekt?

Es tut mir Leid, dass ich das so missverstanden habe und Ihnen deshalb solche Umstände gemacht habe. Vielen Dank für Ihre Geduld.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 23. Mär 2015 14:46

philipp_m hat geschrieben: Wegen des Neins kam ich dann auf die Fehlinterpretation Ihrer Aussage "Der Schnitt minimaler Kapazität muss weder (s,V\s) noch (V\t,t) sein." im englischen Sinne "The cut of minimal capacity must neither be (s,V\s) nor (V\t,t)." (was aber im deutschen eigentlich "darf weder" heißen würde da "must not" = "darf nicht"), was ja dann wiederum falsch gewesen wäre - daher mein letzter Post.
Ich verstehe ehrlich gesagt immer weniger. Wieso übersetzen Sie eine Aussage von mir (inkorrekt) ins Englische und nehmen dann die (inkorrekte) englische Aussage als Basis Ihrer weiteren Überlegungen?

philipp_m hat geschrieben: Noch kurz des Verständnisses halber: Mit ihrer Aussage meinten sie einfach nur, dass ein saturierter Schnitt sich auch irgendwo anders im Graph befinden kann (nicht muss!). Bildlich würde das bedeuten, dass der maximale Fluss von s nach t dann durch diesen Schnitt gedrosselt werden würde (auf den aufsummierten Fluss aller Kanten von S nach T).
So kann man das bildlich sehen, denke ich.

Mir ist nicht ganz klar, ob Ihre Fragen jetzt beantwortet sind.

KW

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: Übungsaufgabe WS 2014/15

Beitrag von philipp_m » 23. Mär 2015 16:20

Prof. Karsten Weihe hat geschrieben:Ich verstehe ehrlich gesagt immer weniger. Wieso übersetzen Sie eine Aussage von mir (inkorrekt) ins Englische und nehmen dann die (inkorrekte) englische Aussage als Basis Ihrer weiteren Überlegungen?
Nicht bewusst, sondern unterbewusst ist mir wohl dieser Fehler unterlaufen, da es nur so für mich im Zusammenhang mit ihrem "Nein" zu diesem Zeitpunkt Sinn ergeben hat. Das Ganze ist etwas schwer zu erklären und macht natürlich für Ihre Veranstaltung auch keinen Sinn, war vor allem bei nicht muttersprachlich deutschen Dozenten in der Vergangenheit teils jedoch notwendig, um den Sinn der von diesen Dozenten ins Deutsche übersetzten Aussagen zu verstehen.

Kurzversion: Unterbewusster Denkfehler meinerseits.
So kann man das bildlich sehen, denke ich.

Mir ist nicht ganz klar, ob Ihre Fragen jetzt beantwortet sind.

KW
Ja, sind sie. Vielen Dank noch einmal.

Antworten

Zurück zu „Effiziente Graphenalgorithmen“