Min. Cost Flows < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 11:52 Mi 20.08.2008 | | Autor: | Jan_Z |
| Aufgabe | Input: A digraph G with infinite capacities, numbers b: V(G) [mm] \to \IR [/mm] mit [mm] \summe_{v \in V(G)}b(v)=0 [/mm] und conservative weights c: [mm] E(G)\to [/mm] IR
Output: A min. cost b-flow f.
1) Set b'=b, f=0, [mm] r=id_{V(G)}, F=\emptyset, \gamma=max\{|b'(v)|:v\in V(G)\}
[/mm]
2) If b'=0 then STOP.
3) Choose a vertex s with [mm] b'(s)>\bruch{n-1}{n}\gamma. [/mm] If there is no such s then go to 4)
Choose a vertex t with [mm] b'(t)<-\bruch{1}{n}\gamma [/mm] such that t is reachable from s in [mm] G_{f}. [/mm] If there is no such t then STOP (there exists no b-flow)
Go to 5)
4) Choose a vertex t with [mm] b'(t)<-\bruch{n-1}{n}\gamma. [/mm] If there is no such t then go to 6)
Choose a vertex s with [mm] b'(s)>\bruch{1}{n}\gamma [/mm] such that t is reachable from s in [mm] G_{f}. [/mm] If there is no such s then STOP (there exists no b-flow)
5) Find an s-t-path P in [mm] G_f [/mm] of minimum weight. Set [mm] b'(s):=b'(s)-\gamma, b'(t):=b'(t)+\gamma [/mm] and augment f along P by [mm] \gamma.
[/mm]
Go to 2)
6) If f(e)=0 for all [mm] e\in E(G)\backslash [/mm] F then set [mm] \gamma:=\min\{\bruch{\gamma}{2},max\{|b'(v)|:v\in V(G)\}\}
[/mm]
else set [mm] \gamma:=\bruch{\gamma}{2}
[/mm]
7) For all [mm] e=(x,y)e\in E(G)\backslash [/mm] F with [mm] r(x)\not=r(y) [/mm] and [mm] f(e)>8n\gamma [/mm] do:
Set [mm] F:=F\cup\{e,e^{-1}\}
[/mm]
Let x':=r(x) and y':=r(y). Let Q be the x'-y'-path in F.
If b'(x')>0 then augment f along Q by b'(x')
else augment f along the reverse of Q by -b'(x')
Set b'(y'):=b'(y')+b'(x') and b'(x')=0
Set r(z):=y' for all vertices z reachable from y' in F
8) Go to 2)
|
Hallo,
ich bereite mich grad auf ne Pruefung vor und verzweifle :(
Ich versteh diesen Algortihmus irgendwie nicht:
Warum man die Knoten s und t in 3) und 4) so waehlt, und warum man bei 6 eine fallunterscheidung macht. In 7) ist von "der x'-y'-Pfad" die Rede. Warum gibt es da genau einen?
Waer gut wenn jemand das Buch "Combinatorial Optimization" zur Hand hat (Kapitel 9.5).
Ich hoffe mir kann jemand helfen :( Vielen Dank schonmal!
Zu den Bezeichnungen: V(G) ist die Menge der Knoten in G, E(G) die Menge der Kanten, das "conservative" bei den Kantengewichten c bedeutet, dass es keine Kreise in G von negativem Gewicht gibt, [mm] G_{f} [/mm] ist der Residuengraph von f, [mm] e^{-1} [/mm] ist die Inverse Kante zu e (wird im Buch mit einem Pfeil nach links ueber dem e bezeichnet, aber ich wusste nicht wie das mit dem Formeleditor geht)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Sa 20.09.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
