Graph - Flusswert, Excess und maximaler Fluss

Neue Frage »

Majin_Clodan Auf diesen Beitrag antworten »
Graph - Flusswert, Excess und maximaler Fluss
Heyho Leute. smile

Ich habe ein paar Fragen bzgl. Flüssen in Graphen.

Wir haben den flusswert wie folgt definiert:



Hierbei bezeichnet f den Fluss.

Ich verstehe diese Definition leider irgendwie falsch. Ich denke mir hier immer, dass der Wert 0 herauskommen muss. Laut meiner Kommolitonen ist dies nicht der Fall. Kann mir vllt. jemand erklären, wie man diese Definiton genau versteht? smile

Den Excess in einem Graphen definieren wir wie folgt:




Dieser ist doch zu verstehen, dass die Summe aller Kantenwerte, die aus v rausgehen mit der Summe aller Kantenwerte, die in v reingehen, subtrahiert werden, oder? smile

Die letzte Definition ist die des maximalen Flusses:
"Ein Fluss heißt maximaler s-t-Fluss (s und t sind Knoten), wenn er maximalen Flusswert unter allen s-t-Flüssen hat."

Ich dachte die ganze Zeit, dass es im Graphen nur einen Fluss gibt. Wieso kann es jetzt mehrere geben? Wahrscheinlich verstehe ich diese Definition auch nicht genau, weil ich mir mit dem Begriff "Flusswert" noch sehr unsicher bin.


Wäre super von euch, wenn ihr mir bei meinen Fragen helfen könntet. smile
Vielen Dank schon einmal für die Hilfe. smile


MFG Majin_Clodan
Abakus Auf diesen Beitrag antworten »
RE: Graph - Flusswert, Excess und maximaler Fluss
Hallo,

im Prinzip hast du ein Netzwerk von Wasserleitungen. Irgendwo gibt es Quellknoten, wo das Wasser herkommt. Und dann gibt es Senken, wo das Wasser wieder verschwindet (also etwa ein Wasserhahn, wenn er Endknoten ist und du ihn aufdrehst).

Jetzt kann Wasser durch dein Netzwerk fließen, und zwar viel oder wenig. Das hängt halt davon ab, wie stark deine Leitungen ausgenutzt werden, und wie stark dein Wasserhahn aufgedreht ist. Das Maximum, was am Wasserhahn rauskommen kann, ist der max. Fluss.

Etwas bildlich erklärt; aber danach müsstest du deine Definitionen mal abchecken, was diese in diesem Kontext besagen (ich kenne deine Bezeichnungen nicht exakt).

Abakus smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »