H5.5

burgi
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 115
Registriert: 15. Apr 2009 18:08
Wohnort: Ludwigshafen

H5.5

Beitrag von 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

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: H5.5

Beitrag von 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.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: H5.5

Beitrag von 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
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: H5.5

Beitrag von daniel_b »

//
Zuletzt geändert von daniel_b am 21. Mai 2009 02:40, insgesamt 1-mal geändert.

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: H5.5

Beitrag von daniel_b »

robert.n hat geschrieben: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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 115
Registriert: 15. Apr 2009 18:08
Wohnort: Ludwigshafen

Re: H5.5

Beitrag von burgi »

cormen nennt dies eine superquelle :)

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: H5.5

Beitrag von robert.n »

daniel_b hat geschrieben:
robert.n hat geschrieben: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! :mrgreen:

//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.
Zuletzt geändert von robert.n am 21. Mai 2009 11:35, insgesamt 1-mal geändert.

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: H5.5

Beitrag von daniel_b »

robert.n hat geschrieben:
daniel_b hat geschrieben:
robert.n hat geschrieben: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.
Zuletzt geändert von daniel_b am 21. Mai 2009 11:39, insgesamt 1-mal geändert.

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: H5.5

Beitrag von robert.n »

daniel_b hat geschrieben:
robert.n hat geschrieben:
daniel_b hat geschrieben: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
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: H5.5

Beitrag von daniel_b »

robert.n hat geschrieben: 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. :shock:

Benutzeravatar
Le_Coeur
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 135
Registriert: 18. Apr 2009 12:39
Kontaktdaten:

Re: H5.5

Beitrag von Le_Coeur »

Ich hab eine Frage zu dieser Aufgabe, z.b. es gibt folgender Graph (DATEIANHÄNGE)
test.jpg
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?

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: H5.5

Beitrag von 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.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

Benutzeravatar
Le_Coeur
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 135
Registriert: 18. Apr 2009 12:39
Kontaktdaten:

Re: H5.5

Beitrag von Le_Coeur »

bruse hat geschrieben: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
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: H5.5

Beitrag von robert.n »

daniel_b hat geschrieben:
robert.n hat geschrieben: 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. :shock:
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.
Le_Coeur hat geschrieben: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... :?:

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: H5.5

Beitrag von 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.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

Antworten

Zurück zu „Archiv“