Diskussion:Flüsse und Schnitte in Netzwerken

Reelle Zahlen

aus dem Bereich der nicht negativen reellen Zahlen zuweist.

Es gingen doch auch positive reelle Zahlen, oder? Wenn nichts fließen kann, kann die Kante doch gleich weggelassen werden. --zeno 18:16, 13. Feb 2004 (CET)

Man bedenke f(e,x,y) = -f(e,y,x) ; wobei e={x,y} eine Multigraphenkante und die Flußrichtung von der zweiten zur dritten Tupelstelle gegeben ist. Es kann also auch e'={y,x} mit f(e',x,y) /= f(e,x,y) existieren ( parallele Kanten, entgegengesetzte Flußrichtung ). Läßt man Multigraphen außen vor, so erscheint die Forderung nach negativem Fluß bei entgegengesetzter Flußrichtung zur Anwendung der Kirchhoff'schen Regel ( \sum_{y \in N(x)} f(x,y) = 0 ) trotzdem sinnvoll.

Hinweis: da spaeter der Algorithmus von Ford _Fulkerson genannt wird, ist es wichtig, bereits an dieser Stelle darauf hinzuweisen, dass man sich zweckmaessigerweise oft auf ganzzahlige (bzw. rationale, dann mit Multiplikation ganzzahlig machen) Werte beschränkt, denn der Ford-Fulkerson Algorithmus konvergiert bei beliebigen reellen Werten nicht immer.Letztlich ist die "Beschränkung" auf ganzzahlige Werte keine besondere, denn sie entspricht der Festlegung der "Einheit" des "Mediums", welches über die Kanten fliesst. Negative Werte sind durchaus sinnvoll, weil etwas gegen den Orientierungssinn in der Praxis zurüchfliessen kann, Kanten mit Kapazität 0 sind formal praktisch. JRM, 16.5. 2005

Artikelbezeichnung

Wäre es möglich diesen Artikel Netzwerke in der Graphentheorie zu benennen, da dies ein sog. Übersichtsartikel in der Thematik Graphentheorie zu sein scheint (was in der Form erst auf dem dritten Blick erkennbar ist). Neben Flüssen und Schnitten bieten Netzwerke sicher noch mehr... --Bolliver 21:08, 17. Feb 2005 (CET)

Ähmm... nö, es geht hier ja nur um Flüsse und Schnitte und das Thema ist sicher ausreichend für einen Artikel. Was gibt es noch über Netzwerke zu sagen? --Coma 16:35, 18. Feb 2005 (CET)

Wert

Der Wert eines s-t-Flusses ist die Summe der eingehenden abzüglich der ausgehenden Belegungen der Senke s bzw. die ausgehenden Belegungen abzüglich der eingehenden Belegungen der Quelle t. Senken haben keine ausgehenden, Quellen keine eingehenden Kanten! Die Verwendung des Begriffs Belegung scheint mir auch nicht sonderlich geeignet, da an keiner Stelle definiert!? --Bolliver 21:21, 17. Feb 2005 (CET)

Hmm... ein s-t-Fluss ist ja eine Funktion mit speziellen Eigenschaften, die von den Kanten in die Menge der reellen Zahlen abbildet. Ich schätze mal, der Satz muss komplett neu formuliert werden, um das klarzustellen. --Coma 16:37, 18. Feb 2005 (CET)

Bolliver, wer sagt denn, dass eine Quelle keine eingehenden Kanten haben darf? Mirakulix 17:22, 3. Jul. 2008 (CEST)

Ich hab' den Absatz komplett neu formuliert. Ich weiß nicht, ob die neue Formulierung schöner klingt, ist aber auf jeden Fall exakter. Mirakulix 18:48, 3. Jul. 2008 (CEST)

Quelle/Senke

Kommentar: Zunächst sind die Bezeichnungen unglücklich gewählt: s = source oder sink ? Also besser Quelle q und Senke s. Dann ist die Netzwerk- Definition einerseits eine Spezialisierung: es wird nur eine Quelle und nur eine Senke angenommen. Anderseits, im allgemeinen Fall, können mehrere Quellen und Senken in einem Netzwerk (mehrere Produzenten, Verbraucher) vorhanden sein. Quellen zB haben in diesem Sinne eine "Ergiebigkeit": Summe von dem, was hineinfliesst minus Summe von dem , was herausfliesst. Es ist daher im Sinne des obigen Kommentars im nächsten Schritt zweckmaessig, nach einer allgemeinen Definition des Netzwerkes (Transportnetz)sich dann zu beschränken auf: Netze mit (1) nur einer (genau einer) Quelle und nur einer (genau) einer Senke und dann aber explizit zu verlangen (2) d-(Quelle) = 0 , d.h., es fliesst nichts hinein und d+(Senke) = 0 , es fliesst nichts heraus. Die Flusserhaltungsregel besagt dann, dass es neben Quelle und Senke es eben noch Durchgangsknoten gibt, für die die Summen der Eingänge minus der Summen der Ausgänge = 0 sind. Demnach sollte die grundlegende Definition geändert werden. JRM, 16.5.2005

Netzwerke mit mehreren Quellen und Senken können leicht durch solche mit genau einer Quelle und genau einer Senke simuliert werden. Daher ist es wenig nützlich solche Netzwerke explizit zu betrachten. --Coma 21:39, 16. Mai 2005 (CEST)

Die Bezeichnungen s und t sind meiner Kenntniss nach üblich. Mirakulix 18:52, 3. Jul. 2008 (CEST)

Also im englischsprachigen Ausland wird ebenfalls s und t verwendet. Die Bedeutung ist allerdings Source und Sink, aber nicht Target. night 22:27, 18. Nov. 2011

Schnitte

Hallo zusammen, ich hatte die Ehre mich in meinem Studium etwas mit Graphentheorie rumschlagen zu dürfen und hab dabei auch hier und da mal in den zugehörigen Artikeln hier gestörbert. Etwas merkwürdig fand ich dabei immer, dass das Thema Schnitte hier nur mehr oder weniger in einem Absatz zu Flüssen und Netzwerken abgehandelt wird, während es in meinen Vorlesungen doch einen recht breiten Raum einnahm (wie ich finde, zurecht, aber ich kenne natürlich auch nur eine Vorlesung). Ich hab daher auf einer Benutzerseite mal mit einer neuen Version von Schnitt (Graphentheorie) angefangen. Abbildungen sollen auch noch dazu (und natürlich der fehlende Text).

Was haltet ihr davon? Immerhin ist die Weiterleitung von Schnitt (Graphentheorie) seit Ewigkeiten aktiv, scheint bisher also keinen gestört zu haben (aber ich bin ja mutig). Da ich nicht soooo viel Erfahrung mit dem Schreiben mathematischer Artikel habe, freue ich mich natürlich auch über Hinweise und, wenn das Zeugs dann die Tage im Artikelraum steht, auch über Ergänzungen/Korrekturen usw. (prinzipiell könnt ihr natürlich auch auf meiner Benutzerseite an dem Artikel mithelfen, würde dann aber problematisch mit Autorennennung und so weiter). Kurz: Falls ihr meint, ich mach da grad totalen Blödsinn, gebt mir bescheid, dann brauch ich nämlich nicht weiterarbeiten. Danke. :) -- Ollie B Bommel 22:53, 1. Feb 2006 (CET)

Natuerlich sollen Schnitte in Graphen in einem besonderen Artikel behandelt werden. Danke fuer Dein Vorpreschen ;-). --zeno 13:41, 10. Feb 2006 (CET)

Laufzeit

wenn alle Kanten nur 0 oder 1 als Kapazitäten haben dürfen, verbessert sich die Laufzeit auf O(|V|2/3|E|).

Ist dieser Nebensatz noetig? Die Beschraenkung auf 0 oder 1 macht unser Netzwerk quasi zu einem gerichteten Graphen... --zeno 13:36, 10. Feb 2006 (CET)

Ein Netzwerk an sich ist schon ein gerichteter Graph.

Restnetzwerk

Die Definition des Restnetzwerks stimmt meiner Meinung nach nicht mit der Graphik überein.

Laut Definition würde das Restnetzwerk nur aus den Fett-gedruckten Pfeilen bestehen, nicht jedoch aus den Dünn-gedruckten grauen Pfeilen, die das "Rückwärtslaufen" ermöglichen.

Leider kriege ich keine schöne Definition dafür hin, deshalb stelle ich folgende zur Diskussion:

Das Restnetzwerk (auch: Residualgraph) bezüglich eines zulässigen Flusses ist ein Graph, der alle Kanten des ursprünglichen Netzwerkes enthält, mit um den jeweiligen Flusswert verminderten Kantenkapazitäten, und einer jeweiligen Rückkante mit dem Fluss als neuer Kapazität.

Stimmt. Dass müsste dann auch noch auf Residualgraph geändert werden.Mirakulix 18:57, 3. Jul. 2008 (CEST)

Algorithmenspezifikation fehlt

quote: "Die folgende Tabelle gibt eine Übersicht der entwickelten Fluss-Algorithmen und ihrer Laufzeiten:" Da fehlt doch etwas. "Fluss-Algorithmen", wofuer?

Definition des Schnitts

Nach meinen Unterlagen ist die Aussage, dass ein Schnitt eine Teilmenge der Knoten ist nicht richtig. Vielmehr ist ein Schnitt die Kantenmenge, die die Knoten aus $S$ und $V\backslash S$ verbindet. Dann wird auch die Aussage zur Kapazität weiter unten klarer.

Stimmt. Das wäre einheitlich mit dem Schnitt (Graphentheorie) und dem Skript von Martin Grötschel(http://www.zib.de/groetschel/teaching/skript-SS2006.pdf). Im englischen en:Cut (graph theory) ist allerdings auch der Schnitt als Zerlegung der Knotenmenge definiert. Mirakulix 19:19, 3. Jul. 2008 (CEST)

Verschieben nach Flussalgorithmmus

Passt mE etwas besser zum Inhalt.-goiken 01:19, 23. Okt. 2009 (CEST)

Hallo goiken! Hm, finde ich nicht. Meinetwegen könnte man die Algorithmen hier auch weniger ausführlich beschreiben, weil sie ja schon in ihren eigenen Artikeln erklärt werden. Prinzipiell glaube ich, dass viele kurze Artikel besser sind als ein langer. Wenn man nur mal eben einen Begriff nachschlagen möchte, findet man es praktischer, in einem übersichtlichen Artikel des Begriffes das zu finden, was man sucht, anstatt es sich in einem langen Übersichtsartikel raussuchen zu müssen. MfG Stefan Knauf 01:56, 27. Dez. 2009 (CET)

na die Motivation hinter dem Vorschlag war, dass der Artikel hier nicht kaum hält, was er im Titel verspricht. Auch, wenn man Ausführungen zu den Algorithmen herauskürzt. Würde man nach dem Titel arbeiten, müsste man imho auf die Dualität Kreis <-> Schnitt viel stärker eingehen. Man müsste das Färbungslemma von Minty erwähnen, inzidenzvektoren und in der Folge Zyklen- und Co-Zykleraum einführen, sowie und auch überhaupt den Zusammenhang zwischen existenz von gewissen Flüssen und Färbbarkeitsaussagen im Dualgraphen viel stärker herausheben. Ich würde aber, nicht zuletzt, weil es bis dato kaum Artikel dazu gibt, dafür (irgendwann einmal vielleicht) eine eigene Baustelle aufmachen. --goiken 03:10, 27. Dez. 2009 (CET)

Breite des Fließtextes

die Tabelle

Definition des Schichtnetzwerkes

Hallo goiken! Gerade habe ich die in der Formatierung überarbeitete Tabelle der Flussalgorithmen und ihrer Laufzeiten wieder in den alten Zustand zurückversetzt. Mein Grund dafür liegt lediglich darin, dass bei Laptopbildschirmen (z.B. 1.024 Pixel breit) neben der Tabelle nur eine sehr schmale Spalte für den Fließtext übrig war (siehe Bild). Meinetwegen kannst Du die Tabelle überarbeiten, aber mache es bitte so, dass man den Artikel auch mit Laptops noch gut lesen kann. Das kannst Du beispielsweise überprüfen, indem Du Dein Browser-Fenster einfach schmaler machst. Nebenbei empfinde ich die Tabelle als besser lesbar, wenn die einzelnen Felder mit Trennlinien getrennt sind. Die alte Version empfinde ich optisch als völlig in Ordnung.
Darüber hinaus zerschießen bei 1.024 Pixel breiter Darstellung die Boxen für die Push- und die Lift-Operationen die Definition des Schichtnetzwerkes (siehe Bild). Kannst Du da bitte was gegen machen? MfG Stefan Knauf 01:56, 27. Dez. 2009 (CET)

Die beste Lösund fände ich ja, die große Tabelle einklappbar zu machen. Jemand, der den Artikel liest, schaut da mE eh mehr drauf, als tatsächlich rein. Die Zeit, mich mit den vielen Anleitungen dazu auseinanderzusetzen hab ich aber nicht gefunden. Inhaltlich müsste man da auch noch einmal drüber. Die wurde Afaik etwa vor 2-3 Jahren eingestellt. Zu einigenn Methoden gibt es (mitlerweile) Artikel, zu anderen oftmals wenigstens ein Paper, welches man referenzieren sollte.

Die Code-Fetzen könnte man in den Fließtext legen, etwa so, wie das hier passiert.

was ist mit dem Worst-Case-Beispiel zu Fulkerson? Das war in der Darstellung im Artikel irgendwie falsch, obwohl die richtigen Dateien bereits bei den commons lagen. Dachte, das legt sich mit der Zeit, aber das ist wohl Pustekuchen.--goiken 02:34, 27. Dez. 2009 (CET)

Hallo goiken! Ich bin dagegen, Algorithmen zum Finden eines maximalen s-t-Flusses in diesem Artikel ausführlicher zu beschreiben. Die Beschreibungen der Algorithmen können in ihre eigenen Artikel. Über den Algorithmus von Dinic möchte ich in den nächsten Semesterferien einen Artikel schreiben, wenn mir keiner zuvor kommt.

Das „Worst-Case-Beispiel“ war schon richtig, um einen Graphen anzugeben, bei dem der Ford-Fulkerson-Algorithmus unverhältnismäßig lange brauchen kann. Allerdings ist mir nicht ersichtlich, was bitte schön ein „Worst Case“ sein soll, weil der Ford-Fulkerson-Algorithmus auch in fünfkantigen Graphen beliebig astronomische Laufzeiten annehmen kann, wenn man längst der „richtigen“ Wege augmentiert und die Kapazitäten schön astronomisch gewählt sind. MfG Stefan Knauf 22:32, 27. Dez. 2009 (CET)

Tarjan

Ich würde dem Leser, der von all den Sachen das erste mal hört, beim Einführen der Präflüsse anbieten, das Kapitel zu überspringen. Die Dinger braucht man afaik lediglich bei Preflow-Push-Methoden. zum Verstehen von Karp, F&F und Dinic reichen die anderen Begriffe schon aus. --goiken 16:32, 27. Dez. 2009 (CET)

Hallo goiken! Ich glaube nicht, dass ein normaler Leser den Artikel komplett liest. Ich habe das bei diesem Artikel auch nur gemacht, um Fehler zu finden und zu entsorgen. Und ich vertraue darauf, dass ein Leser selber weiß, was ihn interessiert, und er den Text über die Präflüsse überspringt, wenn ihn das nicht interessiert. Ich halte es für vollkommen sinnlos, in einen Abschnitt zu schreiben, dass er von unerfahrenen Lesern übersprungen werden sollte. Ob jemand was über Präflüsse wissen möchte (z.B. weil er gerade Präflüsse braucht und erst mal wissen möchte, was das eigentlich sind), hängt nicht unbedingt von seiner Erfahrung ab.

Außerdem habe ich gerade schon zum zweitem Male Deinen „Beweis“ zum Edmonds-Karp-Algorithmus aus dem Artikel genommen. Die Behauptung, das Hinzufügen der Rückkanten könnte die Entfernung zwischen zwei Knoten nicht verändern, ist einfach Quatsch. Wenn der Graph nicht gerade symmetrisch war (also nicht zu jeder Kante $(v,w)$ auch eine Kante $(w,v)$ im Graphen war), sollte man damit rechnen, dass man durch das Hinzufügen von Rückkanten Entfernungen verändert. Das kann auch passieren, wenn man nur entlang kürzester s-t-Wege Rückkanten hinzufügt. Ich wäre Dir dankbar, wenn Du keinen Quatsch mehr in Artikel einfügen würdest. Ein korrekter Laufzeit-Beweis des Edmonds-Karp-Algorithmus ist im Korte-Vygen anderthalb Seiten lang; würde ich ihn selber Formulieren, würde er auch nicht kürzer. Im Artikel braucht man den Beweis auch nicht. Beweise sind zwar gut und wichtig, allerdings können sie in einer Enzyklopädie störender Ballast sein. Für Beweise gibt es Mathematikbücher. Unser Artikel sollten einen guten Überblick über den Artikelgegenstand verschaffen. Wenn man einen Beweis in wenigen Sätzen gut formulieren kann, mache ich das zwar auch manchmal, aber „große“ Beweise lasse ich normalerweise weg. Außerdem sollte man die Laufzeit-Beweise für einen bestimmten Algorithmus wenn überhaupt in den Artikel des Algorithmus packen.

In Graphen mit nur endlich vielen Kanten und nur endlichen (reellen) Kapazitäten existieren immer maximale s-t-Flüsse (weil die Menge möglicher Werte der Flüsse abgeschlossen und beschränkt ist und damit ihr Supremum annehmen muss), also braucht man die Existenz auch nicht als Bedingung dazu zu schreiben. In unendlichen Graphen terminieren diese Algorithmen wahrscheinlich eh nicht (zumindest sicher nicht in denen, in denen es unendlich viele s-t-Wege gibt).

Und es gibt auch Anwendungen, in denen man den Ford-Fulkerson-Algorithmus durchaus benutzen möchte, z.B. wenn alle Kanten gleiche Kapazität haben. Die Anzahl der nötigen Augmentierungen ist dann nämlich unabhängig davon, entlang welcher s-t-Wege man augmentiert, so dass man sich das Kürzeste-Wege-Suchen auch sparen kann. Dass man den Algorithmus praktisch nie benutzen will, würde ich also nicht glauben. Wenn keine Bedingungen an die Kapazitäten gestellt sind, sollte man von diesem Algorithmus natürlich die Finger lassen. Meiner Meinung nach brauchen diese Details aber sicher nicht in den Artikel. Ich kann mir nur schwer vorstellen, dass es viele Leute gibt, die in einem Nachschlagewerk einen im Druck acht A4-Seiten langen Text lesen wollen. Weniger ist mehr, allerdings muss das, was bleibt, natürlich auch gut sein. Wenn ich in den Weihnachtsferien noch Zeit finde, werde ich den Artikel noch mal überarbeiten. MfG Stefan Knauf 22:32, 27. Dez. 2009 (CET)

Reihenfolge der Bilder im Artikel

Die Bilder erscheinen im Artikel bevor die entsprechenden Begriffe im Artikel erklärt werden, die Box sollte auseinandergenommen werden und die Bilder in die entsprechenden Unterabschnitte eingefügt werden... Falls demnächst Zeit hab ich dass, ansonsten hab ich aber auch nichts dagegen wenn mir einer zuvor kommt. --Schönen Gruß "Wohingenau" 14:13, 19. Mär. 2010 (CET)

Restnetzwerk oder Residualgraph (-netzwerk)

Ich finde Restnetzwerk ja wesentlich besser; der Begriff beschreibt sehr gut was es ist, ist nicht so sperrig in der Aussprache und verzichtet auf Fremdwörter - also genau das Richtige für eine (deutsche) Enzyklopädie. --89.247.112.169 10:16, 6. Apr. 2010 (CEST)

Ich hab keine Deutsche Literatur zur Verfügung um einzuschätzen welcher Begriff häufiger benutzt wird. Aber Momentan werden beide Begriffe erwähnt, seh also nicht so dass Problem. Wenn man sich aber entscheidet den Begriff Restnetzwerk zu benutzen in der deutschen Wikipedia, so sollte man ihn in allen Artikeln ändern, die auf diesen Begriff verlinken, was ich alls ganz schöne Arbeit ansehe. --Schönen Gruß "Wohingenau" 19:06, 6. Apr. 2010 (CEST)

Max-Flow-Algorithmen

Man sollte vielleicht noch den Algorithmus von Satoru Fujishige (2002) hinzufügen, der eine Laufzeit von O(m*n*log(U)) hat. Erwähnung sollten auch noch Random Sampling Methoden finden. (nicht signierter Beitrag von 91.9.214.252 (Diskussion) 21:49, 30. Okt. 2010 (CEST))

nichtnegative Kapazität

Wie ist das denn definiert? Es geht doch hier um beliebige Mengen mit totaler Ordnung, was ist denn in solchen Mengen positiv und was ist negativ? --Jobu0101 18:06, 20. Jun. 2011 (CEST)

Hallo Jobu0101! Gute Frage... Im Artikel sind die Funktionen ja explizit als reellwertig definiert. Ich habe die Bemerkung „Die Kapazitätsfunktion kann in beliebige Mengen mit einer totalen Ordnung abbilden. (Beispiele: $\mathbb {N}$, $\mathbb {Z}$, $\mathbb {R}$, $\mathbb {Q} ,$ ... nicht aber $\mathbb {C}$)“ gerade mal aus dem Artikel entfernt. So wie die Beispiele aussehen, war damit wohl eigentlich „jede Teilmenge der reellen Zahlen“ an Stelle von „beliebige Mengen mit einer totalen Ordnung“ gemeint... Aber jede Funktion in eine Teilmenge der reellen Zahlen ist ja insbesondere auch eine reellwertige Funktion, weswegen man das wohl auch weglassen kann. (Ganz nebenbei bemerkt ist es auch kein Problem, die Menge der komplexen Zahlen linear zu ordnen, die Ordnung hat dann nur nicht viel mit der Körperstruktur zu tun.) MfG Stefan Knauf 00:10, 21. Jun. 2011 (CEST)

Richtig, die komplexen Zahlen sind ja gleichmächtig wie die reellen, von daher ist vollkommen klar, dass man die komplexen Zahlen auch total ordnen kann, da es mit den reellen geht. Das ist mir beim Durchlesen auch aufgefallen, nur wollte ich dazu nichts schreiben, weil den Leuten, die das lesen und verstehen können, das klar sein sollte, was gemeint ist. --Jobu0101 17:46, 21. Jun. 2011 (CEST)