Reziduální graf a augmentující cesta
V [L4.1] Síť, tok, Kirchhoffův zákon jsme na zkouškové síti z 25. 5. 2026 ověřili, že zadané $f$ je přípustný tok s hodnotou $|f| = 9$, a bez počítání odvodili mez $|f| \le 16$. Mezi 9 a 16 je propast — dnes si postavíme nástroj, kterým se tok vylepšuje. Ford-Fulkersonův algoritmus, který ho v [L4.3] bude opakovat v cyklu, pak už bude jen jednověté „opakuj, dokud to jde“.
První nápad: protlačit víc po cestě s rezervou
Zkus sám: najdi na zkouškové síti (obrázek v [L4.1], popisek hrany $= l_e, f_e, u_e$) orientovanou cestu z $T_1$ do $T_8$, na které má každá hrana rezervu $f(e) < u(e)$. O kolik můžeš tok podél ní zvýšit, aby zůstal přípustný? A nerozbije se Kirchhoffův zákon?
Z $T_1$ mají rezervu jen hrany do $T_4$ ($0 < 7$): cesta $T_1 \to T_4 \to T_5 \to T_8$ má rezervy $7 - 0 = 7$, $8 - 0 = 8$ a $8 - 4 = 4$. Zvýšit můžeš o minimum rezerv, tedy o $4$: nový tok $f_{14} = 4$, $f_{45} = 4$, $f_{58} = 8$ a $|f| = 9 + 4 = 13$. Kirchhoff přežije: každý vnitřní vrchol cesty ($T_4$, $T_5$) dostal $+4$ na vstupu i $+4$ na výstupu.
Nápad funguje: orientovaná cesta $s \to t$, kde všude $f(e) < u(e)$, snese zvýšení o minimum rezerv a tok zůstane tokem. Kdyby tohle stačilo vždycky, byli bychom hotovi. Jenže…
Kde se dopředný nápad zasekne
Podívej se na následující síť s tokem (vlastní minimální příklad; popisek hrany $= l_e, f_e, u_e$):
Zkus sám: najdi v téhle síti orientovanou cestu $s \to t$, kde má každá hrana $f < u$.
Žádná není. Kandidáti jsou tři: $s \to a \to t$ (hrana $s \to a$ je nasycená, $1 = u$), $s \to b \to t$ (hrana $b \to t$ je nasycená) a $s \to a \to b \to t$ (nasycená už $s \to a$). Dopředný nápad je v koncích.
Zkus sám: znamená to, že tok $|f| = 1$ je maximální? (Zkus tok navrhnout úplně od nuly.)
Neznamená! Tok $f(s,a) = f(a,t) = 1$, $f(s,b) = f(b,t) = 1$, $f(a,b) = 0$ je přípustný a má hodnotu $2$. Porovnej ho s tím zaseknutým: liší se právě tím, že po hraně $a \to b$ teče míň. Vylepšovací krok tedy musí umět tok nejen přidávat, ale i ubírat — poslat zpět. Jednotka, která z $a$ odtékala do $b$, se „přesměruje“ do $t$, a uvolněné místo v $b \to t$ zaplní nová jednotka po $s \to b$.
Přesně tohle „ubírání po cestě“ formalizují slidy: cesta z $s$ do $t$ nemusí respektovat orientaci hran — některé hrany projde po směru, jiné proti směru.
Forward a backward hrana, augmentující cesta (slide 10)
It is based on incremental augmentation of the flow along an oriented path while maintaining the flow's feasibility. The path from source $s$ to sink $t$ does not respect orientation of arcs.
Forward arc and backward arc: An arc is called a forward arc if it is oriented in the same direction as the path from $s$ to $t$ and a backward arc otherwise.
Augmenting path: An augmenting path for flow $f$ is a path from $s$ to $t$ with:
- $f(e) < u(e)$ for all forward arcs on the path … $f(e)$ can be increased
- $f(e) > l(e)$ for all backward arcs on the path … $f(e)$ can be decreased
Capacity of an augmenting path: Capacity $\gamma = \min\{\min_{e \text{ is forward}} u(e) - f(e),\ \min_{e \text{ is backward}} f(e) - l(e)\}$ is the biggest possible increase of the flow on the augmenting path.
Česky: augmenting path (augmentující cesta) pro tok $f$ je posloupnost hran vedoucí z $s$ do $t$, kde hrany procházené po směru (forward, dopředné) mají rezervu $f < u$ a hrany procházené proti směru (backward, zpětné) mají co vracet: $f > l$. Kapacita cesty $\gamma$ = nejmenší z rezerv $u - f$ (dopředné) a $f - l$ (zpětné) — o tolik nejvýš lze tok podél cesty zvednout.
Zkus sám: v zaseknuté síti vezmi posloupnost $s \to b$, pak hranu $a \to b$ proti směru, pak $a \to t$. Které hrany jsou forward, které backward, je to augmentující cesta a jaké má $\gamma$?
$s \to b$ a $a \to t$ jdou po směru — forward; $a \to b$ procházíme z $b$ do $a$, tedy proti směru — backward. Podmínky: $f(s,b) = 0 < 1 = u$ ✓, $f(a,b) = 1 > 0 = l$ ✓, $f(a,t) = 0 < 1 = u$ ✓ — je to augmentující cesta. Kapacita $\gamma = \min\{1 - 0,\ 1 - 0,\ 1 - 0\} = 1$.
A co se po nalezení cesty stane? Slide 11 (zbytek slidu — celý algoritmus — si necháme do [L4.3]):
Increase of the flow by $\gamma$ on forward arcs and decrease of the flow by $\gamma$ on backward arcs - this preserves feasibility of the flow and Kirchhof's law moreover the flow is augmented by $\gamma$. This augmenting path can't be used again since the flow along this path is the highest possible.
Zkus sám: proč augmentace nerozbije Kirchhoffův zákon? Cesta může vnitřním vrcholem $v$ projít čtyřmi způsoby (vejít dopřednou/zpětnou hranou × odejít dopřednou/zpětnou). Projdi všechny čtyři případy.
Sleduj bilanci vrcholu $v$ (vstup minus výstup):
- forward dovnitř + forward ven: vstup $+\gamma$, výstup $+\gamma$ — bilance beze změny. ✓
- forward dovnitř + backward ven: „odchozí“ zpětná hrana je ve skutečnosti orientovaná do $v$ a tok na ní klesá; vstup se změní o $+\gamma - \gamma = 0$. ✓
- backward dovnitř + forward ven: „příchozí“ zpětná hrana je orientovaná z $v$ a klesá; výstup se změní o $-\gamma + \gamma = 0$. ✓
- backward dovnitř + backward ven: vstup $-\gamma$, výstup $-\gamma$. ✓
Meze hlídá přímo volba $\gamma$ (nikde nepřeteče přes $u$ ani neklesne pod $l$) a hodnota $|f|$ vzroste o $\gamma$, protože první hrana cesty vychází z $s$ (dopředná zvyšuje odtok z $s$; zpětná první hrana by snižovala přítok do $s$ — obojí zvedne čistý odtok).
Celá záchranná akce na zaseknuté síti, krok za krokem:
Reziduální graf: obě rezervy jako jeden graf (slide 32)
„Cesta, která nerespektuje orientaci hran“ se nepohodlně hledá i zapisuje. Slidy proto zavádějí elegantní převlek: místo abychom chodili proti šipkám, nakreslíme rezervy jako nové šipky. Definice na slidu 32 sedí v přednášce až u minimum cost flow, proto obsahuje i ceny $c_f$ — ty využije až [L4.10], my dnes potřebujeme kapacitní část (a balance $b$ dnes nemáme žádné):
The residual graph shows where an extra capacity might be found. The residual graph $G_f$ is constructed from network $(G, l, u, b, c)$ and specific feasible flow $f$ as follows:
$$ \begin{aligned} G_f &= (V, E_f, u_f, c_f) \\ \bar{E} &= E \cup \{(j, i) : (i, j) \in E\} \\ u_f(i, j) &= u(i, j) - f(i, j) & \forall (i, j) \in E \\ u_f(j, i) &= f(i, j) - l(i, j) & \forall (i, j) \in E \\ E_f &= \{(i, j) \in \bar{E} : u_f(i, j) > 0\} \\ c_f(i, j) &= c(i, j) & \forall (i, j) \in E \\ c_f(j, i) &= -c(i, j) & \forall (i, j) \in E \end{aligned} $$
Česky: každá hrana $(i,j)$ původní sítě vyrobí v $G_f$ až dvě hrany — dopřednou $(i,j)$ s reziduální kapacitou $u_f = u - f$ (kolik lze ještě přidat) a zpětnou $(j,i)$ s $u_f = f - l$ (kolik lze vrátit). Hrany s nulovou reziduální kapacitou se vynechají. První věta slidu je celá pointa: reziduální graf ukazuje, kde se dá najít extra kapacita — vpřed i vzad.
Zkus sám: přečti teď definici augmentující cesty znovu, ale v řeči $G_f$. Čím je augmentující cesta v reziduálním grafu? A čím je $\gamma$?
Augmentující cesta = obyčejná orientovaná cesta $s \to t$ v $G_f$. Podmínka $f < u$ na dopředné hraně říká přesně „dopředná reziduální hrana existuje“, podmínka $f > l$ na zpětné říká „zpětná reziduální hrana existuje“. Všechno nepohodlí s „cestou proti šipkám“ zmizelo — v $G_f$ se jde normálně po šipkách. A $\gamma$ je prostě minimum reziduálních kapacit $u_f$ podél cesty.
Reziduální graf zaseknuté sítě (popisek hrany $= u_f$). Srovnej s obrázkem výše — augmentující cesta, kterou jsme pracně skládali z dopředných a zpětných hran, je tady obyčejná orientovaná cesta:
Nebezpečná polopravda: „zpětná hrana má kapacitu $f(e)$“Zpětná reziduální kapacita je $f(e) - l(e)$, ne $f(e)$ — vrátit smíš jen to, co je nad dolní mezí. Při $l \equiv 0$ obojí splývá, ale zkoušková síť z 25. 5. 2026 má tři hrany s $l > 0$ a na jedné z nich to bolí: hrana $T_7 \to T_8$ nese $(l, f, u) = (1, 1, 4)$, tok $f = 1$ je kladný, a přesto zpětná hrana $T_8 \to T_7$ v $G_f$ neexistuje, protože $u_f = f - l = 0$. Podobně zpětná hrana $T_3 \to T_1$ má kapacitu $5 - 2 = 3$, ne $5$.
Reziduální graf zkouškové sítě
Tady je $G_f$ pro zkouškovou síť a její startovní tok $|f| = 9$ z [L4.1] (popisek hrany $= u_f$; zvýrazněná je augmentující cesta ze začátku lekce):
Zkus sám: kudy všudy vedou augmentující cesty? Čím musí každá začínat a jaká je $\gamma$ té zvýrazněné?
Z $T_1$ vede v $G_f$ jediná hrana, $T_1 \to T_4$ s $u_f = 7$ (hrany do $T_2$ a $T_3$ jsou nasycené, takže dopředné reziduální hrany nemají) — každá augmentující cesta začíná $T_1 \to T_4$. Zvýrazněná cesta $T_1 \to T_4 \to T_5 \to T_8$ má $\gamma = \min\{7, 8, 4\} = 4$. Další možnosti: $T_1 \to T_4 \to T_7 \to T_8$ s $\gamma = \min\{7, 1, 3\} = 1$, nebo přes zpětnou hranu $T_5 \to T_3$: $T_1 \to T_4 \to T_5 \to T_3 \to T_6 \to T_8$ s $\gamma = \min\{7, 8, 3, 6, 3\} = 3$. Které pořadí vybrat a jak iterovat až k maximu — to je [L4.3].
Jak cestu najít: značkování (slide 12)
Na malé síti cestu uvidíš okem. Slidy ale dávají i mechanický postup — labeling procedure (značkovací proceduru), která je přesně prohledáváním dosažitelnosti v $G_f$, jen zapsaným na původní síti:
Input: Network $(G, l, u, s, t)$, feasible flow $f$. Output: Augmenting path $P$ or decide it does not exist.
- Label $m_s = TRUE$, $m_v = FALSE\ \forall v \in V(G) \setminus s$.
- If there exists $e \in E(G)$ (where $e$ is the edge from $v_i$ to $v_j$) that satisfies $m_i = TRUE$, $m_j = FALSE$ and $f(e) < u(e)$ Then $m_j = TRUE$.
- If there exists $e \in E(G)$ (where $e$ is the edge from $v_i$ to $v_j$) that satisfies $m_i = FALSE$, $m_j = TRUE$ and $f(e) > l(e)$ Then $m_i = TRUE$.
- If $t$ is reached, then the search stops as we have found the augmenting path $P$. If it is not possible to mark another node, then $P$ does not exists. In other cases go to step 2.
Zkus sám: krok 3 vypadá zvláštně — hrana vede z $v_i$ do $v_j$, ale značku dostává $v_i$. Který pojem z téhle lekce krok 3 realizuje?
Zpětnou hranu. Krok 2 šíří značku po dopředné reziduální hraně ($f < u$, jdu po směru), krok 3 po zpětné ($f > l$, jdu proti směru hrany — z jejího konce $v_j$ na začátek $v_i$). Dohromady je to obyčejné šíření „vlny“ dosažitelnosti z $s$ v reziduálním grafu $G_f$ — stejná vlna jako BFS v [L2.10], jen nad $G_f$.
Běh značkování na zkouškové síti (popisek hrany $= l, f, u$; pod označeným vrcholem svítí TRUE):
Co když se vlna zastaví a $t$ značku nedostane? Pak augmentující cesta neexistuje — a slide 11 k tomu říká větu, která je srdcem celé kapitoly:
The flow from $s$ to $t$ is the maximum if and only if there is no augmenting path.
Směr „maximální ⇒ žádná cesta“ je snadný (cesta by tok zvedla o $\gamma > 0$). Opačný směr dokáže až řez: množina označených vrcholů v posledním, neúspěšném značkování vytvoří minimální řez — to je obsah [L4.4]. V [L4.3] zatím kritérium použijeme jako zastavovací podmínku Ford-Fulkersona.
Key takeaways — L4.2- Forward hrana (po směru cesty): tok lze přidat, pokud $f(e) < u(e)$; backward hrana (proti směru): tok lze ubrat (poslat zpět), pokud $f(e) > l(e)$.
- Augmentující cesta pro $f$ = cesta $s \to t$ nerespektující orientaci, kde dopředné hrany mají $f < u$ a zpětné $f > l$; její kapacita $\gamma = \min\{\min_{\text{fwd}} u(e) - f(e),\ \min_{\text{bwd}} f(e) - l(e)\}$.
- Reziduální graf $G_f$: dopředná hrana s $u_f = u - f$, zpětná s $u_f = f - l$, nulové se vynechají. Augmentující cesta = obyčejná orientovaná cesta $s \to t$ v $G_f$, $\gamma$ = minimum $u_f$ podél ní.
- Augmentace: $+\gamma$ na dopředných, $-\gamma$ na zpětných hranách — zachová přípustnost i Kirchhoffa a zvedne $|f|$ o $\gamma$.
- Pozor: zpětná kapacita je $f - l$, ne $f$ — při $l > 0$ může zpětná hrana chybět i při kladném toku (na zkouškové síti $T_8 \to T_7$).
- Hledání cesty = značkování (vlna dosažitelnosti z $s$ v $G_f$; krok 2 = dopředné, krok 3 = zpětné hrany). Tok je maximální ⟺ augmentující cesta neexistuje — zastavovací podmínka [L4.3], důkaz řezem [L4.4].
Consider the flow network from the exam of May 25, 2026 (see the figure in [L4.1]; arc label is $l_e, f_e, u_e$, the source is $T_1$, the sink is $T_8$) together with the prescribed feasible flow $f$, $|f| = 9$.
- Construct the residual graph $G_f$ (list all residual arcs with their residual capacities $u_f$).
- Find an arc of $G$ carrying positive flow $f(e) > 0$ whose backward residual arc is missing in $G_f$. Explain.
- Find an augmenting path and its capacity $\gamma$.
a) Co je v zadání?
Zkoušková síť s 12 hranami a startovním tokem $|f| = 9$ (přípustnost jsme ověřili v [L4.1] T01). Máme mechanicky postavit $G_f$ — pro každou hranu spočíst obě reziduální kapacity a nulové vyhodit — a pak v něm najít orientovanou cestu $T_1 \to T_8$. Přesně tohle je přípravný krok každé iterace Ford-Fulkersona, takže si tu předpočítáváme první iteraci pro [L4.3].
b) Co k tomu budeme potřebovat?
- Tato lekce — definice $G_f$, augmentující cesta, $\gamma$ (takeaways).
- [L4.1] — čtení popisku $(l_e, f_e, u_e)$ a samotná síť.
c) Jak nad úlohou uvažovat?
(i) Jdi hranu po hraně: dopředná kapacita $u - f$, zpětná $f - l$, nuly škrtej. (ii) Kdy je $f > 0$, ale $f - l = 0$? Které hrany sítě mají $l > 0$? (iii) Kolik hran vychází v $G_f$ z $T_1$? To ti řekne, kudy každá augmentující cesta musí začít.
d) Úplné řešení
(i) Dopředné reziduální hrany ($u_f = u - f > 0$):
$T_1{\to}T_4$: $7$; $T_2{\to}T_6$: $3$; $T_3{\to}T_6$: $6$; $T_4{\to}T_5$: $8$; $T_4{\to}T_7$: $1$; $T_5{\to}T_8$: $4$; $T_6{\to}T_8$: $3$; $T_7{\to}T_8$: $3$.
Zpětné reziduální hrany ($u_f = f - l > 0$):
$T_2{\to}T_1$: $4$; $T_3{\to}T_1$: $5 - 2 = 3$; $T_6{\to}T_2$: $4$; $T_5{\to}T_3$: $4 - 1 = 3$; $T_7{\to}T_3$: $1$; $T_8{\to}T_5$: $4$; $T_8{\to}T_6$: $4$.
Vynechané dopředné (nasycené hrany, $f = u$): $T_1{\to}T_2$, $T_1{\to}T_3$, $T_3{\to}T_5$, $T_3{\to}T_7$. Vynechané zpětné ($f = l$): $T_1{\to}T_4$, $T_3{\to}T_6$, $T_4{\to}T_5$, $T_4{\to}T_7$ (vše $f = 0$) a $T_7{\to}T_8$ ($f = l = 1$). Celkem má $G_f$ 15 hran — nakreslený je ve výkladu výše.
(ii) Hrana $T_7 \to T_8$: nese kladný tok $f = 1$, ale $u_f(T_8, T_7) = f - l = 1 - 1 = 0$, takže zpětná hrana $T_8 \to T_7$ v $G_f$ není. Vrátit jde jen tok nad dolní mezí — a tady je celý tok „přibitý“ povinným minimem $l = 1$. (To je přesně polopravda z danger boxu: kapacita zpětné hrany není $f$, ale $f - l$.)
(iii) Z $T_1$ vede v $G_f$ jediná hrana $T_1 \to T_4$, takže každá augmentující cesta začíná $T_1 \to T_4$. Například $$T_1 \to T_4 \to T_5 \to T_8, \qquad \gamma = \min\{7,\ 8,\ 4\} = 4.$$ Augmentací vznikne tok $|f| = 13$ ($f_{14} = 4$, $f_{45} = 4$, $f_{58} = 8$) — to bude 1. iterace vzorového běhu Ford-Fulkersona v [L4.3]. (Jiné správné odpovědi: $T_1 \to T_4 \to T_7 \to T_8$ s $\gamma = 1$, nebo $T_1 \to T_4 \to T_5 \to T_3 \to T_6 \to T_8$ s $\gamma = 3$ přes zpětnou hranu $T_5 \to T_3$.)
Consider the small network from [L4.1] with the feasible flow shown below (arc label is $l_e, f_e, u_e$), $|f| = 4$.
- Construct the residual graph $G_f$.
- Explain why the sequence $s \to b$, then arc $a \to b$ traversed backwards, then $a \to t$ is not an augmenting path.
- Find an augmenting path, compute $\gamma$, augment the flow and argue that the resulting flow is maximum.
a) Co je v zadání?
Známá síť z [L4.1] — čtyři vrcholy, pět hran, jedna hrana s dolní mezí $l(a,b) = 1$. Tok $|f| = 4$ je přípustný (ověřeno v [L4.1]). Máme postavit reziduální graf, vysvětlit jednu past se zpětnou hranou a tok doaugmentovat na maximum.
b) Co k tomu budeme potřebovat?
- Tato lekce — $G_f$, augmentující cesta, $\gamma$, kritérium maximality (takeaways).
- [L4.1] — hodnota toku a horní mez přes hrany ze zdroje.
c) Jak nad úlohou uvažovat?
(i) Pět hran × dvě reziduální kapacity, škrtni nuly. (ii) U hrany $a \to b$ spočti $f - l$; a i kdyby zpětná hrana existovala, prošla by cesta dál přes $a \to t$? (iii) Po augmentaci se podívej na hrany vycházející z $s$ — co říká mez z [L4.1] T01 (iii)?
d) Úplné řešení
(i) Po hranách ($u_f$ dopředná / zpětná, nuly škrtáme):
- $s \to a$ $(0,3,3)$: dopředná $0$ — není; zpětná $a \to s$: $3$.
- $s \to b$ $(0,1,2)$: dopředná $1$; zpětná $b \to s$: $1$.
- $a \to b$ $(1,1,2)$: dopředná $1$; zpětná $b \to a$: $f - l = 0$ — není.
- $a \to t$ $(0,2,2)$: dopředná $0$ — není; zpětná $t \to a$: $2$.
- $b \to t$ $(0,2,3)$: dopředná $1$; zpětná $t \to b$: $2$.
$G_f$ má tedy hrany: $s{\to}b\,(1)$, $a{\to}b\,(1)$, $b{\to}t\,(1)$, $a{\to}s\,(3)$, $b{\to}s\,(1)$, $t{\to}a\,(2)$, $t{\to}b\,(2)$.
(ii) Hned ze dvou důvodů. Zpětný průchod hranou $a \to b$ vyžaduje $f > l$, ale $f(a,b) = 1 = l(a,b)$ — tok je na dolní mezi a nic vracet nesmí (v $G_f$: hrana $b \to a$ chybí). A nezávisle na tom je hrana $a \to t$ nasycená ($f = u = 2$), takže by cesta neprošla ani posledním krokem. (Pozor: kdyby ses řídil polopravdou „zpětná kapacita $= f$“, první důvod bys přehlédl.)
(iii) V $G_f$ vede z $s$ jediná hrana $s \to b$ a z $b$ dál do $t$ hrana $b \to t$: $$s \to b \to t, \qquad \gamma = \min\{1,\ 1\} = 1.$$ (Obě hrany jsou dopředné — augmentující cesta zpětnou hranu mít může, ne musí.) Augmentace: $f(s,b) = 2$, $f(b,t) = 3$, ostatní beze změny; $|f| = 5$. Teď jsou obě hrany ze zdroje nasycené ($f_{sa} = 3 = u$, $f_{sb} = 2 = u$), takže z $s$ v novém $G_f$ nevede žádná hrana — augmentující cesta neexistuje a podle kritéria maximality (slide 11) je tok maximální. Sedí to i s mezí z [L4.1]: $|f| \le u(s,a) + u(s,b) = 5$ a hodnoty $5$ jsme dosáhli. $\blacksquare$