Netzwerkflüsse |
| 28.08.2009, 23:28 | plizzz | Auf diesen Beitrag antworten » | ||
| Netzwerkflüsse ich schaue mir gerade das Thema Netzwerkflüsse an und bin jetzt da angekommen, wo von "augmentierenden Wegen" gesprochen wird. Und ich muss sagen, dass ich mir so gar nichts darunter vorstellen kann. Also Fragen: Warum ist der Fluss größer, wenn ich ihn über einen bestimmten Weg augmentiert habe? Wo ist der Sinn von den gegenläufigen Kanten? Sorry, dass da jetzt etwas derart Unkonkretes steht, aber ich schaffe es irgendwie nicht, Fuß in dem Thema zu fassen. Vielen Dank und freundliche Grüße, plizzz |
||||
| 30.08.2009, 11:13 | Abakus | Auf diesen Beitrag antworten » | ||
| RE: Netzwerkflüsse Da müsstest du ggf. die genauen Definitionen angeben, dann lässt sich das besser diskutieren. Sonst ist das eine Fahrt im Nebel. Grüße Abakus 
|
||||
| 31.08.2009, 12:05 | plizzz | Auf diesen Beitrag antworten » | ||
Also es geht mir in erster Linie um den Ford-Fulkerson Algorithmus. Dazu mal die Definitionen von Wikipedia: http://de.wikipedia.org/wiki/Algorithmus...d_und_Fulkerson So ein augmentierender Weg ist für mich ja noch ganz logisch, solange nur Kanten benutzt werden, die es schon im Graphen gibt. Das bedeutet für mich anschaulich, dass ich sozusagen noch mehr durch das Netzwerk durchschicken könnte, was dann über irgendeinen Weg (genau den augmentierenden Weg) zum Ziel kommt. Und dass man dann auf diesem Weg den Fluss um das Minimum der Kapazitäten des Restgraphen erhöhen kann, ohne die Flusseigenschaften zu verletzen, ist mir auch klar. Allerdings ist mir völlig unklar, was diese gegenläufigen Kanten da zu suchen haben. Der Sinn erschließt sich mir einfach nicht. Und an dieser Stelle hänge ich grade. |
||||
| 31.08.2009, 23:45 | Abakus | Auf diesen Beitrag antworten » | ||
Du solltest dir eine algorithmische Version des Algorithmus besorgen: dieser arbeitet mit Markierungen der Knoten. Markiert wird sukzessive, angefangen bei der Quelle. Untersucht werden dabei in jedem Markierungs-Schritt alle (noch nicht markierten) Nachfolger und Vorgänger eines schon markierten Knotens. Erreicht man auf diese Art die Senke, hat man einen flussvergrößernden Weg gefunden und es beginnt die nächste Iterationsrunde. Lässt sich kein weiterer Knoten erreichen, bricht das Verfahren ab. Wird nun ein Knoten markiert, merkt man sich, wie dieser erreicht wurde (also ob er Vorgänger oder Nachfolger welches Knotens ist) und auch wie groß der jeweilige, zusätzlich dahin mögliche Fluss ist. Deine gegenläufigen Kanten sind wohl (?) die Vorgänger bei diesem Markierungsprozess. Das Ganze lässt sich nur schwerfällig beschreiben; am Besten verstehst du es mit dem ausformulierten Algorithmus und einem Beispiel. Grüße Abakus
|
||||
|
|