wolti
17-06-2003, 22:44
Hallo,
:edit: Erledigt. Ich denke ich bekomme es jetzt raus.
Da ich heute leider irgendwie verpennt habe, habe ich leider dir Vorlesung verpasst. Habe aber vom Hal die Mitschrift bekommen und wollte fragen, ob jemand den letzten Algorithmus versteht, mir kommt vor als ob er noch nicht fertig ist, aber Hal meint schon irgendwie.
Der erste Schritt ist klar:
1) Ich definiere alle f(e) als 0, das ist sicher ein gültiger Fluss.
2) f' = f + g (Die Addition dieser beiden Funktion, wobei f'(e) = f(e) + f(g) ist)
Die muss wieder einen Fluß darstellen, daher die Bedinungen:
f'(e) <= f(e) + g(e) <= c(e) (Klar, die Kapazität selber darf nicht überschritten werden)
=> g(e) <= c(e) - f(e)
Da ich jetzte denke ich weiss wie das funktionieren könnte -> Hier ein Ansatz für die, die es heute auch verpasst haben
1) Man bildet das Restflussnetzwerk. Wobei der Graph Gf definier ist als.
Gf=(V(Gf),E(Gf)) mit
V(Gf)=V(G)
E(Gf): <x,y> e E(Gf) <=> c(<x,y>) - f(<x,y>) > 0 ist (Auf gut Deutsch, wenn noch Platz ist)
cf(<x,y>) = c(<x,y>) -f(<x,y>)
Dann zeichnet man den Graphen und sucht sich eine Tour von s nach t. Dann nimmt man das minium der dabei auftretenden neuen Kapazitäten. Dies ist dann das delta vom g.
Aus der Addition der beiden Funktionen (Elementweise) erhält man dann ein neues f'.
Dann probiert man wieder, ob noch eine neue Tour im Restflussnetzwerk vorhanden ist.
Gibt es keine mehr, ist der so entstandene Fluss maximal.
Grüße,
Wolti
:edit: Erledigt. Ich denke ich bekomme es jetzt raus.
Da ich heute leider irgendwie verpennt habe, habe ich leider dir Vorlesung verpasst. Habe aber vom Hal die Mitschrift bekommen und wollte fragen, ob jemand den letzten Algorithmus versteht, mir kommt vor als ob er noch nicht fertig ist, aber Hal meint schon irgendwie.
Der erste Schritt ist klar:
1) Ich definiere alle f(e) als 0, das ist sicher ein gültiger Fluss.
2) f' = f + g (Die Addition dieser beiden Funktion, wobei f'(e) = f(e) + f(g) ist)
Die muss wieder einen Fluß darstellen, daher die Bedinungen:
f'(e) <= f(e) + g(e) <= c(e) (Klar, die Kapazität selber darf nicht überschritten werden)
=> g(e) <= c(e) - f(e)
Da ich jetzte denke ich weiss wie das funktionieren könnte -> Hier ein Ansatz für die, die es heute auch verpasst haben
1) Man bildet das Restflussnetzwerk. Wobei der Graph Gf definier ist als.
Gf=(V(Gf),E(Gf)) mit
V(Gf)=V(G)
E(Gf): <x,y> e E(Gf) <=> c(<x,y>) - f(<x,y>) > 0 ist (Auf gut Deutsch, wenn noch Platz ist)
cf(<x,y>) = c(<x,y>) -f(<x,y>)
Dann zeichnet man den Graphen und sucht sich eine Tour von s nach t. Dann nimmt man das minium der dabei auftretenden neuen Kapazitäten. Dies ist dann das delta vom g.
Aus der Addition der beiden Funktionen (Elementweise) erhält man dann ein neues f'.
Dann probiert man wieder, ob noch eine neue Tour im Restflussnetzwerk vorhanden ist.
Gibt es keine mehr, ist der so entstandene Fluss maximal.
Grüße,
Wolti