Definice: Síť $( G , s, t, c)$ je orientovaný graf $ G =(V, E )$, který má dva speciální vrcholy: zdroj $s$ a spotřebič $t\in V$ (z anglického source a target), a každá hrana $e$ má kapacitu $c(e)$, kde kapacita je funkce $c: E \to \RR_+$. Spotřebič je někdy označován jako stok.

Tok $f$ je funkce $f: E \to \RR_+$, která splňuje $$\begin{eqnarray} i) & 0\leq f(e) \leq c(e) & \mbox{pro každou hranu $e\in E $}\\ ii) & \sum\limits_{xv\in E } f(xv) = \sum\limits_{vx\in E } f(vx)& \mbox{pro každý vrchol $v\in V\setminus\{s,t\}$} \end{eqnarray}$$

Číslu $f(e)$ říkáme tok po hraně $e$ nebo také průtok hranou $e$. První podmínka říká, že průtok hranou je nezáporný a nemůže překročit kapacitu hrany. Druhá podmínka říká, že co do vrcholu přiteče, to z něj zase musí odtéci. Druhé podmínce se také říká zákon zachování toku, protože se tok ve vrcholech ani neztrácí1, ani nepřibývá (kromě zdroje a spotřebiče). V analogii v elektrických obvodech se druhé podmínce říká Kirchhoffův zákon. Pokud chceme explicitně vyjádřit, že mluvíme o toku ze zdroje $s$ do spotřebiče $t$, tak tok označíme jako $(s,t)$-tok.

Protože se v teorii o tocích vyskytuje rozdíl mezi přítokem do vrcholu $v$ a odtokem z vrcholu $v$ hodně často, tak si zavedeme zkrácené označení $$f(v)=
\sum\limits_{xv\in E } f(xv) –
\sum\limits_{vx\in E } f(vx) .
$$ Číslu $f(v)$ budeme říkat bilance vrcholu $v$ nebo také přebytek toku ve vrcholu $v$. Při čtení následujícího textu budeme muset být malinko opatrní na to, co je argumentem $f()$, protože $f(e)$ nebo $f(uv)$ je průtok hranou $e=uv$, ale $f(v)$ je bilance vrcholu $v$. Druhou podmínku z definice toku můžeme jednoduše vyjádřit jako $f(v)=0$.

Velikost toku $|f|$ je množství toku, které protéká ze zdroje do spotřebiče. Protože se tok ve vrcholech ani neztrácí ani nepřibývá, tak ho můžeme spočítat jako $|f|=f(t)$. Tedy jako tok, který přitéká do spotřebiče. Stejně bychom mohli velikost toku měřit jako $-f(s)$, což je velikost toku, který vytéká ze zdroje.

Doplněk množiny $R\subseteq V$ značíme $\overline{R}$. Tedy $\overline{R}=V\setminus R$. Množinu orientovaných hran $\delta(R)=\{ vw\in E \,|\, v\in R \,\&\, w\in \overline{\R} \}$ nazveme řezem určeným množinou $R\subseteq V$. Řez je $(s,t)$-řez, pokud $s\in R$ a $t\not\in R$. Tedy pokud řez odděluje zdroj od spotřebiče. Řez určený jediným vrcholem $v$ budeme zjednodušeně značit $\delta(v)$ místo $\delta(\{v\})$. Kapacita řezu $c(\delta(R)):=\sum_{e\in \delta(R)} c(e)$.

Pozor, je rozdíl mezi řezem v orientovaném grafu a řezem v neorientovaném grafu. Řez určený množinou $R$ v orientovaném grafu obsahuje jen hrany, které z $R$ vychází ven. Na proti tomu řez určený množinou $R$ v neorientovaném grafu obsahuje hrany, které mají jeden konec v $R$.

Pokud chceme hledat maximální tok nebo minimální řez v neorientovaném grafu, tak nahradíme každou neorientovanou hranu dvojicí šipek jdoucích proti sobě. Kapacity obou šipek budou stejné jako kapacita původní hrany. Maximální tok a minimální řez v takto vytvořeném orientovaném grafu odpovídá toku a řezu v původním neorientovaném grafu. Pro jednoduchost budeme v celé kapitole o tocích pracovat pouze s orientovanými grafy.

Příklad: Na následujícím obrázku je síť. U každé hrany $e$ jsou uvedeno “$f(e)/c(e)$”.

Velikost toku v síti na obrázku je $3$. Velikost řezu určeného vrcholy $\{s,a,b\}$ je $6$ a velikost opačného řezu, to je řezu určeného vrcholy $\{c,d,t\}$, je $1$.

Platí věta, že v každém grafu existuje maximální tok. Přímý důkaz věty vyžaduje pokročilejší znalosti matematické analýzy a proto ho neuvedeme. Větu dokážeme nepřímo tím, že si ukážeme algoritmy, které maximální tok najdou.

Lemma (o toku přes řez): Pro každý $(s,t)$-tok $f$ a každý $(s,t)$-řez $\delta(R)$ platí $$ f(\delta(R)) – f(\delta(\overline{R})) = f(t)$$
Důkaz: Spočítáme $X=\sum_{v\in \overline{R}} f(v)$ dvěma způsoby. Jednou přes příspěvky vrcholů, podruhé přes příspěvky hran.

Bilance všech vrcholů kromě zdroje a spotřebiče je rovna nule. Množina $\overline{R}$ obsahuje jen spotřebič $t$ a proto $X=f(t)$.

Na druhou stranu se podívejme na příspěvky od jednotlivých hran. Hrana $e=vw$ s oběma konci v $\overline{R}$ přispívá do bilance vrcholu $v$ hodnotou $-f(e)$ a do bilance vrcholu $w$ hodnotou $f(e)$. Proto je její celkový příspěvek do $X$ roven nule. Jediné hrany, které přispívají do $X$ něčím nenulovým, jsou ty které mají jeden konec v $R$ a druhý v $\overline{R}$. Můžeme je rozdělit na hrany $\delta(R)$ vedoucí z $R$ ven a na hrany $\delta(\overline{R})$ vedoucí z venku do $R$. Jejich příspěvky do $X$ jsou $f(\delta(R)) – f(\delta(\overline{R}))$.

Důsledek: Pro každý $(s,t)$-tok $f$ a každý $(s,t)$-řez $\delta(R)$ platí $$ f(t) \leq c(\delta(R)) $$
Důkaz: Z lemmatu „o toku přes řez“ dostáváme $f(t) \leq f(\delta(R)) \leq c(\delta(R))$. Druhá nerovnost platí, protože kapacita hrany je horním odhadem na průtok hranou.

Velikost každého $(s,t)$-řezu je horním odhadem na velikost toku. Řez je zároveň jednoduchým a snadno ověřitelným certifikátem, jak dokázat, že v síti větší tok neexistuje. Dokonce platí následující věta, která byla objevena Fordem a Fulkersonem v roce 1956 a nezávisle Kotzigem2 v témže roce.

Věta (o maximálním toku a minimálním řezu): Pokud existuje maximální $(s,t)$-tok, pak $$\max\{|f|\,:\, \mbox{$f$ je $(s,t)$-tok}\,\}=
\min\{c(\delta(R))\,:\,\mbox{$\delta(R)$ je $(s,t)$-řez}\, \} $$

Společně s důkazem věty si ukážeme i základní myšlenku, jak zvětšovat velikost toku. Předpokládejme, že už známe nějaký tok $f$. Pokud v grafu najdeme orientovanou cestu $sPt$ takovou, že pro každou hranu $e$ cesty $P$ je $f(e) \lt c(e)$, tak zvětšíme průtok cestou $P$ a tím zvětšíme i tok $f$. Tato myšlenka ale sama o sobě nestačí. Proč?

Pokud ze spotřebiče do zdroje vede hrana $ts$ s průtokem $f(ts) \gt 0$, tak celkový tok zvětšíme tím, že z $s$ do $t$ pošleme tok o velikosti $f(ts)$ po hraně $ts$ v protisměru. Ve skutečnosti nic v protisměru nepoteče. Průtoky hranou jdoucí proti sobě se odečtou. Místo toho, aby se z $t$ posílal do $s$ tok o velikosti $f(ts)$ (původní tok po hraně) a zároveň z $s$ do $t$ tok o velikosti $f(ts)$ (přidávaný tok po hraně), tak se vrcholy $s$ a $t$ dohodnou, že si každý nechá tok o velikosti $f(ts)$. Nebudou si nic vyměňovat, protože to vyjde na stejno.

Množství toku, které můžeme poslat po směru hrany $e$, nazveme rezerva po směru hrany. Její velikost je $c(e)-f(e)$. Množství toku, které můžeme poslat proti směru hrany $e$, nazveme rezerva proti směru hrany.3 Její velikost je $f(e)$.

Cestou v následující definici vylepšující cesty myslíme cestu, u které ignorujeme orientaci hran. Hranu cesty zorientovanou směrem od zdroje do spotřebiče nazveme dopřednou a opačně orientovanou hranu nazveme zpětnou. Cesta $v_0 e_1 v_1 e_2 v_2 \dots e_k v_k$ je vylepšující cesta pro tok $f$, pokud pro každou dopřednou hranu $e$ cesty platí $f(e) \lt c(e)$ a pro každou zpětnou hranu platí $f(e) \gt 0$. Cestu vedoucí ze zdroje $s$ do spotřebiče $t$ budeme zkráceně označovat jako $(s,t)$-cestu.

Lemma (o vylepšující cestě): Pokud v síti existuje vylepšující cesta $P$ pro tok $f$ vedoucí ze zdroje do spotřebiče, tak tok $f$ není maximální.
Důkaz: Tok $f$ můžeme vylepšit podél vylepšující cesty $sPt$. Nechť $\varepsilon = \min\{\varepsilon_1, \varepsilon_2\}$, kde $\varepsilon_1 = \min\{ c(e)-f(e)\,|\, \mbox{$e \in P$ je dopředná}\}$ a $\varepsilon_2 = \min\{ f(e)\,|\, \mbox{$e \in P$ je zpětná}\}$. Slovy se dá říci, že $\varepsilon$ je největší tok, který se dá poslat ze zdroje do spotřebiče podél cesty $P$. Vylepšením toku $f$ podél cesty $P$ dostaneme tok $f’$.

$$f'(e) :=
\begin{cases}f(e)+\varepsilon, & \mbox{$e\in P$ je dopředná hrana},\\
f(e)-\varepsilon, & \mbox{$e\in P$ je zpětná hrana},\\
f(e), & \mbox{$e\not\in P$.}\\
\end{cases} $$

Funkce $f’$ je opět tok, protože splňuje definici toku (ověřte).

Důkaz: (Věty o maximálním toku a minimálním řezu) Každý tok je menší nebo roven velikosti libovolného řezu (důsledek [ref]corollary_min_rez[/ref]). To dokazuje první nerovnost.

Pro důkaz druhé nerovnosti vezmeme maximální tok $f$ a budeme chtít najít řez stejné velikosti. V síti neexistuje vylepšující cesta ze zdroje do spotřebiče, protože jinak se dostaneme do sporu s lemmatem „o vylepšující cestě“.

Nechť $R=\{v\in V \,$ do kterých vede vylepšující cesta z $s\,\}$. Množina $\delta(R)$ je $(s,t)$-řez, protože z $s$ do $s$ vede vylepšující cesta nulové délky, ale z $s$ do $t$ žádná vylepšující cesta nevede. Pro každou hranu řezu $\delta(R)$ je $f(e)=c(e)$ a pro každou hranu řezu $\delta(\overline{R})$ je $f(e)=0$. Jinak by šla vylepšující cesta prodloužit do vrcholů mimo $R$. Podle lemmatu „o toku přes řez“ je velikost toku $f(s)=f(\delta(R))-f(\delta(\overline{R})) = c(\delta(R))$, což jsme chtěli ukázat.

Důsledek: Tok $f$ je maximální $\Longleftrightarrow$ neexistuje vylepšující cesta pro tok $f$.

Předchozí důkaz nám dokonce ukazuje, jak najít minimální řez, který dosvědčí, že větší tok neexistuje.