Síť, tok, Kirchhoffův zákon
Začíná kapitola K4. Slot 4 padl v obou doložených termínech 2026 — Ford-Fulkerson (25. 5.), Residents & council (1. 6.) — za 7 bodů. Všechno v této kapitole (augmentující cesty, řezy, párování, min-cost flow) stojí na slovníku z téhle lekce, takže si ho postavíme pečlivě. Stačí ti k tomu orientované grafy [L0.1] Co je graf a značení $\delta^+(v)$, $\delta^-(v)$ z [L0.2] Stupeň vrcholu.
K čemu toky jsou
Vzorová aplikace ze slidů (slide 4): transportation problem — chceme přepravit maximum zboží z místa $s$ do místa $t$ po síti tras (pipeline, railway, motorway…). Předpokládáme, že proudění na trasách je steady and lossless — ustálené a bezeztrátové: nic se cestou neztrácí, nic se nikde nehromadí. Přesně tahle dvě slova se za chvíli stanou Kirchhoffovým zákonem.
Co je síť (slide 3)
By network we mean a 5-tuple $(G, l, u, s, t)$, where $G$ denotes the directed graph, $u : E(G) \to \mathbb{R}^+_0$ and $l : E(G) \to \mathbb{R}^+_0$ denote the maximum and minimum capacity of the arcs and finally $s$ represents the source node (there is an oriented path from the source node to every other node) while $t$ represents the sink node (there is an oriented path from every other node to the sink node).
Česky: network (síť) je orientovaný graf $G$, kde každá hrana $e$ nese dvě čísla — maximum capacity $u(e)$ (kapacita: víc než $u(e)$ hranou protéct nesmí) a minimum capacity $l(e)$ (dolní mez: míň než $l(e)$ taky ne) — a dva vyznačené vrcholy: source $s$ (zdroj) a sink $t$ (stok). Ostatním vrcholům říkáme vnitřní.
Zkus sám: definice navíc chce, aby z $s$ vedla orientovaná cesta do každého vrcholu a z každého vrcholu do $t$. Proč si takový předpoklad můžeme dovolit — co bys udělal s vrcholem, do kterého se z $s$ vůbec nedá dostat?
Takový vrchol se žádné dopravy z $s$ do $t$ nemůže účastnit: nepřiteče do něj (resp. z něj neodteče) nic, co by mělo se zdrojem a stokem něco společného. Můžeš ho i s jeho hranami ze sítě vyhodit a úloha se nezmění. Předpoklad tedy nic neomezuje — jen říká „síť už je takhle uklizená“.
Malá síť na hraní (popisek hrany = $l(e),\ u(e)$):
Tok a Kirchhoffův zákon
Zkus sám: do vnitřní křižovatky potrubí přitéká 5 litrů za sekundu, ale odtéká jen 3. Co se v křižovatce děje? A jaká rovnost musí platit, když je proudění „steady and lossless“?
Každou sekundu se v křižovatce „ztratí“ 2 litry — buď se tam voda hromadí (a křižovatka brzy bouchne), nebo někudy uniká. Ustálené bezeztrátové proudění obojí zakazuje, takže ve vnitřní křižovatce musí platit přítok = odtok. Jediné dva vrcholy, kde rovnost neplatí, jsou $s$ (tok vyrábí) a $t$ (tok polyká).
$f : E(G) \to \mathbb{R}^+_0$ is the flow if Kirchhoff law $\sum_{e \in \delta^-(v)} f(e) = \sum_{e \in \delta^+(v)} f(e)$ is valid for every node except $s$ and $t$.
Flow (tok) je tedy libovolné nezáporné ohodnocení hran, které v každém vrcholu kromě $s$ a $t$ splňuje Kirchhoff law (Kirchhoffův zákon, zákon zachování toku): součet toku na hranách vstupujících do $v$ (množina $\delta^-(v)$ [L0.2]) se rovná součtu na hranách vystupujících ($\delta^+(v)$). Jméno je vypůjčené z fyziky — je to přesně Kirchhoffův zákon o proudu v elektrickém uzlu.
Stejná síť, teď i s tokem (popisek hrany = $l(e),\ f(e),\ u(e)$ — tohle pořadí používá i zkouška):
Zkus sám: ověř Kirchhoffův zákon ve vrcholech $a$ a $b$ na obrázku.
Vrchol $a$: dovnitř $f(s,a) = 3$; ven $f(a,b) + f(a,t) = 1 + 2 = 3$. ✓
Vrchol $b$: dovnitř $f(s,b) + f(a,b) = 1 + 1 = 2$; ven $f(b,t) = 2$. ✓
U $s$ a $t$ rovnost neplatí a platit nemá: z $s$ čistě odtékají 4 jednotky, do $t$ 4 přitékají.
Přípustný tok
Feasible flow must satisfy $f(e) \in \langle l(e), u(e) \rangle$.
There might be no feasible flow when $l(e) > 0$.
Feasible flow (přípustný tok) = tok, který se na každé hraně vejde do mezí: $l(e) \le f(e) \le u(e)$. Meze umí vyjádřit překvapivě hodně:
Zkus sám: co o hraně říkají omezení ze slidu 4 — $u_i = 10$, $l_j = 3$ a $l_k = u_k = 20$?
1:1 ze slidu 4: $u_i = 10$ — arc $i$ is capable of transporting 10 units maximum; $l_j = 3$ — arc $j$ must transport at least 3 units; $l_k = u_k = 20$ — arc $k$ transports exactly 20 units. Tedy: horní mez = „nejvýš“, dolní mez = „aspoň“ a $l = u$ přibije tok hrany na přesnou hodnotu — žádná volnost.
Nebezpečná polopravda: „nulový tok je vždy přípustný“Při $l \equiv 0$ ano — $f \equiv 0$ meze triviálně splní a každý algoritmus z něj může vystartovat. Jakmile ale má některá hrana $l(e) > 0$, nulový tok přípustný není a přípustný tok dokonce nemusí existovat vůbec (vyzkoušíš si v úloze T02 dole). Proto zkouškové zadání Ford-Fulkersona rovnou dává přípustný tok $f$ v popisku $(l_e, f_e, u_e)$ — a proto existuje samostatná konstrukce počátečního přípustného toku, kterou potkáš v [L4.7]; rozhodovací verzi s bilancemi pak v [L4.6].
Hodnota toku a problém maximálního toku (slide 4)
Zkus sám: tok je rozprostřený po celé síti. Jak ho „změřit“ jedním číslem? Proč nedává smysl prostě sečíst všechna $f(e)$?
Jedna jednotka zboží putující po cestě o čtyřech hranách by se v součtu $\sum_e f(e)$ započítala čtyřikrát — to neměří, kolik sítí proteklo, ale jak dlouhé trasy zboží jede. Správné měřidlo: postav se ke zdroji a počítej, kolik z něj čistě odteče (odtok minus případný přítok zpět do $s$). Díky Kirchhoffovu zákonu se nic cestou neztratí, takže totéž číslo naměříš i u stoku $t$.
Given a network $(G, l, u, s, t)$. The goal is to find the feasible flow $f$ from the source to the sink that maximizes $\sum_{e \in \delta^+(s)} f(e) - \sum_{e \in \delta^-(s)} f(e)$ (i.e. to send the maximum volume of the flow from $s$ to $t$).
$\delta^+(s)$ is a set of arcs leaving node $s$
$\delta^-(s)$ is a set of arcs entering node $s$ (often we do not consider these arcs).
Číslu $\sum_{e \in \delta^+(s)} f(e) - \sum_{e \in \delta^-(s)} f(e)$ budeme říkat hodnota toku a značit $|f|$. V naší malé síti žádná hrana do $s$ nevstupuje, takže $|f| = f(s,a) + f(s,b) = 3 + 1 = 4$. Maximum flow problem (problém maximálního toku) = najdi přípustný tok s největší hodnotou.
Tok jako LP — a měření na libovolné hranici (slide 8)
Definici umíme přepsat rovnou jako lineární program (LP znáš z [L0.7] Co je ILP a LP relaxace a celé K1) — proměnná $f(e) \in \mathbb{R}^+_0$ pro každou hranu, Kirchhoff jako rovnosti, meze jako nerovnosti:
$$ \begin{aligned} \max \quad & \sum_{e \in \delta^+(s)} f(e) - \sum_{e \in \delta^-(s)} f(e) \\ \text{s.t.} \quad & \sum_{e \in \delta^-(v)} f(e) = \sum_{e \in \delta^+(v)} f(e) \qquad & v \in V(G) \setminus \{s, t\} \\ & l(e) \le f(e) \le u(e) & e \in E(G) \end{aligned} $$
Žádné celočíselné proměnné — je to čisté LP. (Kdy a proč vyjde tok celočíselně „zadarmo“, se dozvíš později v kapitole; logická omezení, která už ILP vyžadují, přijdou v [L4.14].) Slide 8 k formulaci přidává nenápadnou poznámku, která je ve skutečnosti předzvěst nejdůležitější věty kapitoly:
Note that the following equation is valid for any set $A$ containing source $s$ but not containing sink $t$:
$$\sum_{e \in \delta^+(s)} f(e) - \sum_{e \in \delta^-(s)} f(e) = \sum_{e \in \delta^+(A)} f(e) - \sum_{e \in \delta^-(A)} f(e).$$
Homework: Prove it while using Kirchhoff's law.
Slovy: hodnotu toku $|f|$ nenaměříš jen u zdroje — stejné číslo dostaneš na hranici libovolné množiny vrcholů $A$ s $s \in A$, $t \notin A$ (ven přes hranici minus dovnitř přes hranici). Takovým hranicím se bude říkat řez (cut) a v [L4.4] z téhle rovnosti vyroste věta max-flow = min-cut.
Zkus sám: ověř rovnost na naší malé síti pro $A = \{s, a\}$.
Hrany ven z $A$: $(a,b)$ s $f = 1$, $(a,t)$ s $f = 2$ a $(s,b)$ s $f = 1$ → součet $4$. Hrany dovnitř do $A$: žádné. Takže $\sum_{\delta^+(A)} f - \sum_{\delta^-(A)} f = 4 - 0 = 4 = |f|$. ✓
Zkus sám (Homework ze slidu 8): dokaž rovnost Kirchhoffovým zákonem. Nápověda: sečti Kirchhoffovy rovnosti přes všechny vrcholy $v \in A$ a sleduj, co se stane s hranami, které mají oba konce uvnitř $A$.
(Rozepsání je naše — slide dává důkaz jen jako homework.) Sečti přes všechny $v \in A$ výraz $\sum_{e \in \delta^+(v)} f(e) - \sum_{e \in \delta^-(v)} f(e)$:
- Pro vnitřní vrcholy $v \in A \setminus \{s\}$ je tento výraz $0$ (Kirchhoff; $t \notin A$, takže jediný vrchol v $A$ bez Kirchhoffa je $s$). Celkový součet je proto roven příspěvku zdroje $\sum_{\delta^+(s)} f - \sum_{\delta^-(s)} f = |f|$.
- Teď totéž spočítej po hranách. Hrana s oběma konci v $A$ se v součtu objeví dvakrát: jednou jako vystupující ($+f(e)$ u svého počátku), jednou jako vstupující ($-f(e)$ u svého konce) — vyruší se. Hrana vedoucí ven z $A$ přispěje jen $+f(e)$, hrana dovnitř jen $-f(e)$, hrany mimo $A$ nepřispějí vůbec.
Součet je tedy zároveň $\sum_{e \in \delta^+(A)} f(e) - \sum_{e \in \delta^-(A)} f(e)$, a rovnost platí. $\blacksquare$
Zkoušková síť z 25. 5. 2026 — naučit se ji číst
Zkouškové zadání Ford-Fulkersona (25. 5. 2026) dává síť, kde každá hrana nese trojici $(l_e, f_e, u_e)$ — minimum capacity, feasible flow, maximum capacity. Samotný běh algoritmu přijde až v [L4.3] a řez v [L4.4]; dnes síť „jen“ přečteme brýlemi téhle lekce: je zadané $f$ opravdu přípustný tok a jakou má hodnotu?
Poznámka k přepisu: tištěné popisky obou diagonálních hran jsou ve zdrojových přepisech rozporné (sama banka úloh u $T_3 \to T_7$ uvádí korekci). Používáme jediné čtení konzistentní s oficiálním řešením banky: $T_3 \to T_7 = (0,1,1)$ a $T_4 \to T_5 = (0,0,8)$ — jen s ním je zadané $f$ vůbec tok.
Zkus sám: ověř Kirchhoffův zákon ve vrcholu $T_3$ (tři hrany ven, jedna dovnitř).
Dovnitř: $f(T_1, T_3) = 5$. Ven: $f(T_3, T_6) + f(T_3, T_5) + f(T_3, T_7) = 0 + 4 + 1 = 5$. ✓ Sedí — a všimni si, že bez korekce diagonály ($f_{37} = 1$) by to nesedělo.
Celá kontrola přípustnosti, vrchol po vrcholu, a výpočet hodnoty:
Tři rychlé kontroly, než začneš cokoli počítatU každé tokové úlohy na zkoušce se vyplatí 30 sekund: ① Kirchhoff v každém vnitřním vrcholu (odhalí překlep v zadání i ve vlastním výpočtu), ② meze $l \le f \le u$ na každé hraně — pozor hlavně na hrany s $l > 0$, ③ hodnota $|f|$ = čistý odtok z $s$ (a pro kontrolu totéž u $t$). Mimochodem: kapacity sedí vždy na hranách — kdyby zadání omezovalo průtok vrcholem, rozdělíš vrchol na dva stejným trikem, jako byl split vrcholu v [L2.6].
Key takeaways — L4.1- Síť = pětice $(G, l, u, s, t)$: orientovaný graf, dolní meze $l(e)$ a kapacity $u(e)$ na hranách, zdroj $s$, stok $t$.
- Tok $f: E(G) \to \mathbb{R}^+_0$ splňuje Kirchhoffův zákon v každém vrcholu kromě $s, t$: $\sum_{e \in \delta^-(v)} f(e) = \sum_{e \in \delta^+(v)} f(e)$ (vstup = výstup, nic se neztrácí ani nehromadí).
- Přípustný tok: navíc $l(e) \le f(e) \le u(e)$ na každé hraně. Při $l > 0$ není $f \equiv 0$ přípustný a přípustný tok nemusí existovat vůbec.
- Hodnota toku $|f| = \sum_{e \in \delta^+(s)} f(e) - \sum_{e \in \delta^-(s)} f(e)$; díky Kirchhoffovi naměříš totéž číslo na hranici libovolné množiny $A \ni s$, $t \notin A$ — předzvěst řezu [L4.4].
- Max flow problem: najdi přípustný tok maximalizující $|f|$; jako LP má jen Kirchhoffovy rovnosti + meze na hranách.
- Zkouškový formát popisku hrany: $(l_e, f_e, u_e)$ — minimum capacity, feasible flow, maximum capacity.
“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.”
Edge list — $(l_e, f_e, u_e)$: $T_1{\to}T_2$: $0,4,4$; $T_1{\to}T_3$: $2,5,5$; $T_1{\to}T_4$: $0,0,7$; $T_2{\to}T_6$: $0,4,7$; $T_3{\to}T_6$: $0,0,6$; $T_3{\to}T_5$: $1,4,4$; $T_3{\to}T_7$: $0,1,1$; $T_4{\to}T_5$: $0,0,8$; $T_4{\to}T_7$: $0,0,1$; $T_6{\to}T_8$: $0,4,7$; $T_5{\to}T_8$: $0,4,8$; $T_7{\to}T_8$: $1,1,4$. (Síť je nakreslená výše ve výkladu.)
Originální otázky a), b) vyřešíme až v [L4.3] a [L4.4] — dnes na síti procvičíme přesně to, co umí tahle lekce. Otázky (i)–(iii) jsou naše vlastní:
- Verify that the prescribed $f$ is a feasible flow.
- Compute the flow value $|f|$.
- Without running any algorithm, give an upper bound on the maximum flow value.
a) Co je v zadání?
Síť $(G, l, u, s{=}T_1, t{=}T_8)$ s 8 vrcholy a 12 hranami; každá hrana nese trojici $(l_e, f_e, u_e)$. Prostřední číslo je nabídnutý přípustný tok — zkouška ti ho dává jako startovní bod pro Ford-Fulkersona. My ověříme, že to přípustný tok opravdu je, změříme ho a odhadneme, kam až může maximální tok vyrůst.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice toku, přípustnosti a hodnoty $|f|$ (takeaways).
- [L0.2] Stupeň vrcholu — značení $\delta^+(v)$, $\delta^-(v)$.
c) Jak nad úlohou uvažovat?
(i) Přípustnost má dvě nezávislé části — kterou kontroluješ po vrcholech a kterou po hranách? Kolik vrcholů musíš projít (a které dva přeskočit)? (ii) Kde se hodnota toku odečítá a co kdyby do $T_1$ nějaká hrana vstupovala? (iii) Veškerý tok musí opustit $s$ — co ho shora omezuje, i kdyby zbytek sítě byl nekonečně štědrý? Existuje stejný argument u $t$? Které z obou omezení je těsnější?
d) Úplné řešení
(i) Kirchhoff ve vnitřních vrcholech $T_2, \ldots, T_7$ (vstup = výstup):
- $T_2$: $4 = 4$ ✓ ($f_{12} = f_{26}$)
- $T_3$: $5 = 0 + 4 + 1$ ✓ ($f_{13} = f_{36} + f_{35} + f_{37}$)
- $T_4$: $0 = 0 + 0$ ✓ ($f_{14} = f_{45} + f_{47}$)
- $T_5$: $4 + 0 = 4$ ✓ ($f_{35} + f_{45} = f_{58}$)
- $T_6$: $4 + 0 = 4$ ✓ ($f_{26} + f_{36} = f_{68}$)
- $T_7$: $1 + 0 = 1$ ✓ ($f_{37} + f_{47} = f_{78}$)
Meze $l \le f \le u$: hrany s $l > 0$ jsou tři: $T_1{\to}T_3$ ($2 \le 5 \le 5$ ✓), $T_3{\to}T_5$ ($1 \le 4 \le 4$ ✓), $T_7{\to}T_8$ ($1 \le 1 \le 4$ ✓). Zbylé hrany mají $l = 0$ a všude $f \le u$ (zkontroluj po řádcích tabulky). Takže $f$ je přípustný tok. ✓
(ii) Hodnota: do $T_1$ žádná hrana nevstupuje, takže $$|f| = f_{12} + f_{13} + f_{14} = 4 + 5 + 0 = 9.$$ Kontrola u stoku: $f_{68} + f_{58} + f_{78} = 4 + 4 + 1 = 9$ ✓ (Kirchhoff funguje).
(iii) Horní mez: všechen tok musí odtéct hranami $\delta^+(T_1)$, takže $$|f| \le u_{12} + u_{13} + u_{14} = 4 + 5 + 7 = 16.$$ Stejný argument u stoku: $|f| \le u_{68} + u_{58} + u_{78} = 7 + 8 + 4 = 19$. Těsnější je mez u zdroje, $16$. (To jsou jen dvě nejjednodušší „hranice“ ze slidu 8 — $A = \{T_1\}$ a $A = V \setminus \{T_8\}$; obecné řezy v [L4.4]. A spoiler: Ford-Fulkerson v [L4.3] dožene tok z 9 právě na 16, takže mez u zdroje je zde dokonce dosažená.)
Consider the network in the figure below; arc labels are $(l_e, u_e)$. (i) Prove that no feasible flow exists. (ii) Change the upper bound of a single arc as little as possible so that a feasible flow exists, and give one such flow.
a) Co je v zadání?
Síť se zdrojem $s$, stokem $t$ a dvěma vnitřními vrcholy; hrana $a \to t$ má dolní mez $l = 3$ (musí jí protéct aspoň 3), ale přívod do $a$ má kapacitu jen 2. Máme dokázat, že žádný přípustný tok neexistuje, a pak síť minimální úpravou jedné kapacity spravit.
b) Co k tomu budeme potřebovat?
- Tato lekce — Kirchhoffův zákon + meze $l \le f \le u$ (takeaways).
c) Jak nad úlohou uvažovat?
Důkaz neexistence = najít vrchol, kde se Kirchhoff a meze poperou. Co říká Kirchhoff o $f(s,a)$ a $f(a,t)$? Jaké nerovnosti na ně kladou meze? Dají se všechny tři podmínky splnit najednou? (Větev přes $b$ do konfliktu vůbec nemluví — proč?)
d) Úplné řešení
(i) Vrchol $a$ má jedinou hranu dovnitř a jedinou ven, takže Kirchhoff dává $f(s,a) = f(a,t)$. Meze ale chtějí $$f(a,t) \ge l(a,t) = 3 \quad\text{a}\quad f(s,a) \le u(s,a) = 2,$$ dohromady $3 \le f(a,t) = f(s,a) \le 2$ — spor. Žádný přípustný tok neexistuje. $\blacksquare$ (Větev $s \to b \to t$ je nevinná: její toky se v konfliktu nevyskytují, sama si vystačí třeba s $f = 0$, protože má $l = 0$.)
(ii) Konflikt zmizí, právě když $u(s,a) \ge 3$ — nejmenší úprava je zvýšit $u(s,a)$ z $2$ na $3$. Pak je přípustný např. tok $$f(s,a) = f(a,t) = 3, \qquad f(s,b) = f(b,t) = 0,$$ (Kirchhoff: $a$: $3 = 3$ ✓, $b$: $0 = 0$ ✓; meze všude ✓) s hodnotou $|f| = 3$. Systematickou konstrukci počátečního přípustného toku — bez hádání — dostaneš v [L4.7].