Řez a věta max-flow/min-cut [FOTO]
V [L4.3] Ford-Fulkerson: iterativní augmentace (běh) jsme na zkouškové síti z 25. 5. 2026 dotáhli tok na $|f| = 16$ a skončili, protože už neexistovala augmentující cesta. Zkouškové zadání ale pokračuje: „b) Determine the minimum capacity cut.“ Dnes zjistíš, co to je, proč je to certifikát maximality — a že na konci běhu ho máš vlastně už v ruce. Lekce končí FOTO checkpointem celé kapitoly.
Řez: hrdlo sítě (slide 15)
Zkus sám: chceš kamarádovi dokázat, že přes zkouškovou síť víc než 16 prostě nepoteče — bez přehrávání celého běhu algoritmu. Jaký nejstručnější argument tě napadá?
Ukázat hrdlo: množinu hran, přes kterou musí projít všechno, co teče z $T_1$ do $T_8$, a jejíž celková propustnost je $16$. Tady se nabízejí rovnou hrany ze zdroje: $u_{12} + u_{13} + u_{14} = 4 + 5 + 7 = 16$ — každá jednotka toku zdroj opouští některou z nich, takže $|f| \le 16$. A protože tok hodnoty $16$ existuje (našli jsme ho), je maximální. Tomuhle hrdlu se říká řez.
Cut - given by edge set $\delta(A)$ given by vertex set $A$. The cut in $G$ is an edge set $\delta(A) = \delta^+(A) \cup \delta^-(A)$ with $s \in A$ and $t \in V(G) \setminus A$ (i.e. the cut separates nodes $s$ and $t$). The minimum cut is the cut of minimum capacity $C(A) = \sum_{e \in \delta^+(A)} u(e) - \sum_{e \in \delta^-(A)} l(e)$.
Česky: cut (řez) vybereš tak, že vybereš množinu vrcholů $A$ obsahující zdroj, ale ne stok. Řez pak tvoří hrany, které hranici $A$ překračují: $\delta^+(A)$ ven z $A$, $\delta^-(A)$ dovnitř. Hrany s oběma konci uvnitř (nebo oběma vně) do řezu nepatří. Kapacita řezu sčítá horní meze výstupních hran a odečítá dolní meze vstupních:
Zkus sám: proč se $l(e)$ vstupních hran v kapacitě řezu odečítá? (Vzpomeň si, co dolní mez vynucuje pro každý přípustný tok.)
Vstupní hrana $e \in \delta^-(A)$ musí v každém přípustném toku nést aspoň $f(e) \ge l(e)$ — tedy aspoň $l(e)$ jednotek se vrací dovnitř $A$ a o to méně může být čistý odtok z $A$ směrem k $t$. Hrdlo $A$ tak reálně propustí nejvýš „všechno ven na maximum, minus co se povinně vrací“: $\sum_{\delta^+} u - \sum_{\delta^-} l$. Při $l \equiv 0$ se člen ztrácí a kapacita řezu je prostě součet kapacit výstupních hran.
Každý řez je strop pro každý tok
Zkus sám: z [L4.1] víš, že hodnotu toku lze měřit na libovolné množině $A \ni s$, $t \notin A$: $\;|f| = \sum_{e \in \delta^+(A)} f(e) - \sum_{e \in \delta^-(A)} f(e)$. Dosaď meze $l \le f \le u$ a uvidíš, co z toho vypadne.
Na výstupních hranách zvětši $f(e)$ na $u(e)$, na vstupních zmenši $f(e)$ na $l(e)$ — obojí pravou stranu jen zvedne: $$|f| = \sum_{e \in \delta^+(A)} f(e) - \sum_{e \in \delta^-(A)} f(e) \;\le\; \sum_{e \in \delta^+(A)} u(e) - \sum_{e \in \delta^-(A)} l(e) = C(A).$$ Tedy každý přípustný tok ≤ kapacita každého řezu (slabá dualita). Speciálně: maximální tok ≤ minimální řez.
Tohle už jsi mimochodem jednou použil: „meze“ $16$ a $19$ z [L4.1] nebyly nic jiného než kapacity dvou konkrétních řezů zkouškové sítě — zdrojového $A = \{T_1\}$ ($4+5+7 = 16$) a stokového $A = V \setminus \{T_8\}$ ($7+8+4 = 19$). Slabá dualita říká: kterýkoli řez, který napíšeš, je platný strop. Otázka dne zní: dotkne se nejlepší tok nejlepšího stropu?
Zkus sám: kdy v odhadu výše nastane rovnost $|f| = C(A)$?
Přesně tehdy, když ani jedno zaokrouhlení nic nezměnilo: $f(e) = u(e)$ na všech výstupních hranách ($\delta^+(A)$ nasycené) a $f(e) = l(e)$ na všech vstupních ($\delta^-(A)$ na dolní mezi). Pokud takovou dvojici (tok, řez) najdeš, je tok automaticky maximální a řez minimální — nic lepšího se mezi strop a podlahu nevejde.
Věta max-flow/min-cut — a kde tu rovnost vzít (slide 15)
The value of the maximum flow from $s$ to $t$ is equal to the capacity of the minimum cut, i.e., $$\sum_{e \in \delta^+(A)} f(e) - \sum_{e \in \delta^-(A)} f(e) = \sum_{e \in \delta^+(A)} u(e) - \sum_{e \in \delta^-(A)} l(e).$$
This property follows from LP duality. When the labeling procedure stops, since there is no augmenting path, the minimum cut is given by the labeled vertices (the minimum cut is equal to the set of edges that do not allow further labeling). Therefore, $f(e) = u(e)$ holds for all $e \in \delta^+(A)$ and $f(e) = l(e)$ holds for all $e \in \delta^-(A)$.
Slidy se odvolávají na LP dualitu (max-flow LP znáš z [L4.1]), ale druhá půlka boxu skrývá konstruktivní argument, který u zkoušky reálně použiješ. Rozbal si ho sám:
Zkus sám: Ford-Fulkerson skončil — značkování z [L4.2] nedosáhlo $t$. Vezmi $A$ = množinu označených vrcholů. Proč je každá hrana $e \in \delta^+(A)$ nasycená a každá $e \in \delta^-(A)$ na dolní mezi?
Kdyby výstupní hrana $e$ z označeného $v_i$ do neoznačeného $v_j$ měla $f(e) < u(e)$, pravidlo 2 značkování by $v_j$ označilo — spor s tím, že značkování skončilo. Stejně tak kdyby vstupní hrana z neoznačeného $v_i$ do označeného $v_j$ měla $f(e) > l(e)$, pravidlo 3 označí $v_i$. Takže po zastavení: $f = u$ na celém $\delta^+(A)$ a $f = l$ na celém $\delta^-(A)$ — přesně podmínka rovnosti z minulé sekce. Proto $|f| = C(A)$, tok je maximální a $A$ určuje minimální řez. (A protože $s$ je označený vždy a $t$ označený není — jinak by existovala augmentující cesta — je $A$ opravdu řez.)
Tím je věta dokázaná „přes algoritmus“: slabá dualita dává $\le$ a poslední značkování vyrábí dvojici s rovností. Prakticky to znamená recept na zkouškové b):
Recept: minimální řez po skončení Ford-Fulkersona- Doběhni Ford-Fulkerson [L4.3] — poslední pokus o značkování selže.
- $A$ = vrcholy, které poslední značkování stihlo označit (vždy aspoň $\{s\}$).
- Min řez $= \delta(A)$; vypiš $\delta^+(A)$ (a případné $\delta^-(A)$) a spočti $C(A) = \sum_{\delta^+} u - \sum_{\delta^-} l$.
- Kontrola: musí vyjít $C(A) = |f|$. Když nevyjde, je chyba v běhu nebo ve čtení hran.
Dvakrát naživo: malá síť a zkoušková síť
Nejdřív malá síť ze slidu 13 — běh skončil v [L4.3] na $|f| = 14$ a slide tvrdí: „set $A = \{s, u, v\}$ determines the minimum capacity cut“. Proklikej si, jak k té množině dojde poslední značkování:
A teď hlavní číslo — zkoušková síť 25. 5. 2026 po skončení běhu z [L4.3] ($|f| = 16$):
Nebezpečná polopravda: „minimální řez = nasycené hrany“Na hranách min řezu sice platí $f = u$, ale obráceně to neplatí: nasycených hran bývá víc, než kolik jich řez tvoří. Ve zkouškové síti je na konci nasyceno šest hran ($T_1{\to}T_2$, $T_1{\to}T_3$, $T_1{\to}T_4$, $T_3{\to}T_7$, $T_4{\to}T_7$, $T_5{\to}T_8$ — součet kapacit $26$), ale minimální řez tvoří jen tři z nich s $C(A) = 16$. Řez je vždy $\delta(A)$ pro nějakou množinu vrcholů $A$ — vypiš $A$ z posledního značkování, nehledej ho „očima“ podle nasycenosti. A nezapomeň na druhou past: u sítí s $l > 0$ se dolní meze vstupních hran odečítají.
Key takeaways — L4.4- Řez (cut): množina vrcholů $A$, $s \in A$, $t \notin A$; hrany řezu $\delta(A) = \delta^+(A) \cup \delta^-(A)$; kapacita $C(A) = \sum_{e \in \delta^+(A)} u(e) - \sum_{e \in \delta^-(A)} l(e)$ — dolní meze vstupních hran se odečítají.
- Slabá dualita: $|f| \le C(A)$ pro každý tok a každý řez (rovnost z [L4.1] + meze $l \le f \le u$). Rovnost ⟺ $f = u$ na celém $\delta^+(A)$ a $f = l$ na celém $\delta^-(A)$.
- Max-flow = min-cut (Ford a Fulkerson 1956; slidy přes LP dualitu, konstruktivně přes poslední značkování).
- Min řez prakticky: $A$ = vrcholy označené v posledním (neúspěšném) značkování [L4.3]; kontrola $C(A) = |f|$. Zkouška 25. 5. 2026: $A = \{T_1\}$, řez $\{(T_1,T_2), (T_1,T_3), (T_1,T_4)\}$, $C(A) = 4 + 5 + 7 = 16 = |f|$.
- Pozor: nasycená hrana ≠ hrana min řezu; řez vždy zapisuj přes množinu $A$.
FOTO checkpoint
zdroj: zkouška KO 25.05.2026 = task bank #21 (zadání EN 1:1; čtení špatně čitelných diagonál dle [L4.1]); část a) řešena v [L4.3] T01, zde se uzavírá částí b)
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í?
Kompletní zkoušková úloha slotu 4: běh Ford-Fulkersona s vypsanými iteracemi (část a) a minimální řez (část b). Část a) jsme vyřešili v [L4.3] T01; tady úlohu uzavíráme částí b) — a jako FOTO checkpoint ji píšeš celou.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice řezu, $C(A)$, recept „$A$ = označené vrcholy“ (takeaways).
- [L4.3] — celý běh: iterace, $\gamma$, zastavení.
- [L4.2] — značkovací procedura a reziduální graf.
- [L4.1] — čtení popisku $(l_e, f_e, u_e)$ a hodnota $|f|$.
c) Jak nad úlohou uvažovat?
Po skončení běhu z části a) spusť značkování ještě jednou a sleduj, kam se dostane. Tady je to rychlé: všechny tři hrany ze zdroje jsou nasycené, takže pravidlo 2 nic neoznačí, a do $T_1$ žádná hrana nevede, takže ani pravidlo 3. Označený zůstane jen zdroj. Pak už jen vypiš $\delta^+(A)$, $\delta^-(A)$ a spočti kapacitu — a zkontroluj, že vyšla rovná $|f|$ z části a).
d) Úplné řešení
a) (podrobně v [L4.3] T01) Start $|f| = 9$; iterace ① $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 hranu $T_5 \to T_3$, $\gamma = 2$. Výsledek $|f| = 9 + 4 + 1 + 2 = 16$; pak jsou všechny hrany ze zdroje nasycené a augmentující cesta neexistuje.
b) Řez je určen množinou $A$ s $T_1 \in A$, $T_8 \notin A$; pro sítě s dolními mezemi je jeho kapacita $$C(A) = \sum_{e \in \delta^+(A)} u(e) - \sum_{e \in \delta^-(A)} l(e).$$ Poslední (neúspěšné) značkování označí jen zdroj — z $T_1$ nevede v reziduálním grafu žádná hrana ($f_{12} = u_{12} = 4$, $f_{13} = u_{13} = 5$, $f_{14} = u_{14} = 7$). Tedy $$A = \{T_1\}, \qquad \delta^+(A) = \{(T_1, T_2),\ (T_1, T_3),\ (T_1, T_4)\}, \qquad \delta^-(A) = \emptyset,$$ $$C(A) = 4 + 5 + 7 - 0 = 16.$$ Minimální řez je zdrojový řez $\{(T_1, T_2), (T_1, T_3), (T_1, T_4)\}$ s kapacitou $16$ — rovnou hodnotě maximálního toku z části a), což je zároveň kontrola správnosti (max-flow = min-cut).
FOTO checkpointVyřeš celou úlohu (a) i (b) NA PAPÍR bez koukání do řešení — přesně takhle padla 25. 5. 2026 — a pošli mi fotku. Zkontroluju: u a) každou iteraci (cesta, výpočet $\gamma$ jako minimum rezerv, změněné toky — zejména zpětnou hranu $T_5 \to T_3$ s rezervou $f - l = 3$) a zdůvodnění konce; u b) že řez zapisuješ přes množinu $A$ z posledního značkování, vypsané hrany $\delta^+(A)$ a kontrolu $C(A) = |f| = 16$.
An adversary has a tank located at one node $t$ and the gasoline supply pipeline denoted by directed graph $G(E, V)$. Gasoline supply node is denoted by $s$. Let pipe $e$ have minimum throughput $l(e)$ and maximum throughput $u(e)$. We may decrease $u(e)$ by $k(e) \in \langle 0, u(e) - l(e) \rangle$, but in such case we lose $k(e)$ soldiers.
We want to isolate the tank from the gasoline supply while losing a minimum number of soldiers.
a) Consider $l(e) = 0$ and determine the minimal effort required to isolate the tank from gasoline.
b) How does the problem change when we consider non-zero minimum throughput?
c) Consider several supply nodes denoted by the set $S \subset V$ such that $t \notin S$.
a) Co je v zadání?
Modelovací úloha na význam minimálního řezu: „odříznout“ cisternu od zásobování znamená srazit propustnost nějakého hrdla na nulu a každá ubraná jednotka kapacity stojí jednoho vojáka. Tři varianty: bez dolních mezí, s dolními mezemi, více zdrojů.
b) Co k tomu budeme potřebovat?
- Tato lekce — řez $\delta(A)$, kapacita $C(A)$, max-flow = min-cut (takeaways).
- [L4.1] — co vynucuje dolní mez $l(e)$.
c) Jak nad úlohou uvažovat?
(i) Kdy je cisterna izolovaná? Když po snížení kapacit je maximální tok $s \to t$ nulový. (ii) Jakou množinu hran se vyplatí „uzavírat“? Promysli, že snižovat kapacitu hrany, která netvoří s ostatními řez, je vyhozený voják. (iii) U b): na kolik nejméně jde srazit kapacita hrany? A co z toho plyne pro hrany s $l(e) > 0$? (iv) U c): jak víc zdrojů převést na jeden — vzpomeň na trik s pomocným vrcholem.
d) Úplné řešení (vlastní — slidy řešení neuvádějí)
a) Vyber libovolný řez $A$ ($s \in A$, $t \notin A$) a sraz na nulu všechny výstupní hrany: $k(e) = u(e)$ pro $e \in \delta^+(A)$. Cena $= \sum_{e \in \delta^+(A)} u(e) = C(A)$ (při $l \equiv 0$) a tok je nulový — hodnota toku měřená na $A$ je $\le 0$ a zároveň $\ge 0$. Naopak každé úspěšné zablokování nějaký řez vynulovat musí: kdyby po snížení měl každý řez kladnou kapacitu, byl by podle věty max-flow/min-cut kladný i maximální tok. Vynulování řezu $A$ stojí aspoň $C(A) \ge C_{\min}$. Minimální počet ztracených vojáků = kapacita minimálního řezu = hodnota maximálního toku — spočteš ji Ford-Fulkersonem [L4.3] a řez odečteš z posledního značkování.
b) Dvě změny. Cena: hranu jde srazit nejvýš o $u(e) - l(e)$ (na dolní mez), takže uzavření řezu $A$ stojí $\sum_{e \in \delta^+(A)} (u(e) - l(e))$ — hledáš minimální řez v síti s kapacitami $u(e) - l(e)$. Proveditelnost: i po maximálním snížení teče hranou pořád aspoň $l(e)$; nejlepší dosažitelná kapacita řezu $A$ je $\sum_{e \in \delta^+(A)} l(e) - \sum_{e \in \delta^-(A)} l(e)$. Úplná izolace je tedy možná, jen pokud existuje řez, kde tahle hodnota je $\le 0$ (typicky: všechny výstupní hrany řezu mají $l(e) = 0$); jinak nenulové zásobování garantované dolními mezemi nezastavíš.
c) Standardní trik se super-zdrojem: přidej nový vrchol $s'$ a hrany $s' \to v$ pro každé $v \in S$ s kapacitou $u = \infty$ (ty „přestřihnout“ nejde — stály by nekonečno vojáků). Minimální řez oddělující $s'$ od $t$ v rozšířené síti nikdy neobsahuje hranu $s' \to v$, takže odpovídá řezu $A \supseteq S$, $t \notin A$ v původní síti — tedy hrdlu, které odřízne cisternu od všech zdrojů najednou. Dál jako v a).