Diskussion:Algorithmus von Ford und Fulkerson

Verständlichkeit

Beitrag ist vollkommen unverständlich. (nicht signierter Beitrag von ‎141.3.48.123 (Diskussion | Beiträge) 11:18, 5. Jul. 2005)

Sehe ich auch so. Habe mal den Überarbeiten-Baustein eingesetzt.--JFKCom 20:21, 5. Aug 2006 (CEST)

Mir bleibt die Bemerkung zu irrationale Kapazitäten etwas rätselhaft: "Für irrationale Kapazitäten konvergiert der Algorithmus mitunter nicht oder nicht unbedingt gegen den richtigen Wert." Der Fluss von q nach s wird in jedem Schritt erhöht und ist nach oben beschränkt (andernfalls gäbe es überhaupt keinen Maximal-Fluss). Monotone beschränkte Folgen sind konvergent. Also konvergiert der Algorithmus. Ob es tatsächlich möglich ist, dass der Algorithmus (in einem endlichen Graphen) nicht nach endlich vielen Schritten terminiert und dann eventuell sogar noch gegen einen falschen Grenzwert konvergiert, kann ich im Moment nicht überblicken. -- StS. (nicht signierter Beitrag von 141.35.15.80 (Diskussion) 07:48, 14. Dez. 2006‎)

"für irrationale...": Hier hilft googlen mit "ford fulkerson irrational Uri Zwick" -> z.b. http://www.cs.uiuc.edu/class/sp07/cs473g/lectures/14-maxflowalgs.pdf

Habe den ganzen Artikel überarbeitet (hat Spass gemacht, war aber ziemlich anstrengend) - hoffentlich ist's jetzt verständlich. Obwohl sicher noch ein paar Verbesserungen möglich sind, habe ich den Überarbeiten-Baustein schon mal entfernt. Wickie1681 01:10, 6. Apr. 2008 (CEST)

Ich würde mir eine ergänzende "Erklärung in deutscher Sprache" wünschen, die weitgehend auf "Formelaussagen/-erklärungen" verzichtet. Die "Formelerklärung" kann ruhig stehen bleiben, aber ich hätte es gerne "nochmal auf deutsch". Siehe auch :http://de.wikipedia.org/wiki/Wikipedia:Auskunft#Algorithmus_von_Ford_Fulkerson --Junior zanett1 17:41, 13. Feb. 2012 (CET)

Hallo Junior zanett1! Beim Schreiben mathematischer Texte gilt es, ein gesundes Mittelmaß von Formeln und natürlicher Sprache zu finden. Wenn man auf eines von beiden verzichtet, ist der Text in der Regel nur extrem schwer verständlich. An einfaches Beispiel mit Schulmathematik wäre z.B., statt „$f(x)=x^{2}+3x$“ zu schreiben: „Sei $f$ die Funktion, die jede Zahl auf die Summe des Produktes von ihr mit sich selbst mit dem Dreifachen von ihr abbildet.“ Wenn man noch $f(x)={\tfrac {x^{2}+3x+1,7}{x^{3}+\pi }}$ ohne Formeln ausdrücken wollte, wird es noch schlimmer. Hier ist denke ich klar, dass die Formelschreibweise einfacher zu verstehen ist.

Der Text des Artikels im Abschnitt Der Algorithmus besteht eigentlich nur aus deutschen Sätzen, in denen Formeln vorkommen. Manches, z.B. die Definition der Residualkapazitäten $u_{f}$, ist erst in fast formelfreier natürlicher Sprache erklärt und dahinter als Formel wiederholt.

Es wäre hilfreich, wenn Du sagen könntest, welche Stellen genau Du nicht verstehst, damit man überlegen könnte, was genau man ändern sollte. Ich wäre beeindruckt, wenn jemand den Text komplett formelfrei in solcher Weise aufschreiben könnte, dass man ihn noch gut verstehen kann. MfG Stefan Knauf 16:28, 14. Feb. 2012 (CET)

1. Es wäre ein Anwendungsbeispiel aus der Praxis ganz hilfreich, wie z.B. ein Schienennetz oder ein Datennetz. Mir erschließt sich der Zweck des Algorithmus nicht ganz. Warum misst man die Kapazität? Die steht doch an den Kanten? Des weiteren wird auch die Aussage Maximaler Schnitt=Minimaler Fluss nicht behandelt. (oder andersrum, bin mir nicht mehr ganz sicher)

2.

    *Kapazitätsbeschränkung: Für jede Kante $e$ ist $0\leq f(e)\leq u(e)$.

f(e) ist größer/gleich 0 ist kleiner/gleich u(e)? Ich denke u(e) ist die Kapazität? Die Kapazität ist kleiner/gleich der Kapazität? Was ist überhaupt f(e)? Wird vorher nirgends erklärt.

3. Was ist eine Rückkante? Das eine Rückkante durch ${\overleftarrow {e}}=(w,v)$. beschrieben wird, hilft mir leider wenig.

4. Was ist ein flussvergrößernder Pfad?

5. Was ist der Unterschied zwischen einer Kapazität und einer Residualkapazität?

6. Dieser Abschnitt ist mir leider vollkommen unverständlich. Was ist E(W) z.B.? Es wäre ganz praktisch rechts daneben jeweils zu schreiben, was passiert.

# Solange es im Residualgraphen $G_{f}$ einen Weg von $s$ nach $t$ gibt, bestimme einen solchen Weg $W$ und tue:

1. Bestimme $\gamma :=\min\{u_{f}(e)\mid e\in E(W)\}$.

   Für alle $e\in E(W)\cap E(G)$ setze: $f(e):=f(e)+\gamma$.

   Für alle ${\overleftarrow {e}}\in E(W)\setminus E(G)$ setze für die zugehörige Hinkante $e$: $f(e):=f(e)-\gamma$.--Junior zanett1 18:23, 14. Feb. 2012 (CET)

Hallo Junior zanett1! Der Algorithmus ist einer zur Lösung eines abstrakten Problems, nämlich dem, in einem „Netzwerk“ einen „maximalen Fluss“ zu finden. „Netzwerk“ und „Fluss“ sind hier abstrakte mathematische Begriffe, die zwar etwas mit der umgangssprachlichen Bedeutung zu tun haben, aber nicht mit ihnen verwechselt werden dürfen. Was die Begriffe genauer bedeuten, ist im Artikel Flüsse und Schnitte in Netzwerken behandelt.

Ein konkretes Beispiel für den Algorithmus steht im Abschnitt Beispiel. Dieses Beispiel ist auch so abstrakt wie das Problem, das der Algorithmus bearbeitet. Die praktisch relevanten Netzwerke (z.B. Eisenbahn- oder Telefonnetze) sind so groß, dass sie nicht zum Vorrechnen taugen. Netzwerke, an denen man gut ein Beispiel vorrechnen kann, sind naturgemäß so einfach, dass man auch gut ohne komplizierte Algorithmen mit ihnen klarkäme.

Für den Algorithmus muss man natürlich wissen, welche Kapazitäten die Kanten haben. Das Messen der Kapazitäten ist jedoch kein Bestandteil des Algorithmus.

Der Aussage, dass der Wert eines maximalen Flusses dem eines minimalen Schnittes entspricht, ist der Artikel Max-Flow-Min-Cut-Theorem gewidmet.

In der Zeile des Artikels über der von Dir zitierten Zeile mit „$0\leq f(e)\leq u(e)$“ ist angegeben, dass $f$ den Fluss bezeichnet. $f(e)$ ist der Flusswert auf der Kante $e$. Die Aussage „$0\leq f(e)\leq u(e)$“ bedeutet dann, dass über die Kante $e$ mindestens nichts und höchstens so viel fließt, wie die Kapazität der Kante ist.

Rückkanten sind einfach Zusatzkanten – von denen kommt für jede Kante des Netzwerks, über die mehr als nichts fließt, eine in den Restegraphen (im Artikel meist „Residualgraph“ genannt). Die Beschreibung ${\overleftarrow {e}}=(w,v)$ besagt, dass die Rückkante ${\overleftarrow {e}}$ am Knoten $w$ beginnt und zum Knoten $v$ führt.

Der Begriff „flussvergrößernder Pfad“ kommt in der Beschreibung im Absatz Der Algorithmus zwar nicht vor, aber damit ist einfach ein Pfad im Restegraphen gemeint.

Der Unterschied zwischen der Kapazität und der Residualkapazität (Restkapazität) ist, dass die Kapazität angibt, wie viel insgesamt über die Kante fließen kann, und die Restkapazität, wie viel noch zusätzlich zu dem, was schon über die Kante fließt, drüberfließen könnte.

$E(W)$ bezeichnet die Menge der Kanten, die in $W$ vorkommen. MfG Stefan Knauf 19:55, 14. Feb. 2012 (CET)

1:Netzwerke, an denen man gut ein Beispiel vorrechnen kann, sind naturgemäß so einfach, dass man auch gut ohne komplizierte Algorithmen mit ihnen klarkäme.

Es würde mir trotzdem helfen, da abstraktes Denken nicht unbedingt meine Stärke ist. Ich bin da mehr so der Praktiker, der erfolgreiches "Learning-by-doing" betreibt.

2.:Rückkanten sind einfach Zusatzkanten – von denen kommt für jede Kante des Netzwerks, über die mehr als nichts fließt, eine in den Restegraphen (im Artikel meist „Residualgraph“ genannt).

Also ist die Definition von Rückkanten, dass sie im Pfad von s nach q fließen (von der Senke zur Quelle fließen)?

3.:Der Begriff „flussvergrößernder Pfad“ kommt in der Beschreibung im Absatz Der Algorithmus zwar nicht vor, aber damit ist einfach ein Pfad im Restegraphen gemeint.

Zum Verständnis des FF-Algorithmus halte ich es für notwendig, dass man die Aussage "Er sucht sukzessiv nach flussvergrößernden Pfaden im Residualgraphen (Restnetz)" versteht. Dazu müsste ich erstmal wissen, was ein „flussvergrößernder Pfad“ ist. Kann jeder Pfad von q nach s umgehkehrt im Residualgraph ein „flussvergrößernder Pfad“ sein oder gibt es zur Bestimmung eines „flussvergrößernder Pfades“ Einschuss-/Ausschlusskriterien? Bzw. wenn jeder Pfad ein flussvergrößernder Pfad sein kann und ein Fluss genau dann maximal ist, wenn es keinen vergrößernde Pfade mehr gibt, mit welchem Pfad fängt man dann an, welcher Pfad ist dann (noch) flussvergörßernd(er) zum ersten "Flussvergrößer" anzusehen und wann weis man, dass man fertig ist?--Junior zanett1 03:40, 16. Feb. 2012 (CET)

Alle s-t-Pfade im Residualgraphen sind Flussverbessernd. (So ist das Residualnetz gerade gebaut.) Falls es mehrere solcher Pfade gibt, sagt F&F nichts darüber aus, welcher zu wählen ist, Er nimmt den Erstbesten. Das ist auch der Grund, weshalb F&F bei irrationalen Kantengewichten nicht notwendigerweise terminiert. Fertig ist man, wenn ein Suchlauf das Ergebnis liefert, dass es keine weiteren s-t-Pfade im Residualnetzwerk gibt.--goiken 03:48, 16. Feb. 2012 (CET)

4.Kann man sagen, dass mit dem FF-Algorithmus der Flaschenhals eines Transportnetzwerkes ermittelt wird?--Junior zanett1 04:31, 16. Feb. 2012 (CET)

Zur Anwendung in der Chemie kann ich nichts sagen, aber zu einem maximalen Fluss gibt es immer einen gleichwertigen minimalen Schnitt. F&F liefert einen maximalen Fluss. Die Zusammenhangskomponente der Quelle in dem Residualnetzwerk zu diesem maximalen Fluss definiert mit ihrem Knotenkomplement einen minimalen Schnitt. Manchmal kann man sich diesen Schnitt sinnvoll mit der Vorstellung eines Flaschenhalses veranschaulichen. --goiken 04:51, 16. Feb. 2012 (CET)

Hallo Junior zanett1! Ich würde nicht sagen, dass die Kanten „fließen“. Die Kanten sind sozusagen Leitungen, durch die etwas „fließt“. Und die Rückkanten sind rein gedachte Objekte, die man nur „benutzt“, um den Algorithmus besser erklären zu können. Du solltest versuchen, das Beispiel im Artikel durchzugehen. Die Rückkanten sind da die roten Kanten.

Die „Fähigkeit“, abstrakt zu denken, ist reine Übungssache. Wenn man sich einmal daran gewöhnt hat, ist es auch einfacher, weil dabei die ganzen eigentlich unwichtigen Realitätsbezüge ausgeblendet werden. Ob man Datenleitungen, Eisenbahnnetze oder Rohrleitungen betrachtet, ist für das Konzept der maximalen Flüsse und minimalen Schnitte unwichtig. Abstrahieren bedeutet quasi, alles Unwichtige wegzulassen.

Ich denke, Deine anderen Fragen hat goiken schon beantwortet. MfG Stefan Knauf 19:15, 17. Feb. 2012 (CET)

Algorithmus

1. müsste P nicht ein Pfad anstatt eines Weges sein, also zykelfrei? (nicht signierter Beitrag von Head (Diskussion | Beiträge) 00:30, 5. Aug. 2005‎)

   Das ist korrekt. Sollte eigentlich Pfad heißen (nicht signierter Beitrag von 128.131.224.241 (Diskussion) 09:56, 28. Okt. 2006‎)

2. muss N nicht mit G initialisiert werden? (nicht signierter Beitrag von Head (Diskussion | Beiträge) 00:30, 5. Aug. 2005‎)

   Denke schon, bin mir aber nicht 100% sicher.(nicht signierter Beitrag von 128.131.224.241 (Diskussion) 09:56, 28. Okt. 2006‎)

Ja, N sollte zu Beginn mit G initialisiert werden. Ob man allerdings einen Pfad oder nur einen Weg hinzunimmt, ist dem Algorithmus egal. In einer effizienten Implementierung wird es wohl immer auf einen Pfad hinauslaufen, um "unproduktive" Zykel zu vermeiden. (nicht signierter Beitrag von 141.35.15.80 (Diskussion) 07:21, 14. Dez. 2006‎)

Fehlerhafter Algorithmus

Der Algorithmus ist so wie er momentan angegeben ist fehlerhaft. man kann sehr einfache gegenbeispiele konsturieren, in denen dieser Algorithmus nicht zum maximalen Fluss führt. Die Idee ist schon richtig, aber da gibt's schon noch ein paar Fälle zu beachten. (nicht signierter Beitrag von 129.70.24.99 (Diskussion) 15:49, 16. Feb. 2006‎)

Wie sollen denn diese Gegenbeispiele aussehen? OK, die Beschreibung des Algorithmus ist nicht sehr toll, man muss schon wissen, wie man mit Flüssen arbeitet, um das nachvollziehen zu können, aber einen Fehler sehe ich nicht. -- StS. (nicht signierter Beitrag von 141.35.15.80 (Diskussion) 07:22, 14. Dez. 2006‎)

was meiner meinung nach nicht stimmt:

"solange es einen Weg P von q nach s gibt" ... - es muss einen aufteigenden Pfad geben (flow(e) > 0 f.a. Kanten e, die auf diesem Pfad durchlaufen werden) - es muss irgendwo stehen, dass eine Kapazitätsfunktion existiert, die jeder Kante eine Kapazität cap(e) >= 0 zuweist - es muss irgendwo stehen, dass flow(e) <= cap(e) gelten muss

"erweitere Fluss mit einem Fluss über P" - dies ist für mich unverständlich. der fluss eines solchen netzwerks ist doch eine natürliche zahl? das ergebnis wird hier anders bestimmt soweit ich weiß

ausserdem fehlt vollkommen, dass, wenn man einen solchen aufsteigenden pfad nimmt, zu jeder kante e eine rückwärtskante ~e hinzukommt (falls nicht schon vorhanden), die dann als kapazität cap(~e)=flow(e) bekommt. d.h. man kann prinzipiell diese kante wieder rückwärts laufen (dies wirkt sich dann als negative zahl bei der aufsummierung in der schleife aus)

hmm vielleicht ist das alles schon irgendwo beschrieben und ich sehe es nur nicht, aber wie gesagt, meiner meinung nach fehlt hier noch so einiges, bis man anhand der beschreibung diesen algorithmus (a) versteht und (b) anwenden könnte ... (nicht signierter Beitrag von 83.236.62.173 (Diskussion) 05:11, 18. Feb. 2007‎) 83.236.62.173

jetzt ist der Algorithmus wohl korrekt beschrieben, aber zur Verständlichkeit fehlt immer noch einiges ... --Wickie1681 15:25, 31. Mär. 2008 (CEST)

Anmerkungen Algorithmus

Residualgraph wird zweimal verlinkt allerdings find ich die Erklärung hier verständlicher, vieleicht kann man dass mal zusammenfügen. Kann ich auch irgendwann mal machen wenn ich Zeit hab.--Schönen Gruß "Wohingenau" 23:00, 21. Mär. 2010 (CET)

Hallo Wohingenau! Hm, ist die Erklärung des Residualgraphen in diesem Artikel und unter Flüsse und Schnitte in Netzwerken#Residualnetzwerk nicht fast wörtlich dieselbe oder übersehe ich da was? Was gefällt Dir denn an der Erklärung hier besser? MfG Stefan Knauf 22:43, 27. Mär. 2010 (CET)

Ja du hast recht die sind fast gleich. Der einzige Unterschied sind ein, zwei Formeln, die aber mir schon das Verständnis erleichtert haben. Ich wollt eigentlich eher anmerken, dass man nicht einfach hier den Absatz löscht und auf den Artikel verlinkt, sonder vorher lieber guckt, ob man dass übertragen kann. Ob man es überhaupt hier löschen sollte ist dann nochmal eine andere Frage....--Schönen Gruß "Wohingenau" 19:53, 3. Apr. 2010 (CEST)

Beispiel und Bilder

Ich habe einige Fragen zu den Beispielen und den Bildern

• Warum werden in den Bildern der Beispiele q und s anstatt s (source) und t (target) verwendet, wie es in der Literatur üblich ist, und auch davor in diesem Abschnitt korrekt mit s-t-Fluss beschrieben wird?

• Wozu dient dem Beispiel das inhaltlich gleiche Bild mit der Unterschrift "Ein maximaler Fluss im Beispielnetzwerk"? Könnte meiner Meinung nach heraus genommen werden.

• Hat es einen bestimmten Grund, dass das Beispiel mit Punkt und Klammern nummeriert ist? Normalerweise sollte man sich auf ein Zeichen bei Nummerierungen beschränken, mein Vorschlag: 1.1, 1.2...

• Das Beispiel sollte eigentlich Verständlichkeit für den Ablauf des Algorithmus schaffen. Sollte man nicht einen Teil der Formelzeichen in Prosa überführen, um die Leserlichkeit zu gewährleisten?

--Tfr.didi (Diskussion) 15:42, 3. Jan. 2013 (CET)

Hallo Tfr.didi! Der Grund, dass in der Beispielrechnung $q$ und $s$ statt $s$ und $t$ verwendet wird, liegt darin, dass in den Bildern zur Rechnung die Buchstaben $q$ und $s$ (für „Quelle“ und „Senke“) stehen und bisher keiner Lust hatte, neue Bilder zu malen.

Das Bild mit der Unterschrift „Ein maximaler Fluss im Beispielnetzwerk“ dient dazu, den maximalen Fluss $f_{4}$ explizit bildlich darzustellen. Ohne das Bild stünde der Fluss zwar auch da, aber er wäre nicht aufgemalt.

Wenn mit Buchstaben nummeriert wird, sind Klammern um die Buchstaben nicht ungewöhnlich. Mich stören sie da nicht.

Und ich denke, dass Formeln wie $f_{4}((q,u))=4$ nicht schwieriger zu lesen sind als die gleichbedeutende Prosa „Der Wert des Flusses $f_{4}$ auf der Kante von $q$ nach $u$ [bzw. der Kante $(q,u)$] ist 4.“ Die meisten Leute sind sich zwar einig, dass man manche Sachen besser als Formeln und manche besser als Prosa ausdrückt, aber welche Sachen zu welchen gehören, darüber einigt man sich wohl eher selten... MfG Stefan Knauf (Diskussion) 22:19, 14. Jan. 2013 (CET)

Lyrisches Beiwerk...

Hallo, Danke für diesen Artikel, vor allem das Beispiel hat sehr geholfen - habe soweit alles gecheckt...

Einen Satz könnte man vielleicht besser formulieren, Zitat:

"Man beachte: alle Rückwärtskanten im Residualgraph haben wieder dieselbe Residualkapazität, wie dem Wert des Flusses zwischen ihren beiden Knoten entspricht."

Vorschlag:

"Man beachte: Die Residualkapazitäten der Rückwärtskanten im Residualgraphen sind gleich der Werte der ihnen entsprechenden Kanten des Flusses."

Ich glaube, dass "wie" oben sollte ein "die" sein...

Oder einfach mathematisch darstellen...

Na ja, vielen Dank auf jeden Fall noch mal...

Gruß, David Kientopf

--Vege Tarier (Diskussion) 19:51, 16. Dez. 2016 (CET)

Hab' das jetzt einfach gemacht: d für w...

--Vege Tarier (Diskussion) 08:30, 23. Dez. 2016 (CET)