Dotazy na grafové algoritmy

Dotaz k definici Ford-Fulkersona - Mareš ho má v materiálech definovaný takhle:

Algoritmus (Fordův-Fulkersonův)

1. f ← libovolný tok, např. všude nulový (∀e ∈ E : f(e) ← 0).

2. Dokud ∃P cesta ze z do s taková, že ∀e ∈ P : r(e) > 0, opakujeme:

3. ε ← min{r(e) | e ∈ P}.

4. Pro všechny hrany uv ∈ P:

5. δ ← min{f(vu), ε}  
   

6. f(vu) ← f(vu) − δ  
   

7. f(uv) ← f(uv) + ε − δ  
   

8. Prohlásíme f za maximální tok.

co se týče samotného principu algoritmu, tak ten mi jasný je...ovšem asi bych potřeboval od někoho přechroustat, proč jsou ty body 5-7 zadefinovaný právě takhle? konkrétně mě tam mate ten bod č. 7 - to "+ ε − δ"...protože když v kroku 5 nastavím δ ← ε, tak to jako znamená, že se pak tok po hraně vůbec nijak nezmění? možná to je přesně to, co má být, ale nedokážu si to teďka nějak představit v hlavě, za jakých podmínek bude δ ← ε - resp. že to bude ve chvíli, kdy ε je menší než aktuální tok v protisměru, to bych ještě dal, ale co z toho má plynout pro tok po směru a jeho modifikování...?

možná to pro většinu lidí, co to budou číst, bude vypadat triviálně, ale já jsem se na tom zasekl už aspoň na půl hodiny a nepohnul jsem s tím ani během formulování a psaní dotazu (což se mi někdy povede)

Když něco posíláme po hraně, tak snižujeme její rezervu. r(uv) = c(uv) – f(uv) + f(vu)

V 5. kroku porovnáme f(vu) a ε.

Pokud je f(vu) menší, tak v 6. kroku f(vu) vynulujeme. Snížili jsme r(uv) o δ. Celkem máme r(uv) snížit o ε (ε >= δ), takže r(uv) ještě musíme snížit o ε – δ. Nyní tvoří rezervu pouze c(uv) – f(uv), protože f(vu) = 0. Abychom ji snížili, tak v 7. Kroku k f(uv) přičteme ε – δ.

Pokud je ε menší, tak v 6. kroku f(vu) snížíme o ε a tím pádem klesne o stejnou hodnotu i r(uv). Dál už ji snižovat nemusíme, proto se v 7. kroku nic nezmění.

díky, trochu to pomohlo :)

ještě bych ale měl jednu otázku - když jsem se o zkoušku pokoušel minule, neúspěšně, tak jsem měl Goldbergův algoritmus a u někoho dokázat korektnost...a během dokazování jsem řekl Marešovi "když f není max. tok, tak existuje nenasycená cesta ze zdroje do stoku" a on mě hned přerušil a chtěl vědět proč existuje...a to sem nevěděl...ovšem teďka koukám do pdfka z jeho stránek a tam je u toho lemmatu o korektnosti goldberga taky jenom, že ta cesta existuje a není tam už rozebráno proč...

mě napadá jediné, odvolávat se na Ford-Fulkersona, který by tuhle nenasycenou cestu našel a použil ke zlepšení toku a zastaví se až ve chvíli, kdy taková cesta neexistuje a tok je maximální, což o něm víme, že max. tok správně najde...je to ono, nebo je v tom nějaký složitější fígl?

povedal by som, ze by stacilo sa odvolat bud na Ford-Fulkersena, alebo to dokazat sporom: nech mame max. tok f a existuje tam este nenasytena cesta P, teda $\forall e \in P: r(e) > 0$, oznacme potom $\varepsilon := \min_{e \in P} r(e)$ a vieme vytvorit tok f': $$f'(e) = f(e) (e otin P)$$, $f'(e) = f(e) \pm \varepsilon (e \in P)$ podla smeru hrany e, co je vacsi tok ako f, co je v spore s maximalitou toku f