From 63bb7665a2105ed1321b6517f8018cd8e9eef08d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 23 Jan 2007 22:50:41 +0100 Subject: [PATCH] Doladeno povidani o scalingu a prehled variant Dinicova algoritmu. Tim by az na obrazky mely byt kapitoly o tocich hotove. --- 2-dinic/2-dinic.tex | 46 ++++++++++++++++++++++++--------------------- 1 file changed, 25 insertions(+), 21 deletions(-) diff --git a/2-dinic/2-dinic.tex b/2-dinic/2-dinic.tex index 1d3cb38..6512e00 100644 --- a/2-dinic/2-dinic.tex +++ b/2-dinic/2-dinic.tex @@ -214,25 +214,27 @@ $\O(Cn^2 + nm)$. \h{Scaling kapacit} -Základní my¹lenka je podobná, jako u algoritmu pro tøídìní dlouhých èísel postupnì po øádech pomocí -radix-sortu. Pro jistotu si ho pøipomeòme. Algoritmus nejprve setøídí èísla podle poslední +Pokud jsou kapacity hran vìt¹í celá èísla omezená nìjakou konstantou~$C$, mù¾eme si pomoci následujícím algoritmem. +Jeho základní my¹lenka je podobná, jako u~tøídìní èísel postupnì po øádech pomocí +radix-sortu neboli pøíhrádkového tøídìní. Pro jistotu si ho pøipomeòme. Algoritmus nejprve setøídí èísla podle poslední (nejménì významné) cifry, poté podle pøedposlední, pøedpøedposlední a tak dále. \figure{dinic-sort.eps}{Kroky postupného tøídìní podle øádù}{0.4\hsize} -V na¹em pøípadì budeme postupnì budovat sítì a v nich poèítat toky, a¾ nakonec získáme tok pro celou sí». +V na¹em pøípadì budeme postupnì budovat sítì èím dál podobnìj¹í zadané +síti a v~nich poèítat toky, a¾ nakonec získáme tok pro ni. -Pøedpokládejme celoèíselné kapacity. Maximální tok v síti $G$ budeme hledat tak, ¾e hranám postupnì -budeme zvìt¹ovat kapacity bit po bitu v binárním zápisu a¾ k jejich skuteèné kapacitì. -Pøitom po~ka¾dém posunu zavoláme Dinicùv algoritmus. Pomocí pøedchozího odhadu uká¾eme, ¾e jedno -volání Dinice nebude pøíli¹ drahé. +Pøesnìji: Maximální tok v síti $G$ budeme hledat tak, ¾e hranám postupnì +budeme zvìt¹ovat kapacity bit po bitu v~binárním zápisu a¾ k~jejich skuteèné kapacitì. +Pøitom po~ka¾dém posunu zavoláme Dinicùv algoritmus, aby dopoèítal maximální tok. +Pomocí pøedchozího odhadu uká¾eme, ¾e jeden takový krok nebude pøíli¹ drahý. \figure{dinic-scaling-original.eps}{Pùvodní sí», na hranách jsou jejich kapacity v binárním zápisu}{0.4\hsize} -Oznaème $k$ poèet bitù v zápisu nejvìt¹í kapacity z celé sítì. $k = \lfloor \log_2C \rfloor$. +Oznaème $k$ index nejvy¹¹ího bitu v~zápisu kapacit v~zadané síti ($k = \lfloor \log_2C \rfloor$). Postupnì budeme budovat sítì $G_i$ s~kapacitami $c_i(e) = \lfloor {c(e) / 2^{k-i}} \rfloor$. $G_0$ je nejoøezanìj¹í sí», kde ka¾dá hrana má kapacitu rovnou nejvy¹¹ímu bitu v~binárním zápisu -její skuteèné kapacity. $G_k$ je pùvodní sí» $G$. +její skuteèné kapacity, a¾ $G_k$ je pùvodní sí» $G$. $$ c_{i+1}(e) = \left\{ \eqalign{ @@ -246,29 +248,31 @@ $$ Na spoètení maximálního toku $f_i$ v síti $G_i$ zavoláme Dinicùv algoritmus, ov¹em do zaèátku nepou¾ijeme nulový tok, nýbr¾ tok $2f_{i-1}$. Rozdíl toku z inicializace a výsledného bude malý, toti¾: -$$ \vert f_i\vert - \vert 2f_{i-1}\vert \leq m.$$ + +\s{Lemma:} $\vert f_i\vert - \vert 2f_{i-1}\vert \leq m.$ \proof -Vezmeme minimální øez $R$ v $G_{i-1}$. Platí $\vert f_{i-1}\vert = \vert R\vert$\foot{F-F vìta.}. -Øez $R$ obsahuje $\leq m$ hran. V $G_{i}$ má øez $R$ kapacitu maximálnì $2\vert R\vert+m$. -Maximální tok je omezen ka¾dým øezem. Tedy i øezem $R$. Proto tok vzroste o $\leq m$. +Vezmeme minimální øez $R$ v~$G_{i-1}$. Podle F-F vìty víme, ¾e $\vert f_{i-1}\vert = \vert R\vert$. +Øez $R$ obsahuje $\leq m$ hran, a~tedy v~$G_{i}$ má tentý¾ øez kapacitu maximálnì $2\vert R\vert+m$. +Maximální tok je omezen ka¾dým øezem, tedy i øezem $R$, a~proto tok vzroste nejvý¹e o~$m$. \qed -Proto podle pøedchozího odhadu výpoèet toku $f_i$ trvá $\O(mn)$. Takový tok se bude poèítat $k$-krát, -tak¾e celková slo¾itost vyjde $\O(mn\log C)$. +Podle pøedchozího odhadu pro celoèíselné kapacity výpoèet toku $f_i$ trvá $\O(mn)$. +Takový tok se bude poèítat $k$-krát, proèe¾ celková slo¾itost vyjde $\O(mn\log C)$. \h{Pøehled variant Dinicova algoritmu} -$$\vbox{\halign{# \hfil \quad &# \hfil \cr +\medskip + +\centerline{\vbox{\halign{# \hfil \quad &# \hfil \cr \it verze &\it èas \cr\noalign{\smallskip\hrule\smallskip} standardní &$\O(n^2m)$ \cr -jednotkové kapacity &$\O(nm)$ \cr -jednotkové kapacity podruhé &$\O(\sqrt{m}\cdot m) = \O(m^{3/2})$ \cr +jednotkové kapacity &$\O(\sqrt{m}\cdot m) = \O(m^{3/2})$ \cr jednotkové kapacity, 1 stupeò $\leq 1$ &$\O(\sqrt{n}\cdot m)$ \cr -jednotkové kapacity potøetí &$\O(n^{2/3}m)$ \cr +jednotkové kapacity, prostý graf &$\O(n^{2/3}m)$ \cr celoèíselné kapacity &$\O(\vert f\vert\cdot n + nm)$ \cr celoèíselné kapacity $ \leq C$ &$\O(Cn^2 + mn)$ \cr -celoèíselné kapacity $ \leq C$ &$\O(mn\log C)$ \cr -}}$$ +celoèíselné kapacity $ \leq C$ (scaling)&$\O(mn\log C)$ \cr +}}} \bye -- 2.39.2