Malinko zobecníme problém toků v sítích. Nechť $G=(V, E )$ je orientovaný graf. Každá hrana $e\in E $ má kapacitu $c(e)$, kde $c: E \to \RR_+$. Každý vrchol $v\in V$ má požadavek $d(v)\in \RR$. Chceme, aby ve vrcholu $v$ zůstal přebytek toku $d(v)$. Vrchol $v$ s $d(v) \gt 0$ se chová jako spotřebič, vrchol $v$ s $d(v) \lt 0$ jako zdroj a vrchol $v$ s $d(v)=0$ jako normální vrchol.

Definice: Cirkulace s požadavky $\left\{ d(v) \right\}_{v\in V}$ 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) & f(v) = d(v) & \mbox{pro každý vrchol $v\in V$} \end{eqnarray}$$
Úkol: Existuje v síti $G$ cirkulace splňující požadavky?

Na obrázku je příklad cirkulace $f$ v grafu $G$. Hodnoty ve vrcholech označují požadavky $d(v)$ a hrany jsou označeny “$f(e)/c(e)$”.

Pozorování: Pokud v síti $G$ existuje cirkulace splňující požadavky $\left\{ d(v) \right\}_{v\in V}$, tak je $\sum_{v\in V} d(v) = 0$.
Důkaz: Použijeme počítání dvěma způsoby. Na jednu stranu je $X=\sum_{v\in V} d(v)$. To jsme sečetli příspěvky přebytků po vrcholech. Na druhou stranu můžeme příspěvky do $X$ počítat po hranách.1 Tok po každé hraně přispívá do $X$ dvakrát (za každý konec hrany). Jednou s kladným a podruhé se záporným znaménkem. Proto je $X=0$.

Pozorování zároveň říká, že pokud existuje cirkulace $f$, tak je $$|f|=\sum_{v\in V, d(v)\gt 0} d(v) = \sum_{v\in V, d(v)\lt 0} -d(v). $$

Jak tedy zjistit, zda v $G$ existuje cirkulace splňující požadavky? Nejprve zkontrolujeme, jestli $\sum_{v\in V, d(v)\gt 0} d(v) = -\sum_{v\in V, d(v)\lt 0} d(v) $. Pokud tato nutná podmínka platí, tak zkonstruujeme pomocný graf $G’=(V\cup\{ S,T \}, E‘)$.

  • Vytvoříme super-zdroj $S$ a spojíme ho se všemi vrcholy $v$, které mají $d(v)\lt 0$ (chovají se jako “zdroje”). Kapacitu hrany $Sv$ nastavíme na $-d(v)$.
  • Vytvoříme super-spotřebič $T$ a spojíme ho se všemi vrcholy $v$, které mají $d(v)\gt 0$ (chovají se jako “spotřebiče”). Kapacitu hrany $vT$ nastavíme na $d(v)$.

Ve výsledné síti (která už má jen jeden zdroj a jeden spotřebič) nalezneme maximální tok. Pokud je jeho velikost rovna $\sum_{v\in V, d(v)\gt 0} d(v)$, tak je restrikce2 nalezeného toku na původní graf platnou cirkulací. Pokud je velikost maximálního toku menší, tak platná cirkulace neexistuje (zkuste si to dokázat).

Jako důsledek poznatků o tocích v sítích dostáváme, že když jsou všechny kapacity hran a pořadavky toku ve vrcholech celočíselné, tak existuje platná cirkulace, která je celočíselná.