matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorie"Flussproblem"
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Graphentheorie" - "Flussproblem"
"Flussproblem" < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

"Flussproblem": Graphen mit Zyklen
Status: (Frage) beantwortet Status 
Datum: 18:51 Fr 22.04.2011
Autor: bardock84

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 :)

        
Bezug
"Flussproblem": Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
"Flussproblem": Gleichungssystem aufstellen
Status: (Antwort) fertig Status 
Datum: 11:06 Sa 23.04.2011
Autor: Al-Chwarizmi


> 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
    
    

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]