Dotazy na grafové algoritmy

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Dotazy na grafové algoritmy

Příspěvek od Ellrohir »

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)
Naposledy upravil(a) Ellrohir dne 9. 2. 2010 17:52, celkem upraveno 1 x.
Jonáš
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 19. 1. 2010 10:57
Typ studia: Informatika Mgr.

Re: Dotaz k definici Ford-Fulkersona

Příspěvek od Jonáš »

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í.
Uživatelský avatar
Ellrohir
Matfyz(ák|ačka) level III
Příspěvky: 140
Registrován: 21. 12. 2007 13:29
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Re: Dotazy na grafové algoritmy

Příspěvek od Ellrohir »

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?
Pitr2311
Matfyz(ák|ačka) level II
Příspěvky: 53
Registrován: 3. 9. 2009 17:54
Typ studia: Informatika Mgr.

Re: Dotazy na grafové algoritmy

Příspěvek od Pitr2311 »

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
Pitr2311
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“