Feasible flow with balances
Zatím měla každá síť jediný zdroj $s$ a jediný stok $t$ a všude jinde platil Kirchhoffův zákon ([L4.1]). Reálné úlohy ale vypadají jinak: tři rafinerie vyrábějí, čtyři města spotřebovávají a potrubí mezi nimi má omezené kapacity. Žádné $s$, žádné $t$ — jen uzly, které chtějí mít předepsaný přebytek nebo schodek. Dnes se naučíš tuhle úlohu (slidy 21–23) rozhodnout: existuje tok, který všechny bilance splní? Stejný převod budeš za chvíli potřebovat jako vnitřek konstrukce počátečního přípustného toku v [L4.7] a u matrix rounding v [L4.8] — a bilance $b(v)$ se znovu objeví v definici minimum cost flow [L4.10].
Víc zdrojů, víc spotřebičů (slide 22)
There are suppliers (represented by nodes with $b(v) > 0$) and consumers (represented by nodes with $b(v) < 0$) of a product. Our goal is to decide whether it is possible to transport all the product from the suppliers to the consumers through the network with upper bounds $u$. The problem is described by a network (or graph) where the edges represent pipelines, highways or railways of some transportation capacity.
The goal is to decide whether it is possible to transport all the product from suppliers $A$ to consumers $B$ through the network with capacities $u$.
Zkus sám: čím se taková síť liší od sítě $(G, l, u, s, t)$ z [L4.1]? Můžeš na ni rovnou pustit Ford-Fulkersona?
Nemůžeš — chybí jediný zdroj a jediný stok. A hlavně: dodavatelské uzly Kirchhoffův zákon porušují schválně — dodavatel $A_i$ má víc odtéct, než přiteče (vyrábí), spotřebiteli $B_j$ má naopak víc přitéct (spotřebovává). Potřebujeme tedy nejdřív nový jazyk, jak „chtěný přebytek“ uzlu zapsat, a pak trik, jak úlohu vrátit do světa max flow, kde už umíme všechno z [L4.3]–[L4.4].
Tady je konkrétní mini-instance, na které budeme celou lekci pracovat (vlastní, přiznáno — slide 22 má větší obrázek se třemi dodavateli a čtyřmi spotřebiteli, jeho kapacity se v přepisu nedochovaly):
Bilance $b(v)$: zdroj a spotřebič zapsaný do vrcholu (slide 21)
Zkus sám: jak jedinou rovnicí říct „uzel $v$ vyrobí $b(v)$ jednotek“? (Nápověda: uprav Kirchhoffa z [L4.1] — co se musí změnit na pravé straně?)
Kirchhoff říká $\sum_{e \in \delta^+(v)} f(e) - \sum_{e \in \delta^-(v)} f(e) = 0$ — co odteče, to přiteklo. Výroba znamená, že odtéct má o $b(v)$ víc: na pravou stranu napíšeš $b(v)$ místo nuly. Spotřeba je totéž se záporným $b(v)$ (víc přiteče, než odteče). Kirchhoffův zákon je tedy speciální případ $b(v) = 0$.
We assume several sources and several sinks. Later we show its polynomial reduction to the Maximum Flow problem (with one source and one sink).
Instance: Let $(G, l, u, b)$ be a network where $G$ is a digraph with upper bounds $u : E(G) \to \mathbb{R}^+_0$, $l : E(G) \to \mathbb{R}^+_0$ and with balance $b : V(G) \to \mathbb{R}$ that represents the supply/consumption of the nodes and satisfies $\sum_{v \in V(G)} b(v) = 0$.
Goal: Decide if there exists a feasible flow $f$ which satisfies $\sum_{e \in \delta^+(v)} f(e) - \sum_{e \in \delta^-(v)} f(e) = b(v)$ for all $v \in G(V)$.
Slovník: $b(v) > 0$ = supply (dodavatel, zdroj), $b(v) < 0$ = consumption (spotřebič), $b(v) = 0$ = průtokový uzel s obyčejným Kirchhoffem. Všimni si dvou věcí: je to rozhodovací úloha (decision problem) — odpověď je ANO/NE, nic se nemaximalizuje — a v instanci není žádné $s$ ani $t$.
Zkus sám: proč definice vyžaduje $\sum_{v} b(v) = 0$? Co by se stalo bez toho?
Sečti bilanční rovnice přes všechny vrcholy: každá hrana $e = (x, y)$ se v součtu objeví dvakrát — jednou s $+f(e)$ (odchází z $x$), jednou s $-f(e)$ (přichází do $y$) — takže levá strana je vždy $0$. Pravá strana je $\sum_v b(v)$. Kdyby součet bilancí nebyl nulový, rovnice si protiřečí a tok nemůže existovat pro žádné kapacity — celková výroba se musí rovnat celkové spotřebě. V mini-instanci: $2 + 3 - 4 - 1 = 0$ ✓. (Tohle si u zkoušky vždycky zkontroluj jako první.)
Redukce na max flow: super-zdroj a super-stok (slide 23)
Zkus sám: max flow umí vynutit jen Kirchhoffa ($b \equiv 0$ všude mimo $s, t$). Jak donutit uzel $A_1$, aby měl přebytek $+2$? (Nápověda: přebytek nemusí vznikat „z ničeho“ — může odněkud přitéct.)
Přivedeš mu ty $2$ jednotky zvenku: nový super-zdroj $s'$ a hrana $s' \to A_1$ s kapacitou $u = 2$. Když po ní poteče přesně $2$, Kirchhoff v $A_1$ (v rozšířené síti) říká „co přiteklo, odteče“ — a v původní síti to vypadá, jako by $A_1$ dvě jednotky vyrobil. Symetricky spotřebič $B_1$ dostane odvod $B_1 \to t'$ s kapacitou $-b(B_1) = 4$ do super-stoku. Z bilancí se tak stanou obyčejné hrany — a zbývá jediná otázka: jak zařídit, aby po b-hranách teklo přesně $b(v)$, když kapacita umí říct jen „nejvýš“? Stejný tah jako v [L4.5]: „přesně“ = „nejvýš“ + požadavek nasycení.
We transform this problem to the maximum flow problem:
- We add a new node $s$ called the source and add edges $(s, v)$ with the lower bound $l_v = 0$ and the upper bound $u_v = b(v)$ for every node that satisfies $b(v) > 0$
- We add a new node $t$ called the sink and add edges $(v, t)$ with the lower bound $l_v = 0$ and the upper bound $u_v = -b(v)$ for every node that satisfies $b(v) < 0$
- We solve the maximum flow problem
- If the maximum flow saturates all edges leaving $s$ and/or entering $t$, then the answer to the feasible flow decision problem is YES.
(Slide nové uzly pojmenovává $s$ a $t$; my budeme psát $s'$ a $t'$ — jednak je to jméno, které uvidíš na slidu 27 a v [L4.7], jednak se pak neplete s případným původním $s, t$ v grafu.) Takhle dopadne mini-instance po redukci:
Zkus sám: proč je nasycení všech hran ze $s'$ správné kritérium? Rozmysli si obě strany ekvivalence.
(⇐) Když max tok nasytí všechny hrany ze $s'$, teče do každého dodavatele $A_i$ přesně $b(A_i)$ zvenku. Kirchhoff v $A_i$ (rozšířená síť) pak dává: odtok do původních hran $-$ přítok z původních hran $= b(A_i)$ — přesně bilanční rovnice. Stejně u spotřebičů (nasycený odvod $-b(B_j)$ do $t'$; díky $\sum_v b(v) = 0$ se nasytí obě strany naráz, viz další otázka) a uzly s $b = 0$ mají čistého Kirchhoffa. Restrikce maximálního toku na původní hrany je tedy hledaný přípustný tok s bilancemi — odpověď ANO. (⇒) Naopak z přípustného toku $f$ s bilancemi vyrobíš tok v rozšířené síti: na původních hranách nech $f$, na b-hranách pošli $f(s' \to v) = b(v)$ a $f(v \to t') = -b(v)$ — bilanční rovnice říkají přesně to, že Kirchhoff teď platí všude. Tenhle tok má hodnotu $B := \sum_{v:\,b(v)>0} b(v)$ a víc nejde: řez $A = \{s'\}$ má kapacitu $C(A) = B$, takže $|f| \le B$ pro každý tok (slabá dualita [L4.4]). Je to tedy maximální tok a b-hrany jsou nasycené. (Rozepsání ekvivalence je vlastní — slide 23 uvádí jen kritérium.)
Zkus sám: slide píše „saturates all edges leaving $s$ and/or entering $t$“. Stačí opravdu zkontrolovat jen jednu stranu?
Ano. Hodnota toku měří obojí najednou: $|f| = \sum$ toků po hranách ze $s'$ a zároveň (měřeno na řezu kolem $t'$, [L4.1]) $= \sum$ toků po hranách do $t'$. Kapacity obou svazků jsou stejné: $\sum_{b(v)>0} b(v) = \sum_{b(v)<0} (-b(v)) = B$, protože $\sum_v b(v) = 0$. Takže hrany ze $s'$ jsou nasycené $\iff |f| = B \iff$ hrany do $t'$ jsou nasycené — proto to nenápadné „and/or“. Prakticky: stačí porovnat jediné číslo, $|f_{\max}|$ s $B$.
Naživo: rozhodnutí Ford-Fulkersonem
Po redukci je to obyčejná síť s $l \equiv 0$, takže Ford-Fulkerson [L4.3] může vystartovat z nulového toku. Proklikej si běh na mini-instanci (popisek hrany $= l, f, u$):
A co dolní meze $l(e)$?
Definice na slidu 21 dolní meze $l : E(G) \to \mathbb{R}^+_0$ připouští — ale všimni si, že nové b-hrany je v redukci dostávají nulové, a celý krok 3 („solve the maximum flow problem“) je pohodlný jen tehdy, když $l \equiv 0$ i na původních hranách: pak je nulový tok přípustný start pro F-F ([L4.1]). Kdyby původní síť měla $l(e) > 0$, k řešení max flow bys nejdřív potřeboval počáteční přípustný tok — což je přesně úloha, kvůli které se tohle všechno učíme. Vtip příští lekce [L4.7]: substituce $f(e) = f'(e) + l(e)$ umí nenulové dolní meze převést na bilance $b(v)$ s nulovými $l$ — a pak zavoláš dnešní redukci. Proto se „feasible flow with balances“ probírá s $l \equiv 0$ a proto je to stavební kámen, ne okrajová kuriozita.
Nebezpečné polopravdy1) „$b(v)$ je kapacita vrcholu.“ Není — bilance je rovnost (uzel musí mít přebytek přesně $b(v)$), zatímco kapacita říká „nejvýš“. Rovnost vynutíš až kombinací „kapacita $b(v)$ na b-hraně“ + „požadavek nasycení“. 2) „Když přípustný tok neexistuje, algoritmus selže.“ Neselže — maximální tok v rozšířené síti existuje vždy. Odpověď NE poznáš jedině porovnáním $|f_{\max}| < B = \sum_{b(v)>0} b(v)$; bez věty „přípustný tok existuje $\iff$ max tok nasytí b-hrany“ je formulace u zkoušky neúplná (stejná past jako v [L4.5]). A min řez z posledního značkování [L4.4] je certifikát, kudy vede úzké hrdlo. 3) Zapomenutá kontrola $\sum_v b(v) = 0$. Když součet nevyjde nulový, je odpověď NE okamžitě (rovnice si protiřečí) — žádnou síť stavět nemusíš.
Key takeaways — L4.6- Instance $(G, l, u, b)$: bilance $b(v)$ nahrazuje Kirchhoffa — $\sum_{\delta^+} f - \sum_{\delta^-} f = b(v)$; $b > 0$ supply, $b < 0$ consumption, $b = 0$ průtokový uzel. Nutně $\sum_v b(v) = 0$ (sečti rovnice — každá hrana se vyruší).
- Redukce na max flow (slide 23): super-zdroj $s'$ s hranami $(s', v)$, $u = b(v)$, pro $b(v) > 0$; super-stok $t'$ s hranami $(v, t')$, $u = -b(v)$, pro $b(v) < 0$; všechny nové $l = 0$.
- Kritérium: přípustný tok s bilancemi existuje $\iff$ maximální tok nasytí všechny b-hrany, tj. $|f_{\max}| = B = \sum_{b(v)>0} b(v)$. Hrany ze $s'$ a do $t'$ se díky $\sum_v b(v) = 0$ nasytí naráz („and/or“). Víc než $B$ tok mít nemůže (řez $A = \{s'\}$).
- Čtení výsledku: ANO → restrikce max toku na původní hrany je hledaný tok; NE → $|f_{\max}| < B$ a min řez je certifikát.
- Role v kapitole: s $l \equiv 0$ startuje F-F z nuly; nenulové dolní meze se v [L4.7] substitucí $f = f' + l$ převedou právě na tuhle úlohu.
We assume several sources and several sinks. Later we show its polynomial reduction to the Maximum Flow problem (with one source and one sink).
Feasible flow with balances. Instance: Let $(G, l, u, b)$ be a network where $G$ is a digraph with upper bounds $u : E(G) \to \mathbb{R}_0^+$, lower bounds $l : E(G) \to \mathbb{R}_0^+$, and with balance $b : V(G) \to \mathbb{R}$ that represents the supply/consumption of the nodes and satisfies $\sum_{v \in V(G)} b(v) = 0$.
Goal: Decide if there exists a feasible flow $f$ which satisfies $\sum_{e \in \delta^+(v)} f(e) - \sum_{e \in \delta^-(v)} f(e) = b(v)$ for all $v \in V(G)$, together with the edge bounds $l(e) \leq f(e) \leq u(e)$.
Otázky (vlastní, přiznáno): (i) describe the polynomial reduction to the Maximum Flow problem, (ii) state the criterion that decides YES/NO, (iii) justify both directions of the criterion.
a) Co je v zadání?
Učebnicová „state & explain“ úloha ze slidů 21 a 23: síť bez $s, t$, zato s bilancemi $b(v)$ na vrcholech. Máš předvést převod na max flow (jeden zdroj, jeden stok) a vysvětlit, jak se z hodnoty maximálního toku přečte odpověď rozhodovací úlohy.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice, redukce, kritérium nasycení (takeaways).
- [L4.1] — Kirchhoff, hodnota toku $|f|$ měřená na řezu.
- [L4.4] — slabá dualita $|f| \le C(A)$ pro horní odhad $B$.
- [L4.3] — čím se max flow v kroku 3 vyřeší.
c) Jak nad úlohou uvažovat?
Drž osnovu z lekce: (i) co udělají bilance s Kirchhoffem? (ii) jak se z „uzel vyrábí“ stane „uzlu se dodává“ — kam vedou nové hrany a jaké mají meze? (iii) proč kapacita $b(v)$ + nasycení = rovnost? U zdůvodnění (⇐) použij Kirchhoffa v rozšířené síti; u (⇒) sestav tok hodnoty $B$ a zastrop ho řezem $\{s'\}$.
d) Úplné řešení
(i) Redukce (slide 23, 1:1 postup). 1. Přidej nový uzel $s'$ (source) a hrany $(s', v)$ s $l = 0$, $u = b(v)$ pro každý uzel s $b(v) > 0$. 2. Přidej nový uzel $t'$ (sink) a hrany $(v, t')$ s $l = 0$, $u = -b(v)$ pro každý uzel s $b(v) < 0$. 3. Vyřeš maximum flow problem ze $s'$ do $t'$ (původní hrany si nechají své meze $l, u$; při $l \equiv 0$ stačí F-F z nulového toku, [L4.3]). Konstrukce je polynomiální: přidá $2$ uzly a nejvýš $|V|$ hran.
(ii) Kritérium (slide 23, krok 4). Přípustný tok s bilancemi existuje $\iff$ maximální tok nasytí všechny hrany vycházející ze $s'$ (ekvivalentně: všechny hrany vstupující do $t'$), tj. $|f_{\max}| = B = \sum_{v:\,b(v)>0} b(v)$.
(iii) Zdůvodnění (vlastní rozepsání — přiznáno). (⇐) Nechť max tok $f^\ast$ nasytí b-hrany. Pro uzel $v$ s $b(v) > 0$ dává Kirchhoff v rozšířené síti $\sum_{\delta^+(v)} f^\ast - \big(\sum_{\delta^-_{orig}(v)} f^\ast + \underbrace{f^\ast(s' \to v)}_{=\,b(v)}\big) = 0$, tedy na původních hranách $\sum_{\delta^+} f^\ast - \sum_{\delta^-} f^\ast = b(v)$; symetricky pro $b(v) < 0$ (nasycený odvod $-b(v)$ do $t'$) a triviálně pro $b(v) = 0$. Restrikce $f^\ast$ na $E(G)$ splňuje i meze $l \le f \le u$, takže je to hledaný přípustný tok — ANO. (⇒) Nechť existuje přípustný tok $f$ s bilancemi. Rozšiř ho předpisem $f(s' \to v) = b(v)$, $f(v \to t') = -b(v)$: bilanční rovnice $= $ Kirchhoff všude, meze nových hran sedí s rovností (nasyceny). Hodnota toku je $B$. Žádný tok nemůže mít víc, protože řez $A = \{s'\}$ má kapacitu $C(A) = \sum_{b(v)>0} b(v) = B$ a platí slabá dualita $|f| \le C(A)$ ([L4.4]). Sestavený tok je tedy maximální a nasycuje b-hrany. ∎
Poznámka navíc: obě strany ($s'$ i $t'$) mají stejnou celkovou kapacitu $B$ právě díky podmínce $\sum_v b(v) = 0$ — proto slide smí psát „and/or“. Když $|f_{\max}| < B$, odpověď je NE a min řez z posledního značkování je certifikát.
Two suppliers $A_1, A_2$ and two consumers $B_1, B_2$ are given with balances $b(A_1) = 3$, $b(A_2) = 2$, $b(B_1) = -3$, $b(B_2) = -2$. The transportation network has edges with upper bounds $u(A_1 \to B_1) = 1$, $u(A_1 \to B_2) = 2$, $u(A_2 \to B_1) = 1$, $u(A_2 \to B_2) = 2$ and zero lower bounds. Decide whether a feasible flow with balances exists. If it does not, give a certificate (a cut) and interpret it.
a) Co je v zadání?
Malý transportní problém přesně podle dnešní lekce: dva dodavatelé (dohromady vyrobí $5$), dva spotřebitelé (dohromady spotřebují $5$), čtyři silnice s kapacitami. Otázka zní jen ANO/NE — a když NE, máš říct proč (řezem, ne pocitem).
b) Co k tomu budeme potřebovat?
- Tato lekce — redukce $s', t'$ + kritérium $|f_{\max}| = B$ (takeaways).
- [L4.3] — běh Ford-Fulkersona po iteracích.
- [L4.4] — min řez z posledního značkování jako certifikát.
c) Jak nad úlohou uvažovat?
Nejdřív kontrola $\sum_v b(v) = 0$ a výpočet $B$. Pak postav rozšířenou síť (čtyři b-hrany), pusť F-F a každou iteraci vypiš. Až nenajdeš augmentující cestu, porovnej $|f_{\max}|$ s $B$ — a množinu označených vrcholů z posledního značkování použij jako řez. Zkus si výsledek tipnout dopředu: kolik jednotek se vůbec vejde do $B_1$?
d) Úplné řešení (vlastní — přiznáno)
$\sum_v b(v) = 3 + 2 - 3 - 2 = 0$ ✓, $B = 3 + 2 = 5$. Redukce: $s' \to A_1$ ($u = 3$), $s' \to A_2$ ($u = 2$), $B_1 \to t'$ ($u = 3$), $B_2 \to t'$ ($u = 2$). Běh F-F po iteracích:
Závěr. $|f_{\max}| = 4 < 5 = B$ → přípustný tok s bilancemi neexistuje. Certifikát: poslední značkování označí $A = \{s', A_2, B_2, A_1\}$ (z $A_2$ dopředně do $B_2$ po nenasycené $A_2 \to B_2$, z $B_2$ zpětně do $A_1$ po $A_1 \to B_2$ s $f = 2 > 0$); $t'$ neoznačen. Kapacita řezu: $C(A) = u(A_1 \to B_1) + u(A_2 \to B_1) + u(B_2 \to t') = 1 + 1 + 2 = 4 = |f_{\max}|$ ✓ (max-flow = min-cut, [L4.4]). Interpretace: do $B_1$ vedou jen hrany o celkové kapacitě $1 + 1 = 2 < 3 = $ jeho spotřeba — tři jednotky pro $B_1$ prostě nemají kudy přitéct, ať dodavatelé dělají cokoli.