"Flussproblem" < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.informatikerboard.de/board/thread.php?threadid=923
http://www.matheboard.de/thread.php?threadid=453664
Hallo,
ich habe gerade folgends Problem, welches ich auch schon bei matheboard und informatikboard gestellt habe, aber wenig Hoffnung habe, dass das ohne eure Hilfe gelöst werden kann (oder mir gesagt werden kann, dass man das nicht lösen kann):
Man hat einen Graphen z.B. diesen hier:
[Externes Bild http://dl.dropbox.com/u/13484695/graph.bmp]
Hier "fliesst" z.B. eine Einheit von außen zu Knoten A. Von diesem fließen laut Kantengewicht 100% nach B. Hier fließt dann 80% zu G und 20% zu C usw.
Mich interessiert jetzt welche Menge bei den einzelnen Knoten durchgeflossen ist.
Für z.B. den Knoten A nähert sich die "durchgeflossene" Menge an 1,25 an.
Das ist einfach daraus ersichtlich, dass alles letztendlich zu G abfließt und man dann den Reihenwert des Zyklus mit 0,2 bilden kann [mm] [latex]\sum_{i=0}^{\inf}(0.2)^i[/latex] [/mm] = 1,25, woraus man dann A = 1,25 erhält -> B = 1,25 ...
Aber wie verhält sich das Ganze, wenn z.B. ein Teil bei E abfließt.. Gibt es dafür einen allgemeinen Ansatz? Vllt kann mir auch jemand sagen, wie das Problem eigentlich heißt... Ich habe bisher nur Sachen zu maximalen s-t Flüssen gefunden, die hierauf aber nicht wirklich passen...
Irgendjemand eine Idee?
Danke schon einmal :)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:28 Sa 23.04.2011 | | Autor: | Manatu |
Hallo bardock84,
eine richtige Antwort habe ich leider gerade auch nicht zur Hand, werde ich mal drüber nachdenken. Wenn mir im laufe des Wochenendes was einfällt, schreib ich es noch.
Aber ein kleiner Hinweis schonmal:
Vielleicht findest du mehr, wenn du nicht unter Graphentheorie und Netzwerken suchst, sondern wenn du in der Wahrscheinlichkeitsrechnung unter bedingten Wahrscheinlichkeiten suchst.
Viele Grüße,
Manatu
|
|
|
| |
|
> Man hat einen Graphen z.B. diesen hier:
>
> [Externes Bild http://dl.dropbox.com/u/13484695/graph.bmp]
>
> Hier "fliesst" z.B. eine Einheit von außen zu Knoten A.
> Von diesem fließen laut Kantengewicht 100% nach B. Hier
> fließt dann 80% zu G und 20% zu C usw.
>
> Mich interessiert jetzt welche Menge bei den einzelnen
> Knoten durchgeflossen ist.
>
> Für z.B. den Knoten A nähert sich die "durchgeflossene"
> Menge an 1,25 an.
>
> Das ist einfach daraus ersichtlich, dass alles letztendlich
> zu G abfließt und man dann den Reihenwert des Zyklus mit
> 0,2 bilden kann [mm]\sum_{i=0}^{\inf}(0.2)^i\ =1,25[/mm] ,
> woraus man dann A = 1,25 erhält -> B = 1,25 ...
>
> Aber wie verhält sich das Ganze, wenn z.B. ein Teil bei E
> abfließt.. Gibt es dafür einen allgemeinen Ansatz? Vllt
> kann mir auch jemand sagen, wie das Problem eigentlich
> heißt...
Hallo bardock84,
ich musste mir den Graph zuerst etwas näher anschauen,
um zu verstehen, wie alles gemeint ist.
Die an jeder gerichteten Kante angegebene Zahl steht für
eine Übergangswahrscheinlichkeit in diesem Markov-Graph.
Der Wert $\ 0.3$ an der Kante [mm] \overrightarrow{FD} [/mm] bedeutet beispielsweise,
dass von F aus die Übergangswahrscheinlichkeit nach D
30% beträgt. Die anderen 70% fließen von F aus nach C.
Ich würde zuerst geeignete Bezeichnungen einführen,
etwa:
$\ A$ = gesamter Fluss durch Knoten A
$\ AB$ = gesamter Fluss durch die gerichtete Kante [mm] \overrightarrow{AB}
[/mm]
$\ p(A,B)$ = Übergangswahrscheinlichkeit von A aus in Richtung B
(analog für alle übrigen Knoten und Kanten)
Ich würde auch noch vorschlagen, einen zusätzlichen
Knoten I und eine Kante [mm] \overrightarrow{IA} [/mm] einzuführen ("I" für "Input")
mit I=1 und p(I,A)=1 .
Damit kann man nun ein Gleichungssystem aufstellen.
So wie du richtig bemerkt hat, muss der gesamte Fluss
der Größe 1, der zu Beginn von I ausgeht, schließlich
(ev. mit vielen Umweg-Schleifen) in G ankommen. Die
in dem übrigen Netz fließenden Ströme werden in der
Art geometrischer Folgen immer kleiner und streben
gegen Null. Aus dieser Beobachtung ergibt sich auch
ohne Reihensummation der Wert $\ G=1$ und daraus
$\ BG=1=0.8*B$ und somit $\ B=1.25$ . Da alles was je in
B ankommt, von A her kommt (mit p(A,B)=1), folgt
auch $\ AB=1.25=A$. Ferner muss $\ BC=0.2*B=0.25$ sein.
Es ist aber nicht etwa $\ C=BC$, weil C ja auch noch Zufluss
über die Kante [mm] \overrightarrow{FC} [/mm] erhält. An diesem komplexesten Knoten
des Graphen erhält man die Gleichungen:
$\ C=BC+FC=0.2*B+0.7*F$
$\ C=CD+CE$
Aus dem resultierenden Gleichungssystem sollten sich alle
Kanten- und Knotenflüsse berechnen lassen.
Falls der Graph ein "Leck" hätte, z.B. noch einen Knoten L
und eine Kante [mm] \overrightarrow{EL} [/mm] mit p(E,L)=0.3 und deshalb den abge-
änderten Wert p(E,F)=0.7 , dann hätte man einfach zusätz-
liche Gleichungen. Ferner wäre dann der Schluss G=1 natür-
lich nicht mehr zuläßig !
LG Al-Chwarizmi
|
|
|
|
