#1 27. 11. 2014 23:11 — Editoval RayDoyle (27. 11. 2014 23:12)
Maximální tok - zpětný tok
Zdravím, rád bych poprosil o pomoc s příkladem na hledání maximálního toku a minimálního řezu.
Mám problém s pochopením kroku algoritmu, kdy se používá cesta v opačném směru - odečítá se tok na dané hraně.
Rád bych to ukázal na konkrétním příkladu:
Zadání přikladu:
Postupoval jsem takto:
1. Cesta V1-V2-V8, pošlu tok velikosti 1, hrana V2-V8 je nasycená.
2. Cesta V1-V7-V8, pošlu tok velikosti 1, hrana V7-V8 je nasycená.
3. Cesta V1-V4-V3-V6-V8, pošlu tok velikosti 2, hrana V3-V6 je nasycená.
A už nevidím cestu, vedoucí ze zdroje do stoku, končím tedy algoritmus, hodnota max. toku = 4. 
Správn řešení je ale prý toto:
Nerozumím tomu, proč. Další cesta má být ještě V1-V7-V5-V4-V1? To mi nedává smysl.
A jaký je prosím minimální řez?
Děkuji všem za ochotu.
Offline
#2 30. 11. 2014 10:05
Re: Maximální tok - zpětný tok
Myslím, že správná jsou obě řešení.
Obě popisují tok o velikosti 4, takže není důvod jedno upřednostňovat před druhým.
Minimální řez lze najít několik způsoby. Například najdu všechny vrcholy, kam lze ještě dopravit nějaký tok (rezervu) a všechny další (odchozí hrany ají nasycenou kapacitu a příchozí (z vrcholů bez rezervy) mají nulový tok. Řezem budou odchozí hrany.
Jak to máte popsáno ve skriptech?
Jak to vychází pro uvedený příklad?
Offline