Ford-Fulkerson: iterativní augmentace (běh)
V [L4.2] Reziduální graf a augmentující cesta jsme na zkouškové síti z 25. 5. 2026 značkováním našli cestu $T_1 \to T_4 \to T_5 \to T_8$ s $\gamma = 4$ a zvedli tok z $|f| = 9$ na $13$. Dnes to dotáhneme: poběžíme dál, iteraci za iterací, až na maximum — přesně tak, jak to chce zkouškové zadání („Show the augmenting path in each iteration.“).
Algoritmus: tři řádky (slide 11)
Zkus sám: z [L4.2] umíš najít augmentující cestu (značkování), spočítat $\gamma$ a augmentovat. Sestav z těch dílů celý algoritmus pro maximální tok. Co potřebuješ na startu? A kdy se zastavíš?
Na startu potřebuješ nějaký přípustný tok — augmentace přípustnost jen udržuje, takže od něčeho přípustného musíš vyjít. Pak v cyklu: najdi augmentující cestu, spočti $\gamma$, augmentuj. Zastavíš se, když augmentující cesta neexistuje — podle kritéria maximality z [L4.2] je v tu chvíli tok maximální, takže pokračovat ani není kam.
Input: Network $(G, l, u, s, t)$.
Output: Maximum feasible flow $f$ from $s$ to $t$.
- Find the feasible flow $f(e)$ for all $e \in E(G)$.
- Find an augmenting path $P$. If none exists then stop.
- Compute $\gamma$, the capacity of an augmenting path $P$. Augment the flow from $s$ to $t$ and go to 2.
Krok za krokem česky:
- Krok 1 — startovní přípustný tok. Při $l \equiv 0$ stačí $f \equiv 0$; u zkoušky bývá přípustný tok rovnou zadaný (sloupek $f_e$ v popisku hrany). Když ale $l > 0$ a tok zadaný není, je už tenhle krok netriviální úloha sama o sobě — řeší ji [L4.7].
- Krok 2 — hledání cesty. Značkování z [L4.2], neboli dosažitelnost $s \to t$ v reziduálním grafu $G_f$.
- Krok 3 — augmentace. $+\gamma$ na dopředných, $-\gamma$ na zpětných hranách a zpátky na krok 2. Nic víc v algoritmu není — celá práce je v opakování.
Rozcvička: celý běh na malé síti (slide 13)
Slidy předvádějí běh na malé síti s nulovými dolními mezemi a nulovým startovním tokem (krok 1 je zadarmo). Proklikej si ho — sleduj, jak se hrany postupně nasycují a jak poslední iterace potřebuje jinou trasu než ty „přímočaré“:
Zkus sám: po třetí iteraci je $|f| = 13$ a všechny tři „přímé“ cesty ($s{\to}u{\to}t$, $s{\to}v{\to}t$, $s{\to}w{\to}t$) mají nasycenou hranu. Najdi v reziduálním grafu ještě jednu cestu $s \to t$.
Z $s$ má rezervu už jen $s \to v$ ($5 < 7$). Z $v$ je hrana $v \to t$ nasycená, ale vede odtud hrana $v \to u$ s rezervou $2$ — a z $u$… hrana $u \to t$ má rezervu $6 - 5 = 1$. Cesta $s \to v \to u \to t$ s $\gamma = \min\{2, 2, 1\} = 1$. Po ní je $|f| = 14$ a z $s$ sice ještě vede $s \to v$ (rezerva $1$), ale z $v$ už se dál nikam nedostaneš ($v \to t$ nasycená, $v \to u$ vede k nasycené $u \to t$ a zpětné hrany vracejí jen do už prozkoumaných vrcholů) — stop.
Stojí za to vidět, kolik tok stojí na volbě cest: čtyři iterace s $\gamma = 5, 5, 3, 1$. Slide na závěr poznamenává, že množina $A = \{s, u, v\}$ určuje minimum capacity cut — co to znamená a proč zaručuje, že $14$ je opravdu maximum, je obsah [L4.4].
Hlavní číslo: běh na zkouškové síti (25. 5. 2026)
Teď zkouškové zadání. Síť i startovní tok $|f| = 9$ známe z [L4.1], reziduální graf a první cestu z [L4.2]. Iterace 1 je tedy hotová — pokračujeme, dokud to jde.
Zkus sám (iterace 2): po augmentaci $T_1 \to T_4 \to T_5 \to T_8$ o $\gamma = 4$ je $f_{14} = 4$, $f_{45} = 4$, $f_{58} = 8$. Najdi další augmentující cestu a její $\gamma$.
Z $T_1$ vede v $G_f$ pořád jen $T_1 \to T_4$ (rezerva $7 - 4 = 3$). Hrana $T_5 \to T_8$ se nasytila, takže stará trasa už neprojde. Možnosti z $T_4$: krátká cesta $T_1 \to T_4 \to T_7 \to T_8$ s $\gamma = \min\{3,\ 1,\ 4 - 1\} = 1$, nebo delší $T_1 \to T_4 \to T_5 \to T_3 \to T_6 \to T_8$ přes zpětnou hranu $T_5 \to T_3$ s $\gamma = 3$. Obě jsou správně — vzorové řešení bere tu krátkou ($\gamma = 1$).
Zkus sám (iterace 3): po iteraci 2 je $f_{14} = 5$, $f_{47} = 1$, $f_{78} = 2$. Existuje ještě čistě dopředná cesta (všude $f < u$)? A znamená její neexistence konec?
Dopředně se z $T_1$ dostaneš jen do $T_4$ (rezerva $2$) a dál do $T_5$ (rezerva $4$) — ale $T_5 \to T_8$ je nasycená a $T_4 \to T_7$ taky. Čistě dopředná cesta neexistuje. Konec to ale neznamená: z $T_5$ vede zpětná hrana $T_5 \to T_3$ (kapacita $f_{35} - l_{35} = 4 - 1 = 3$) a z $T_3$ dopředně $T_3 \to T_6 \to T_8$. Cesta $T_1 \to T_4 \to T_5 \to T_3 \to T_6 \to T_8$, $\gamma = \min\{2, 4, 3, 6, 3\} = 2$.
Celý běh (popisek hrany $= l, f, u$, hodnoty se v každém kroku aktualizují):
Nebezpečná polopravda: „když nevidím dopřednou cestu, jsem hotov“Zastavovací podmínka je žádná cesta $s \to t$ v reziduálním grafu $G_f$ — tedy včetně zpětných hran. Kdo po iteraci 2 hledal jen dopředné cesty s $f < u$, skončil na $|f| = 14$ a dvě jednotky toku zahodil: iterace 3 vede přes zpětnou hranu $T_5 \to T_3$ a teprve po ní je tok $16$ maximální. Korektní zdůvodnění konce zní: všechny hrany ze zdroje jsou nasycené, takže z $T_1$ v $G_f$ nevede žádná hrana — to vylučuje dopředné i zpětné pokračování najednou.
Skončí to? A jak rychle? (slidy 17–18)
Zkus sám: kapacity i dolní meze jsou celá čísla a startovní tok taky. Kolik iterací může Ford-Fulkerson nejvýš udělat?
Každá iterace zvedne $|f|$ o $\gamma$, a $\gamma$ je při celočíselných datech celé číslo $\ge 1$ (minimum z celočíselných rezerv $u - f$ a $f - l$, které jsou na cestě kladné). Hodnota toku je shora omezená (třeba součtem kapacit hran ze zdroje, viz mez z [L4.1]), takže iterací je nejvýš $F$ = hodnota maximálního toku. Na zkouškové síti: start $9$, maximum $16$ — nejvýš $7$ iterací, nám stačily $3$, protože $\gamma$ byla větší než $1$.
If all capacities are integers, $\gamma$ in 3) of the Ford-Fulkerson algorithm is always an integer. Since there is a maximum flow of finite value, the algorithm terminates after a finite number of steps.
To find an augmenting path takes $\mathcal{O}(|E|)$ time.
For integer capacities, each iteration increases the flow by at least 1. Let $U$ be the highest edge capacity. The maximum number of iterations is equal to the volume of maximum flow $F = |E| \cdot U$ which is equal to the capacity of the minimum cut. Alg. complexity is $\mathcal{O}(|E| \cdot F) = \mathcal{O}(|E|^2 \cdot U)$.
For non-integer capacities and non-integer flow the algorithm might not terminate at all [Korte Vygen] Chapter Flows, Exercise 2.
Edmonds and Karp [1972]: When choosing the augmenting path, if we always choose the shortest one (e.g., by Breadth First Search), time complexity is $\mathcal{O}(|E|^2 \cdot |V|)$.
Česky a s drobným upřesněním: iterací je nejvýš $F$ (hodnota maximálního toku) a $F$ je nejvýš $|E| \cdot U$ — hrubě odhadnuto přes kapacity hran; každá iterace stojí $\mathcal{O}(|E|)$, dohromady $\mathcal{O}(|E| \cdot F) = \mathcal{O}(|E|^2 \cdot U)$. To je pseudopolynomiální mez — roste s velikostí kapacit $U$, ne jen s velikostí grafu. A není to planý strach: na následující síti (protipříklad ze slidu 18, za $U$ dosazujeme $100$) umí zlá volba cest protáhnout běh na $2U$ iterací:
Zkus sám: čím se zigzag liší od rozumného běhu? A jaká jednoduchá změna v kroku 2 ho vyloučí?
Zigzag pokaždé prochází hranou $u \to v$ s kapacitou $1$ (jednou dopředně, jednou zpětně), takže $\gamma = 1$ — a tok roste po kapkách. Rozumný běh vede obě cesty mimo ni a má hotovo za dvě iterace s $\gamma = U$. Léčba: v kroku 2 vybírat nejkratší augmentující cestu (BFS v $G_f$) — to je Edmonds-Karp; cesty $s{\to}u{\to}t$ a $s{\to}v{\to}t$ (2 hrany) pak vyhrají nad zigzagem (3 hrany) a obecně platí mez $\mathcal{O}(|E|^2 \cdot |V|)$, nezávislá na kapacitách.
Key takeaways — L4.3- Ford-Fulkerson = smyčka kolem augmentace: 1. sežeň přípustný tok ($f \equiv 0$ při $l \equiv 0$, u zkoušky zadán; jinak [L4.7]), 2. najdi augmentující cestu ([L4.2]), 3. pošli $\gamma$ a aktualizuj — $+\gamma$ na dopředných, $-\gamma$ na zpětných hranách — a zpět na 2.
- Konec: v reziduálním grafu už není cesta $s \to t$ (typicky: všechny hrany ze zdroje nasycené). Tok je pak maximální; zdůvodnění řezem a min-cut v [L4.4].
- Zkouškový běh 25. 5. 2026: start $|f| = 9$; ① $T_1{\to}T_4{\to}T_5{\to}T_8$, $\gamma = 4$; ② $T_1{\to}T_4{\to}T_7{\to}T_8$, $\gamma = 1$; ③ $T_1{\to}T_4{\to}T_5{\to}T_3{\to}T_6{\to}T_8$ přes zpětnou $T_5{\to}T_3$, $\gamma = 2$; výsledek $|f| = 16$.
- Složitost: celočíselné kapacity → $\gamma \ge 1$ → nejvýš $F$ iterací po $\mathcal{O}(|E|)$, tj. $\mathcal{O}(|E| \cdot F) = \mathcal{O}(|E|^2 \cdot U)$ — pseudopolynomiální (zigzag $2U$ iterací); neceločíselné kapacity: nemusí skončit vůbec. Edmonds-Karp (vždy nejkratší cesta, BFS) → $\mathcal{O}(|E|^2 \cdot |V|)$.
- U zkoušky vypiš každou iteraci: cestu, výpočet $\gamma$ jako minimum rezerv ($u - f$ dopředné, $f - l$ zpětné) a změněné toky.
a) Using Ford-Fulkerson alg. solve the maximum flow problem for the graph in the upper left corner (arc label is $l_e, f_e, u_e$, i.e., minimum capacity, feasible flow, maximum capacity). The source is $T_1$, the sink is $T_8$. Show the augmenting path in each iteration.
b) Determine the minimum capacity cut.
a) Co je v zadání?
Zkoušková síť (12 hran, tři s dolní mezí $l > 0$) se zadaným startovním přípustným tokem $|f| = 9$ — krok 1 algoritmu je tedy darovaný. Část a) chce běh Ford-Fulkersona s vypsanou augmentující cestou v každé iteraci; část b) minimální řez — ten patří do [L4.4], kde úloha pokračuje jako FOTO checkpoint celé kapitoly. Tady řešíme a).
b) Co k tomu budeme potřebovat?
- Tato lekce — smyčka algoritmu, zastavovací podmínka, zápis iterací (takeaways).
- [L4.2] — reziduální graf, augmentující cesta, $\gamma$ (a pozor na zpětnou kapacitu $f - l$).
- [L4.1] — čtení popisku $(l_e, f_e, u_e)$ a hodnota $|f|$.
c) Jak nad úlohou uvažovat?
V každé iteraci: (1) projdi v duchu reziduální graf od $T_1$ (které hrany mají $u - f > 0$, které zpětné mají $f - l > 0$); (2) jakmile dosáhneš $T_8$, vypiš cestu a $\gamma$ = minimum rezerv; (3) aktualizuj toky a hodnotu $|f|$. Klíčové pozorování: z $T_1$ vede po celou dobu jediná reziduální hrana $T_1 \to T_4$ (zbylé dvě hrany ze zdroje jsou nasycené od začátku) — všechno se odehrává za $T_4$. Konec nastane, až se nasytí i $T_1 \to T_4$.
d) Úplné řešení
Startovní tok: $|f| = f_{12} + f_{13} + f_{14} = 4 + 5 + 0 = 9$. Běh (vzorové řešení banky #21; v iteraci 3 je $T_5 \to T_3$ zpětná reziduální hrana původní hrany $T_3 \to T_5$):
| Iter. | Augmentující cesta v $G_f$ | $\gamma$ | Změněné toky |
|---|---|---|---|
| 1 | $T_1 \to T_4 \to T_5 \to T_8$ | $\min\{7, 8, 4\} = 4$ | $f_{14} = 4$, $f_{45} = 4$, $f_{58} = 8$ |
| 2 | $T_1 \to T_4 \to T_7 \to T_8$ | $\min\{3, 1, 3\} = 1$ | $f_{14} = 5$, $f_{47} = 1$, $f_{78} = 2$ |
| 3 | $T_1 \to T_4 \to T_5 \to T_3 \to T_6 \to T_8$ | $\min\{2, 4, 3, 6, 3\} = 2$ | $f_{14} = 7$, $f_{45} = 6$, $f_{35} = 2$, $f_{36} = 2$, $f_{68} = 6$ |
V iteraci 3 je třetí člen minima zpětná rezerva $f_{35} - l_{35} = 4 - 1 = 3$ (ne $4$!). Hodnota toku po třech augmentacích: $$|f| = 9 + 4 + 1 + 2 = 16.$$
Výsledné toky (vše v mezích $l \le f \le u$):
| hrana | 12 | 13 | 14 | 26 | 36 | 35 | 37 | 45 | 47 | 68 | 58 | 78 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $f$ | 4 | 5 | 7 | 4 | 2 | 2 | 1 | 6 | 1 | 6 | 8 | 2 |
Proč už žádná augmentující cesta není: po třetí augmentaci jsou všechny hrany ze zdroje nasycené ($f_{12} = u_{12} = 4$, $f_{13} = u_{13} = 5$, $f_{14} = u_{14} = 7$), takže z $T_1$ nevede v reziduálním grafu žádná hrana, $T_8$ je nedosažitelný a algoritmus končí. Podle kritéria maximality z [L4.2] je tok $|f| = 16$ maximální. (Jiná pořadí cest jsou také správně — třeba v iteraci 2 delší cesta s $\gamma = 3$; maximum vyjde vždy $16$, jen jiným počtem iterací. U zkoušky každou iteraci vypiš.)
Část b) — minimální řez — dořešíme v [L4.4]: vyjde přímo z množiny vrcholů označených v posledním (neúspěšném) značkování.
Pozn. ke zdrojům: dochovaný rukopisný přepis téhož zadání čte špatně čitelné indexy uzlů jinak (např. hrany $T_2 \to T_5$, $T_4 \to T_6$, $T_6 \to T_7$) a dochází k maximu $15$; držíme se konzistentního čtení banky #21 zavedeného v [L4.1] (diagonály $T_3{\to}T_7 = (0,1,1)$, $T_4{\to}T_5 = (0,0,8)$), které dává $16$.
Consider the network with nodes $s, u, v, t$ and arcs $s \to u$, $s \to v$, $u \to t$, $v \to t$, each with $l = 0$ and capacity $U$, and the arc $u \to v$ with $l = 0$ and capacity $1$. The initial flow is zero and $U$ is a large integer.
- Exhibit a sequence of augmenting path choices for which the Ford-Fulkerson algorithm performs $2U$ iterations.
- Exhibit a choice that finishes in 2 iterations.
- State the general bound on the number of iterations and the running time of Ford-Fulkerson for integer capacities, and explain how Edmonds and Karp choose the augmenting path and what bound this gives.
a) Co je v zadání?
Protipříklad ze slidu 18 — čtyři „tlusté“ hrany s kapacitou $U$ a jedna „tenká“ příčka $u \to v$ s kapacitou $1$. Máme ukázat, že počet iterací Ford-Fulkersona závisí na volbě cest: stejná síť snese běh za $2$ iterace i za $2U$ iterací.
b) Co k tomu budeme potřebovat?
- Tato lekce — smyčka algoritmu, meze $\mathcal{O}(|E| \cdot F)$ a Edmonds-Karp (takeaways).
- [L4.2] — zpětná hrana v reziduálním grafu (zigzag ji potřebuje).
c) Jak nad úlohou uvažovat?
(i) Jak donutit $\gamma = 1$ v každé iteraci? Cesta musí obsahovat příčku $u \to v$ — jednou dopředně, podruhé zpětně, aby se kapacita příčky pořád „resetovala“. (ii) Které dvě cesty se příčce vyhnou úplně? (iii) Porovnej délky cest: zigzag má 3 hrany, přímé cesty 2 — co z toho plyne pro pravidlo „ber nejkratší“?
d) Úplné řešení
(i) Střídej cesty $P_1 = s \to u \to v \to t$ a $P_2 = s \to v \to u \to t$, kde $P_2$ prochází příčku $u \to v$ zpětně. Na $P_1$ je $\gamma = \min\{U - f_{su},\ 1 - f_{uv},\ U - f_{vt}\} = 1$ (příčka). Augmentací se příčka nasytí ($f_{uv} = 1$). Na $P_2$ je $\gamma = \min\{U - f_{sv},\ f_{uv} - 0,\ U - f_{ut}\} = 1$ (zpětná rezerva příčky) a augmentace ji zase vyprázdní ($f_{uv} = 0$). Každá iterace zvedne $|f|$ přesně o $1$ a maximum je $F = 2U$ (víc se přes $\{s\}$ nevejde: $U + U$) — celkem $2U$ iterací. Běh prvních iterací je proklikatelný ve výkladu výše.
(ii) Cesty $s \to u \to t$ ($\gamma = U$) a $s \to v \to t$ ($\gamma = U$): po dvou iteracích $|f| = 2U$, všechny hrany ze zdroje nasycené → stop. Tok je stejný, práce stokrát menší (2 vs. 200 iterací).
(iii) Pro celočíselné kapacity zvedne každá iterace tok aspoň o $1$, takže iterací je nejvýš $F$; nalezení cesty stojí $\mathcal{O}(|E|)$, celkem $\mathcal{O}(|E| \cdot F) = \mathcal{O}(|E|^2 \cdot U)$ — pseudopolynomiálně (slide 18; pro neceločíselné kapacity nemusí algoritmus skončit vůbec). Edmonds a Karp [1972]: v kroku 2 vždy vybrat nejkratší augmentující cestu (počtem hran, tj. BFS v reziduálním grafu) — pak je složitost $\mathcal{O}(|E|^2 \cdot |V|)$ nezávisle na velikosti kapacit. Tady BFS najde dvouhranové cesty $s{\to}u{\to}t$, $s{\to}v{\to}t$ dřív než tříhranový zigzag, takže zlý běh vůbec nenastane.