"Flussproblem" |
22.04.2011, 18:30 | bardock | Auf diesen Beitrag antworten » |
"Flussproblem" ich habe gerade folgends Problem: Man hat einen Graphen. Z.B. diesen hier: Edit (mY+): Links zu externen Hosts sind nicht gestattet. Der Link wurde entfernt. Hänge dein Bild - NICHT im BMP- sondern in in einem komprimierten Format (!) - an den Beitrag an. [attach]19217[/attach] 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 = 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 |
||
25.04.2011, 10:36 | Abakus | Auf diesen Beitrag antworten » |
RE: "Flussproblem" Hallo, das sieht aus wie ein Markow-Prozess, behandeln lässt sich dein Beispiel mit einer Übergangsmatrix und ihren Potenzen dann. Grüße Abakus |
|