Počáteční přípustný tok při nenulových dolních mezích
Ford-Fulkerson je smyčka „augmentuj, dokud to jde“ — ale krok 1 zní „sežeň přípustný tok“ ([L4.3]). Při $l \equiv 0$ je to zadarmo ($f \equiv 0$), a u zkouškových běhů bývá tok rovnou v zadání. Dnes vyřešíme zbývající případ: síť s nenulovými dolními mezemi, kde startovní tok nikdo nedal. Je to přesné zkouškové zadání (09.07.2021 a další termíny, úloha T01 dole) i téma k ústní — a zároveň vstupní brána k minimum cost flow: cycle canceling v [L4.11] taky potřebuje z čeho vystartovat.
Proč je start vůbec problém
If $\forall e \in E(G);\, l(e) = 0$ — easy solution — we use zero flow which satisfies Kirchhoff's law.
If $\exists e \in E(G);\, l(e) > 0$, we transform the Maximum Flow problem with non-zero lower bounds to the Feasible Flow with Balances and zero lower bounds.
Celou lekci odpracujeme na příkladu ze slidů 26–27 (orientace hran rekonstruována z popisu obrázku tak, aby seděly kapacity i výsledné bilance — přiznáno; popisek hrany $= l, -, u$, tok zatím neznáme):
Zkus sám: proč nejde vystartovat z $f \equiv 0$? A co druhý reflex — položit rovnou $f \equiv l$?
$f \equiv 0$ porušuje dolní meze: hrana $s \to u$ chce $f \ge 1$, hrana $s \to v$ dokonce $f \ge 2$. A $f \equiv l$ sice meze splní ($l \le l \le u$ ✓), ale obecně rozbije Kirchhoffa ([L4.1]): v uzlu $v$ by přiteklo $l(s{\to}v) + l(u{\to}v) = 2 + 1 = 3$, ale odteklo jen $l(v{\to}t) = 2$. Jednotka by se ve $v$ „ztrácela“. (V uzlu $u$ to náhodou vyjde, $1 = 1$ — ale spoléhat se na to nedá.) Přípustný tok musí vybalancovat obě podmínky najednou — a dokonce nemusí existovat vůbec (drill v [L4.1] T02). Potřebujeme systematickou konstrukci, ne hádání.
Krok 1: uzavři síť cirkulační hranou $t \to s$ (slide 24)
Zkus sám: uzly $s$ a $t$ jsou výjimky — Kirchhoff pro ně neplatí. Jak je jediným tahem „zrovnoprávnit“ se zbytkem grafu?
Vrať tok zpátky: přidej hranu $t \to s$ s $l = 0$ a $u = \infty$. Všechno, co do $t$ přiteče, po ní odteče zpět do $s$ — takže Kirchhoffova rovnice začne platit i v $s$ a $t$. Z toku se stane cirkulace (circulation): tok bez začátku a konce, který jen obíhá. Žádný uzel už není speciální — a přesně to potřebujeme, protože další krok bude manipulovat každý uzel stejným pravidlem. Hodnota původního toku přitom nezmizela: je to přesně $f(t \to s)$.
1) We add a circulation problem by adding an arc from $t$ to $s$ of infinite capacity. Consequently, the Kirchhoff's law applies to nodes $s$ and $t$. Therefore, a feasible circulation must satisfy:
$$\begin{aligned} l(e) \le f(e) \le u(e) & \quad e \in E(G) \\ \sum_{e \in \delta^+(v)} f(e) - \sum_{e \in \delta^-(v)} f(e) = 0 & \quad v \in V(G) \end{aligned}$$Krok 2: substituce $f = f' + l$ — a krok 3: bilance z dolních mezí (slide 25)
Zkus sám: vymysli substituci, po které podmínka $l(e) \le f(e) \le u(e)$ ztratí dolní mez. (Nápověda: neměř celý tok — měř jen to, co je navíc.)
Povinných $l(e)$ jednotek hranou poteče tak jako tak — zajímavá je jen nadstavba $f'(e) := f(e) - l(e)$, tedy $f(e) = f'(e) + l(e)$. Dosazením: $l \le f' + l \le u \iff 0 \le f'(e) \le u(e) - l(e)$. Nová proměnná $f'$ má nulovou dolní mez a kapacitu $u'(e) = u(e) - l(e)$ — přesně svět, ve kterém umí Ford-Fulkerson vystartovat z nuly. Otázka za milion: co ta substituce provede s Kirchhoffem?
Zkus sám: dosaď $f(e) = f'(e) + l(e)$ do cirkulačního Kirchhoffa $\sum_{\delta^+(v)} f - \sum_{\delta^-(v)} f = 0$. Co zbyde na pravé straně?
$\sum_{\delta^+(v)} (f' + l) - \sum_{\delta^-(v)} (f' + l) = 0$, tedy po přerovnání $$\sum_{e \in \delta^+(v)} f'(e) - \sum_{e \in \delta^-(v)} f'(e) = \underbrace{\sum_{e \in \delta^-(v)} l(e) - \sum_{e \in \delta^+(v)} l(e)}_{=:\ b(v)}.$$ Na pravé straně se objevila konstanta spočítaná jen ze vstupních dat (žádný neznámý tok!) — a levá strana je přesně bilanční rovnice z [L4.6]. Dolní meze se proměnily v bilance: uzel, do kterého dolní meze „napumpují“ víc povinného přítoku, než kolik z něj povinně odtéká, se v $f'$-světě chová jako dodavatel ($b(v) > 0$ — přebytek musí odeslat); opačný uzel jako spotřebič ($b(v) < 0$).
2) Substituting $f(e) = f(e)' + l(e)$, we obtain the transformed problem:
$$\begin{aligned} 0 \le f(e)' \le u(e) - l(e) & \quad e \in E(G) \\ \sum_{e \in \delta^+(v)} f(e)' - \sum_{e \in \delta^-(v)} f(e)' = \underbrace{\sum_{e \in \delta^-(v)} l(e) - \sum_{e \in \delta^+(v)} l(e)}_{b(v)} & \quad v \in V(G) \end{aligned}$$3) This is a Feasible Flow with Balances and zero lower bounds because $\sum_{v \in V(G)} b(v) = 0$ (notice that $l(e)$ appears twice in summation, once with a positive and once with a negative sign).
Zkus sám: spočti $b(v)$ pro všechny čtyři uzly příkladu (cirkulační hrana $t \to s$ má $l = 0$). Vyjde $\sum_v b(v) = 0$?
Recept: $b(v) = \sum l(\text{hrany do } v) - \sum l(\text{hrany z } v)$.
- $b(s) = \underbrace{0}_{t \to s} - \underbrace{(1 + 2)}_{s \to u,\ s \to v} = -3$ — spotřebič (musí přijmout 3 jednotky extra toku).
- $b(u) = \underbrace{1}_{s \to u} - \underbrace{(1 + 0)}_{u \to v,\ u \to t} = 0$ — vybalancovaný.
- $b(v) = \underbrace{2 + 1}_{s \to v,\ u \to v} - \underbrace{2}_{v \to t} = +1$ — dodavatel.
- $b(t) = \underbrace{0 + 2}_{u \to t,\ v \to t} - \underbrace{0}_{t \to s} = +2$ — dodavatel.
$\sum_v b(v) = -3 + 0 + 1 + 2 = 0$ ✓ — a nejde o náhodu: každé $l(e)$ hrany $e = (x, y)$ se v součtu objeví jednou s plusem (u $y$) a jednou s minusem (u $x$), přesně jak říká slide. Tahle kontrola tě u zkoušky zdarma upozorní na početní chybu.
Krok 4: zavolej redukci z [L4.6] a přečti odpověď
Dál už nic nového nevymýšlíme — máme instanci $(G', u', b)$ s nulovými dolními mezemi a tu řeší minulá lekce: super-zdroj $s'$ s hranami $u = b(v)$ do dodavatelů, super-stok $t'$ s hranami $u = -b(v)$ ze spotřebičů, max flow, kritérium nasycení ([L4.6]).
4) While solving this decision problem (i.e. adding $s', t'$ and solving the maximum flow problem with zero lower bounds) we obtain the initial feasible circulation/flow or decide that it does not exist.
Conclusion: finding of the initial flow with nonzero lower bounds can be transformed to the Feasible Flow with Balances and zero lower bounds which can be transformed to the Maximum Flow with zero lower bounds.
Zkus sám: ten max flow v kroku 4 taky někde musí vystartovat. Nekoušeme si do ocasu?
Ne — a to je celý vtip konstrukce. V redukované síti je všude $l = 0$ (původní hrany po substituci, b-hrany i cirkulační hrana), takže $f' \equiv 0$ je přípustný start a Ford-Fulkerson [L4.3] normálně poběží. Nenulové dolní meze jsme nezrušili — přestěhovali jsme je do bilancí, kde s nimi max flow umí pracovat.
Běh na příkladu (redukovaná síť = slide 27; samotný běh je vlastní dopočet, slidy ukazují jen transformaci — přiznáno):
Zpětný převod: $f(e) = f'(e) + l(e)$
Odpověď byla ANO — ale úloha nechtěla rozhodnutí, chtěla tok. Ten dostaneš zpětnou substitucí na původních hranách: $f(e) = f'(e) + l(e)$. V příkladu: $f(s{\to}u) = 0 + 1 = 1$, $f(s{\to}v) = 0 + 2 = 2$, $f(u{\to}v) = 0 + 1 = 1$, $f(u{\to}t) = 0 + 0 = 0$, $f(v{\to}t) = 1 + 2 = 3$ — všimni si, že i hrany s $f' = 0$ nesou tok $l(e)$:
Cirkulační hranu $t \to s$ nakonec smažeš a zbyde obyčejný $s$-$t$ tok s hodnotou $|f| = f(t \to s) = 3$. To je počáteční přípustný tok: Ford-Fulkerson z něj na původní síti $(G, l, u, s, t)$ pokračuje augmentacemi v reziduálním grafu — dopředné hrany s $f < u$, zpětné s $f > l$ ([L4.2]) — až k maximálnímu toku.
Nebezpečné polopravdy1) Znaménko $b(v)$: vstupy minus výstupy. $b(v) = \sum_{\delta^-(v)} l - \sum_{\delta^+(v)} l$ — opačně, než je v Kirchhoffovi na levé straně (tam je $\delta^+$ první)! Mnemotechnika: povinný přítok dělá z uzlu dodavatele extra toku ($b > 0$), protože napumpované jednotky musí v $f'$-světě odeslat dál. 2) Zapomenutá hrana $t \to s$ s $\infty$. Bez ní Kirchhoff v $s$ a $t$ neplatí, substituce tam žádné $b$ nevyrobí a transformace nesedí — u zkoušky je to první věc, kterou opravující hledá. 3) Odpověď je $f = f' + l$, ne $f'$. Po max flow nezapomeň přičíst zpátky dolní meze, smazat $t \to s$ a vrátit se k původní síti — F-F pak pokračuje na ní, ne na redukci. 4) Počáteční tok nemusí existovat. Když $|f'_{\max}| < B = \sum_{b(v) > 0} b(v)$, přípustný tok v $(G, l, u, s, t)$ prostě není (kritérium i certifikát řezem viz [L4.6] a [L4.4]) — a původní max-flow úloha nemá žádné řešení.
Key takeaways — L4.7- $l \equiv 0$ → start zdarma: $f \equiv 0$ splňuje Kirchhoffa i meze. Při $l(e) > 0$ nulový tok přípustný není a $f \equiv l$ obecně rozbíjí Kirchhoffa.
- Transformace ve 3 tazích (slidy 24–25): ① cirkulační hrana $t \to s$ s $(l, u) = (0, \infty)$ — Kirchhoff pak platí všude; ② substituce $f(e) = f'(e) + l(e)$ → $0 \le f'(e) \le u'(e) = u(e) - l(e)$; ③ bilance $b(v) = \sum_{\delta^-(v)} l(e) - \sum_{\delta^+(v)} l(e)$ — jen ze vstupních dat, $\sum_v b(v) = 0$ (každé $l(e)$ jednou $+$ a jednou $-$).
- Krok 4 = [L4.6]: přidej $s', t'$, vyřeš max flow s nulovými $l$ (start $f' \equiv 0$); počáteční tok existuje $\iff$ b-hrany nasycené ($|f'_{\max}| = B$).
- Zpětný převod: $f(e) = f'(e) + l(e)$ na původních hranách, smaž $t \to s$ → počáteční $s$-$t$ tok hodnoty $f(t \to s)$; F-F pokračuje na původní síti přes reziduální graf [L4.2].
- Řetěz redukcí (Conclusion, slide 25): initial flow s nenulovými $l$ → Feasible Flow with Balances s $l = 0$ → Maximum Flow s $l = 0$. Stejný startovní problém řeší i cycle canceling pro MCF v [L4.11].
Transform the problem of finding an initial feasible flow (with non-zero lower bound problem $(G, l, u, s, t)$) for Ford-Fulkerson algorithm to problem $(G', u', b)$ i.e., the feasible flow decision problem with zero lower bound.
a) Co je v zadání?
Teoretická „describe the transformation“ úloha (za 2 b): nechtějí po tobě počítat konkrétní síť, ale popsat konstrukci — jak z úlohy „najdi počáteční přípustný tok při $l(e) > 0$“ uděláš instanci $(G', u', b)$ rozhodovací úlohy feasible flow with balances s nulovými dolními mezemi. Tatáž otázka chodí i k ústní.
b) Co k tomu budeme potřebovat?
- Tato lekce — kroky 1–4 a vzorce $u' = u - l$, $b(v)$ (takeaways).
- [L4.6] — co je feasible flow with balances a jak se dořeší max flowem.
- [L4.1] — Kirchhoff a přípustnost $l \le f \le u$.
c) Jak nad úlohou uvažovat?
Odpověď strukturuj přesně podle tří překážek: (1) $s$ a $t$ nemají Kirchhoffa → uzavři síť; (2) dolní meze brání startu z nuly → substituce; (3) substituce změní pravé strany rovnic → to jsou bilance. Ke každému kroku napiš vzorec a jednu větu proč. Nezapomeň říct, čím to končí (max flow + kritérium nasycení) a jak se z $f'$ vrátíš k $f$ — bez toho je odpověď neúplná.
d) Úplné řešení (dle banky #22)
Krok 1 — uzavři síť. Přidej umělou hranu $(t, s)$ s $l(t, s) = 0$, $u(t, s) = \infty$. Úloha o $s$-$t$ toku se změní na úlohu o cirkulaci; uzly $s$ a $t$ přestávají být speciální a Kirchhoffův zákon platí ve všech vrcholech.
Krok 2 — odstraň dolní meze. Pro každou hranu $e$ definuj nový neznámý „extra tok“ $f'(e)$ vztahem $f(e) = l(e) + f'(e)$. Pak $$l(e) \le f(e) \le u(e) \iff 0 \le f'(e) \le u(e) - l(e),$$ takže transformovaná kapacita je $u'(e) = u(e) - l(e)$ a dolní meze jsou nulové.
Krok 3 — bilance z dolních mezí. Dosazení $f = l + f'$ do Kirchhoffova zákona dává pro každý uzel $$\sum_{e \in \delta^+(v)} f'(e) - \sum_{e \in \delta^-(v)} f'(e) = b(v) = \sum_{e \in \delta^-(v)} l(e) - \sum_{e \in \delta^+(v)} l(e).$$ Výraz $b(v)$ používá jen vstupní data, ne neznámý tok; platí $\sum_v b(v) = 0$ (každé $l(e)$ se objeví jednou s $+$ a jednou s $-$). Tím je instance $(G', u', b)$ hotová — to je požadovaná odpověď. Význam bilancí: $b(v) > 0$ → $v$ musí odeslat víc extra toku, než přijme (dodavatel); $b(v) < 0$ → musí víc přijmout (spotřebič); $b(v) = 0$ → vybalancovaný.
Krok 4 — dořešení max flowem (bonus, [L4.6]). Přidej super-zdroj $s^*$ a super-stok $t^*$: pro $b(v) > 0$ hranu $s^* \to v$ s kapacitou $b(v)$, pro $b(v) < 0$ hranu $v \to t^*$ s kapacitou $-b(v)$. Pusť max flow z $s^*$ do $t^*$. Přípustný tok existuje $\iff$ max tok nasytí všechny hrany z $s^*$; pak se původní tok obnoví jako $f(e) = l(e) + f'(e)$. Jinak počáteční přípustný tok neexistuje.
Consider the network $(G, l, u, s, t)$ below with edges labelled $(l(e), u(e))$: $s \to a\ (2, 3)$, $s \to b\ (0, 2)$, $b \to a\ (1, 2)$, $a \to t\ (0, 3)$, $b \to t\ (0, 1)$. (i) Transform the search for an initial feasible flow into the feasible flow problem with balances and zero lower bounds: close the network, compute the transformed capacities $u'(e)$ and the balances $b(v)$. (ii) Solve the resulting maximum flow problem and decide whether a feasible flow exists. (iii) If it does, recover the flow $f$, verify $l \le f \le u$ and Kirchhoff's law, and state the value $|f|$ of the obtained initial $s$-$t$ flow.
a) Co je v zadání?
Stejná konstrukce jako v lekci, ale tentokrát ji celou odpracuješ sám na malé síti: dvě hrany s nenulovou dolní mezí ($s \to a$ s $l = 2$, $b \to a$ s $l = 1$), takže nulový tok nepřipadá v úvahu. Výstupem není jen ANO/NE, ale konkrétní počáteční tok $f$ a jeho hodnota.
b) Co k tomu budeme potřebovat?
- Tato lekce — kroky 1–4 + zpětný převod (takeaways).
- [L4.6] — redukce s $s', t'$ a kritérium nasycení.
- [L4.3] — běh Ford-Fulkersona po iteracích.
c) Jak nad úlohou uvažovat?
Mechanicky podle receptu: ① $t \to s$ s $(0, \infty)$; ② $u' = u - l$ na každé hraně; ③ $b(v) = \sum_{\text{do}} l - \sum_{\text{z}} l$ pro všechny čtyři uzly + kontrola $\sum b = 0$; ④ $s'$, $t'$, max flow, porovnání $|f'_{\max}|$ s $B$; ⑤ $f = f' + l$ a ověření. Pozor na uzel, do kterého vede hrana s $l > 0$ a zároveň z něj jiná s $l > 0$ vychází — znaménka se odečítají.
d) Úplné řešení (vlastní — přiznáno)
(i) Transformace. Cirkulační hrana $t \to s$ s $(l, u) = (0, \infty)$. Nové kapacity $u' = u - l$: $s \to a$: $1$, $s \to b$: $2$, $b \to a$: $1$, $a \to t$: $3$, $b \to t$: $1$, $t \to s$: $\infty$. Bilance:
- $b(s) = 0 - (2 + 0) = -2$ (spotřebič),
- $b(a) = (2 + 1) - 0 = +3$ (dodavatel),
- $b(b) = 0 - (1 + 0) = -1$ (spotřebič),
- $b(t) = (0 + 0) - 0 = 0$;
$\sum_v b(v) = -2 + 3 - 1 + 0 = 0$ ✓. Redukce dle [L4.6]: $s' \to a$ ($u = 3$), $s \to t'$ ($u = 2$), $b \to t'$ ($u = 1$); $B = 3$.
(ii) Max flow (start $f' \equiv 0$, všude $l = 0$):
$|f'_{\max}| = 3 = B$ — všechny b-hrany nasycené → počáteční přípustný tok existuje.
(iii) Zpětný převod $f = f' + l$ na původních hranách: $f(s \to a) = 0 + 2 = 2$, $f(s \to b) = 1 + 0 = 1$, $f(b \to a) = 0 + 1 = 1$ (hrana s $f' = 0$ nese tok $l = 1$!), $f(a \to t) = 3 + 0 = 3$, $f(b \to t) = 0 + 0 = 0$. Ověření mezí: $2 \in [2, 3]$ ✓, $1 \in [0, 2]$ ✓, $1 \in [1, 2]$ ✓, $3 \in [0, 3]$ ✓, $0 \in [0, 1]$ ✓. Kirchhoff: $a$: přítok $2 + 1 = 3$ = odtok $3$ ✓; $b$: přítok $1$ = odtok $1 + 0$ ✓. Po smazání $t \to s$ je to $s$-$t$ tok: z $s$ odteče $2 + 1 = 3$ a nic do něj nepřiteče, takže $|f| = 3$ (= tok na smazané cirkulační hraně $t \to s$ ✓). Ford-Fulkerson teď může na původní síti pokračovat z $f$ augmentacemi přes reziduální graf [L4.2].