H5.5

[burgi]

moin,

bei H5.5 b soll man mittels Ford Fulkerson ein Flussproblem lösen, laut Aufgabenstellung entweder in kompakter Darstellung oder mittels Flussgraph und Restgraph. Letzteres ist mir soweit klar wie es ausschaut, mich würder jedoch diese komkate Schreibweise interessieren,da hab ich nicht der Hauch einer Ahnung was es sein sollte,

gruessle burgi

[bruse]

In der kompakten Schreibweise notiert man an einer Kante in der Form a/b aktuellen Fluss und Gesamtkapazität. Da ist der Restgraph (und die Rückkanten) dann natürlich nicht so offensichtlich aber dafür spart man sich Schreibarbeit.

[robert.n]

Andere Frage: Beim Flussproblem hat man ja normalerweise nur eine Quelle. Wenn ich jetzt eine "Hilfs-Quelle" hinzufüge und diese mit A, B und C verbinde, dann werden die Vorausüberweisungen von Herrn Feldfrau aber unter Umständen rückgängig gemacht... das deckt sich dann nicht mehr mit dem Ausgangsproblem. Wäre das so trotzdem in Ordnung?

[daniel_b]

//

[daniel_b]

Andere Frage: Beim Flussproblem hat man ja normalerweise nur eine Quelle. Wenn ich jetzt eine "Hilfs-Quelle" hinzufüge und diese mit A, B und C verbinde, dann werden die Vorausüberweisungen von Herrn Feldfrau aber unter Umständen rückgängig gemacht... das deckt sich dann nicht mehr mit dem Ausgangsproblem. Wäre das so trotzdem in Ordnung?

Ich glaub, du hast da nen Denkfehler. Wie willst du denn sonst A,B und C mit den Startwerten "initialisieren", wenn nicht über eine vorgeschaltete, einzelne Quelle? Da die Verbindung von der "Super-Quelle" zu A,B,C gerichtet ist, wird auch nix rückgängig gemacht.

[burgi]

cormen nennt dies eine superquelle

[robert.n]

Andere Frage: Beim Flussproblem hat man ja normalerweise nur eine Quelle. Wenn ich jetzt eine "Hilfs-Quelle" hinzufüge und diese mit A, B und C verbinde, dann werden die Vorausüberweisungen von Herrn Feldfrau aber unter Umständen rückgängig gemacht... das deckt sich dann nicht mehr mit dem Ausgangsproblem. Wäre das so trotzdem in Ordnung?

Ich glaub, du hast da nen Denkfehler. Wie willst du denn sonst A,B und C mit den Startwerten "initialisieren", wenn nicht über eine vorgeschaltete, einzelne Quelle? Da die Verbindung von der "Super-Quelle" zu A,B,C gerichtet ist, wird auch nix rückgängig gemacht.

Der Algorithmus könnte ja auf die Idee kommen den Fluss von S -> A zu reduzieren um mehr nach B oder C zu schicken.^^
Naja, dann werds ichs jetzt mal versuchen zu lösen *Angst vor der Schreibarbeit hat*....

//edit: Wenn ich das falsch verstanden habe, dass man den Graphen mehrmals zeichnen soll, dann bitte schnell *HAAAAAAAAAAAAAAALT* schreiben, danke!

//edit2: Ich hab jetzt aber als maximale Kapazitäten an die Kanten ausgehend von der Superquelle die Beträge der Vorausüberweisungen geschrieben. Sodass es zumindest ein bisschen an die Ausgangssituation herankommt. Hoffe das ist so in Ordnung.

[daniel_b]

Andere Frage: Beim Flussproblem hat man ja normalerweise nur eine Quelle. Wenn ich jetzt eine "Hilfs-Quelle" hinzufüge und diese mit A, B und C verbinde, dann werden die Vorausüberweisungen von Herrn Feldfrau aber unter Umständen rückgängig gemacht... das deckt sich dann nicht mehr mit dem Ausgangsproblem. Wäre das so trotzdem in Ordnung?

Ich glaub, du hast da nen Denkfehler. Wie willst du denn sonst A,B und C mit den Startwerten "initialisieren", wenn nicht über eine vorgeschaltete, einzelne Quelle? Da die Verbindung von der "Super-Quelle" zu A,B,C gerichtet ist, wird auch nix rückgängig gemacht.

Der Algorithmus könnte ja auf die Idee kommen den Fluss von S -> A zu reduzieren um mehr nach B oder C zu schicken.^^

Und wieso wäre das schlimm? In meiner Lösung geht sogar "0" über S->A. Die Gesamtkapazität des Netzwerks dahinter ( = Lösung) reicht nunmal nicht, um alle drei Wege vorn voll auszulasten. Welchen du vorne schließlich reduziert hast, is völlig egal.

// Laut meinem Tutor reicht die kompakte Darstellung, sprich ein Graph für alles.

[robert.n]

Ich glaub, du hast da nen Denkfehler. Wie willst du denn sonst A,B und C mit den Startwerten "initialisieren", wenn nicht über eine vorgeschaltete, einzelne Quelle? Da die Verbindung von der "Super-Quelle" zu A,B,C gerichtet ist, wird auch nix rückgängig gemacht.

Der Algorithmus könnte ja auf die Idee kommen den Fluss von S -> A zu reduzieren um mehr nach B oder C zu schicken.^^

Und wieso wäre das schlimm? In meiner Lösung geht sogar "0" über S->A. Die Gesamtkapazität des Netzwerks dahinter reicht nunmal nicht, um alle drei Wege vorn voll auszulasten. Welchen du reduzierst is völlig egal.

// Laut meinem Tutor reicht die kompakte Darstellung, sprich ein Graph für alles.

Guck dir bitte noch mein edit2 an... wenn man die Kapazitäten von der Superquelle aus aber mit unendlich belegt, dann könnte es bitter werden, weil dann über ein Konto mehr übertragen würde als überhaupt möglich (in dieser Ausgangssituation). Naja, ich sehe manchmal einfach Probleme die es nicht gibt. Danke.^^

"Es können maximal 3 Zitate ineinander verschachtelt werden." << wtf, muss ich da jetzt selbst alles rauspfriemeln was zu viel ist -.- vbulletin ftw!

[daniel_b]

Guck dir bitte noch mein edit2 an... wenn man die Kapazitäten von der Superquelle aus aber mit unendlich belegt, dann könnte es bitter werden,

Eigentlich sollte das sogar auch gehen. Die Maximalkapazität des Netzwerks bringt ja irgendwann ne Obergrenze mit sich, die sich bis zur Quelle "zurückstaut". Wenn ab A nur noch Betrag x fließen kann, ist eigentlich egal ob S->A am Ende x/16 oder x/\(\infty\) ist.

[Le_Coeur]

Ich hab eine Frage zu dieser Aufgabe, z.b. es gibt folgender Graph (DATEIANHÄNGE)

test.jpg (21.21 KiB) 744 mal betrachtet

Hier gibt's schon kein zunehmender Weg, d.h. dass ich hab schon mein maximaler Fluss - 10. Aber hier kann ich nicht solchen Kantenschnitt machen, damit f = c; -> weiderspruch:) Vllt gibt's bei mir Fehler hier?

[bruse]

Die Kante 2-3 und die Kante 5-S haben zusammen Kapazität 10. Andere Kanten von der linken in die rechte Komponente gibt es nicht.

[Le_Coeur]

Die Kante 2-3 und die Kante 5-S haben zusammen Kapazität 10. Andere Kanten von der linken in die rechte Komponente gibt es nicht.

D.h., dass ich Termin "Kantenschnitt" nicht richtig verstanden habe?:)
Und noch etwas, ist hier maximaler Fluss 10, oder 5? Denn ich hab ein Paar andere Definitionen von maximalen Fluss gefunden:)

[robert.n]

Guck dir bitte noch mein edit2 an... wenn man die Kapazitäten von der Superquelle aus aber mit unendlich belegt, dann könnte es bitter werden,

Eigentlich sollte das sogar auch gehen. Die Maximalkapazität des Netzwerks bringt ja irgendwann ne Obergrenze mit sich, die sich bis zur Quelle "zurückstaut". Wenn ab A nur noch Betrag x fließen kann, ist eigentlich egal ob S->A am Ende x/16 oder x/\(\infty\) ist.

Nein nein, das war einfach nur doof von mir.^^ Es ist schon gut so, wenn man S -> A / B / C jeweils mit der Vorausüberweisung als Kapazität versieht. Auch, wenn es mit diesen konkreten Werten vllt. gar keinen Unterschied gemacht hätte.

D.h., dass ich Termin "Kantenschnitt" nicht richtig verstanden habe?:)

Also nach bruses Post bin ich auch etwas verwirrt. Ich sehe da eine ganze Menge mehr mögliche Kantenschnitte und somit auch "linke" und "rechte" Komponenten...

[bruse]

Oha

Natürlich gibt es auch andere Kantenschnitte. Aber dieser hier hat Kapazität 10. Wir wissen, dass es auf keinen Fall mehr Fluss geben kann als die Kapazität beliebiger Schnitte (das sollte ja wohl auch intuitiv verständlich sein). Also ist 10 eine obere Grenze für den Fluss in diesem Graphen, denn es gibt einen Schnitt mit dieser Kapazität. Weiterhin gibt es einen Fluss f mit |f| = 10, diese Grenze wird also auch erreicht. Entsprechend ist 10 als Betrag für den Fluss in diesem Graphen maximal.

Ehrlich gesagt verstehe ich auch nicht, was es da nicht zu verstehen gibt. Natürlich gibt es auch andere Schnitte mit höherer Kapazität, aber der Satz, den wir hier anwenden, heißt doch sogar max-flow-min-cut-theorem! Stellt euch das doch mal bildlich vor: Wir haben 50km Autobahn, 10km Landstraße und dann wieder 10km Autobahn: Natürlich bestimmt die Landstraße den maximalen Verkehrsfluss, nicht die Autobahn (eine solche Situation gibt es übrigens bei meiner Heimatstadt ).

Übrigens solltet Ihr euch nochmal klar machen, was der Unterschied zwischen einem Fluss f und |f| für diesen Fluss ist. Ähnliche Probleme sind mir auch schon bei den Färbungen und der zugeordneten chromatischen Zahl aufgefallen...

Zu guter Letzt: Der Fluss in diesem Graphen ist 10, es kommen ja 10 Einheiten von der Quelle zur Senke.