Motivace (pro toky): Ve městě Žízeň je velký nedostatek vody. Město je propojeno potrubní sítí s vodní nádrží Kupavody, kde je vody dostatek. Schéma vodovodní sítě je na obrázku. Každá trubka je jinak široká a proto je ve schématu u každé trubky napsán maximální počet litrů, který trubkou proteče za jednu minutu. Vaším úkolem je zjistit, kolik nejvíce litrů doteče z přehrady do města.1

Toky v sítích nejsou jen o vodě v potrubí. V analogických sítích může protékat elektrický proud, auta ve městě, telefonní hovory, peníze nebo pakety v počítačových sítích.2

Motivace (pro řezy): V Hádavém království jsou některé dvojice měst spojeny přímou silnicí. Po silniční síti se dá dostat z každého města do libovolného jiného. Jak už to tam bývá zvykem, dvě velká města Velezdroje a Hustostoky se pohádala o to, z které strany se loupe banán. Radní obou měst chtějí rozkopat některé silnice tak, aby už nebylo možné dojet po silnici z jednoho města do druhého. Prý tím zabrání šíření špatných názorů. Které silnice mají silničáři překopat, aby splnili úkol a zároveň překopali co nejméně silnic?


Protože je kapitola o tocích v sítích poměrně rozsáhlá, pojďme si stručně představit obsah hlavních sekcí.

Srovnání algoritmů pro hledání maximálního toku

Přehled časových složitostí variant algoritmu vylepšující cesty.

Dinic $\OO(n^2 m)$
3 indové $\OO(n^3)$
nejlepší známé $\OO(mn \log(n^2/m))$
jednotkové kapacity $\OO(\sqrt m \cdot m)$
jednotkové kapacity, prostý graf $\OO( n^{2/3} \cdot m)$
jednotkové kapacity, vstupní nebo výstupní stupeň $\leq 1$ $\OO(\sqrt n\cdot m)$
celočíselné kapacity $\OO(|f|\cdot n + nm)$
celočíselné kapacity $\leq U$ $\OO(Un^2 + nm)$
scaling (celočíselné kapacity $\leq U$) $\OO(nm \log U)$

Prostým grafem myslíme graf bez násobných hran.3 Ostatní algoritmy fungují i na multigrafech.

Golgberg a Tarjan [GT87] přišli s algoritmem na nalezní blokujícího toku v acyklickém orientovaném grafu v čase $\OO(m \log(n^2/m))$. Důsledkem toho dostáváme algoritmus pro hledání maximálního toku v obecných orientovaných grafech v čase $\OO(nm \log(n^2/m))$.

Většinu algoritmů pro speciální případy naleznete ve cvičeních. Podle navrhnutých základních myšlenek nebo kostry algoritmu si sami zkusíte domyslet detaily, sestavit algoritmus a dokázat, že funguje. Upočítání časových složitostí pro speciální případy naleznete v [MaresKGA].

Přehled časových složitostí variant push-relabel algoritmu.

maximum distance push-relabel $\OO(n^2 \sqrt m)$
jednotkové kapacity $\OO(nm)$
celočíselné kapacity $\leq k$ $\OO(knm)$
scaling přebytků $\OO(nm+ n^2\log U)$

S některými variantami se opět seznámíte ve cvičeních.

Scaling přebytků je varianta push-relabel algoritmu, která protlačuje tok z vrcholů s dostatečně vysokým přebytkem do vrcholů s dostatečně nízkým přebytkem, přičemž nikdy nedovolíme, aby byl přebytek příliš velký. Myšlenka scalingu je podobná scalingu u algoritmů vylepšující cesty. Celkem hezky je to popsané v [AO1989].

Poznamenejme, že push-relabel algoritmus se chová dobře i na speciálních grafech. Například na bipartitním grafu s $n_1$ a $n_2$ vrcholy doplněném o zdroj a spotřebič běží FIFO push-relabel algoritmus v čase $\OO( n_1 m + n_1^3 )$ (podívejte se do [AOS94]).

Nejlepší známé řešení pro toky v sítích používá nový přístup k problému. Je to algoritmus Golberg-Rao [GR1998] s časovou složitostí $\OO(m \sqrt m \log(n^2/m) \log U)$.4

Praktické chování.

Poznamenejme, že algoritmus push-relabel se v praxi chová velice dobře a je podstatně rychlejší než algoritmy vylepšující cesty. (Můžeme si to vysvětlit tím, že pomocí platného označkování snadněji “udržujeme” vrstevnatou síť a nemusíme ji pokaždé přepočítávat.)

Push-relabel algoritmus můžeme ještě více zrychlit pomocí heuristiky popsané v podsekci [ref]push_relabel_heuristic[/ref].

Doporučená literatura

Zvídavého čtenáře můžeme odkázat na přehledový článek Goldberg, Tardos a Tarjan [GTT90] nebo knihu Ahuja, Magnanti a Orlin: Network Flows [AMO93]. Mezi hezké lecture notes patří Har-Peled [LNHarPeled]. Z česky psaných textů můžeme doporučit Mareš: Krajinou grafových algoritmů [MaresKGA] a Matoušek, Valla: Kombinatorika a grafy I. [MatValKG].