From fb49fbaed773cbcd4906b9c6a2ae78ed9284c284 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 7 Nov 2011 19:51:28 +0100 Subject: [PATCH] Dinic: Prepsan uvod a lemma o zlepsovany toku tokem --- 3-dinic/3-dinic.tex | 127 +++++++++++++++++++------------------------- 1 file changed, 54 insertions(+), 73 deletions(-) diff --git a/3-dinic/3-dinic.tex b/3-dinic/3-dinic.tex index 0a66a68..871d164 100644 --- a/3-dinic/3-dinic.tex +++ b/3-dinic/3-dinic.tex @@ -4,16 +4,17 @@ Na~minulé pøedná¹ce jsme si~ukázali Fordùv-Fulkersonùv algoritmus. Tento algoritmus hledal maximální tok tak, ¾e zaèal s~tokem nulovým a~postupnì ho -zvìt¹oval. Pro~ka¾dé zvìt¹ení potøeboval v~síti najít cestu, na~které mají -v¹echny hrany kladnou rezervu (po takovéto cestì mù¾eme poslat více, ne¾ po~ní -aktuálnì teèe). Ukázali jsme, ¾e pokud takováto cesta existuje, jde tok -vylep¹it (zvìt¹it). Zároveò pokud tok jde vylep¹it, pak takováto cesta -existuje. Dokázali jsme, ¾e pro~racionální kapacity je algoritmus koneèný -a~najde maximální tok. +zvìt¹oval. Pro~ka¾dé zvìt¹ení potøeboval v~síti najít {\I nenasycenou cestu,} +tedy takovou, na~ní¾ mají v¹echny hrany kladnou rezervu. Podél takové cesty +pak tok zvìt¹il. -Fordùv-Fulkersonùv algoritmus má ov¹em znaèné nevýhody. Funguje pouze -pro~racionální kapacity a~je pomìrnì pomalý. Nyní si~uká¾eme jiný algoritmus, -který nevylep¹uje tok pomocí cest, ale pomocí tokù~\dots +Ukázali jsme, ¾e tato cesta existuje právì tehdy, kdy¾ tok je¹tì není +maximální. Také jsme dokázali, ¾e pro racionální kapacity je tento +algoritmus koneèný a v¾dy najde maximální tok. V~obecném pøípadì to +ov¹em mù¾e trvat velice dlouho. + +Nyní uká¾eme trochu slo¾itìj¹í, ale výraznì rychlej¹í algoritmus zalo¾ený +na my¹lence nezlep¹ovat toky pomocí cest, ale rovnou pomocí tokù~\dots \h{Sí» rezerv a zlep¹ující toky} @@ -21,79 +22,59 @@ kter kde~$r(e)$ je rezerva hrany~$e$ pøi toku~$f$. Je dùle¾ité si~uvìdomit, ¾e sí» rezerv konstruujeme pro konkrétní tok v~pùvodní síti. -Od pùvodní sítì se li¹í pouze tím, ¾e kapacit hran jsme nahradili jejich rezervami. -Pøipomeòme je¹tì, ¾e rezervu hrany~$uv$ jsme definovali jako +Od pùvodní sítì se li¹í pouze tím, ¾e kapacity hran jsme nahradili jejich rezervami. +Pøipomeòme je¹tì, ¾e rezervu hrany~$uv$ jsme definovali vztahem $$r(uv) = c(uv) - f(uv) + f(vu).$$ -Nyní uká¾eme, jak toky zlep¹ovat pomocí tokù v~pøíslu¹né síti rezerv: +Nyní uká¾eme, jak tok zlep¹it pomocí toku v~pøíslu¹né síti rezerv: -\s{Lemma (o~zlep¹ování tokù):} Pro libovolný tok~$f$ v~síti~$S$ a libovolný tok~$g$ v~síti $R=(S,f)$ +\s{Lemma (o~zlep¹ování tokù):} Pro libovolný tok~$f$ v~síti~$S$ a libovolný tok~$g$ v~síti $R(S,f)$ lze v~èase $\O(m)$ nalézt tok~$f'$ v~síti~$S$ takový, ¾e $\vert f' \vert = \vert f \vert + \vert g \vert$. \proof -Nejprve uká¾eme, jak tok~$f'$ sestrojit. V~druhém kroku doká¾eme, ¾e konstrukce -opravdu dává korektní tok. Nakonec nahlédneme, ¾e jeho velikost je taková, jakou +Nejdøív uká¾eme, jak tok~$f'$ sestrojit. Poté doká¾eme, ¾e konstrukce opravdu +dává korektní tok. Nakonec nahlédneme, ¾e jeho velikost je taková, jakou lemma slibuje. -\>{\I Konstrukce~$f'$:} Pro ka¾dou dvojici hran $uv$ a $vu$ urèíme $f'(uv)$ a $f'(vu)$ následovnì: - -\def\irtri{\raise0.2ex\hbox{$\triangleright$}} % Signs frequently used for \itemize - -\itemize\ibull -\:Pokud $g(uv)=g(vu)=0$, polo¾íme: - \itemize\irtri - \:$f'(uv) := f(uv)$, - \:$f'(vu) := f(vu)$. - \endlist - -\:Pokud~$g(uv)>0$ a~$g(vu)=0$, pak polo¾me: - \itemize\irtri - \:$\varepsilon := \min (g(uv), f(vu))$, - \:$f'(uv) := f(uv) + g(uv) - \varepsilon$. - \:$f'(vu) := f(vu) - \varepsilon$, - \endlist - -\:Pøípad~$g(uv)=0$ a~$g(vu)>0$ vyøe¹íme symetricky. - -\:V~ostatních pøípadech je $g(uv)>0$ i $g(vu)>0$. Tehdy odeèteme od~toku~$g$ cirkulaci po cyklu $uvu$: - \itemize\irtri - \:$\delta := \min (g(uv),g(vu))$, - \:$g'(uv) := g(uv) - \delta$, - \:$g'(vu) := g(vu) - \delta$. - \endlist - Tím jsme velikost toku~$g$ nezmìnili a alespoò jednu z~hodnot $g(uv)$ a $g(vu)$ - jsme vynulovali, tak¾e mù¾eme pou¾ít nìkterý z~pøedchozích pøípadù. - -\endlist - -\>{\I Funkce~$f'$ je tok:} -Nejprve si v¹imneme, ¾e na¹e konstrukce nikdy nevytváøí záporná èísla, ani èísla -pøekraèující kapacity (ovìøte si v~jednotlivých pøípadech a vyu¾ijte toho, ¾e funkce~$g$ -je omezena kapacitami v~síti rezerv, èili rezervami v~pùvodní síti). - -Zbývá ovìøit Kirchhoffùv zákon. Doká¾eme, ¾e seètením tokù seèteme i jejich pøebytky, -tedy ¾e pro v¹echny vrcholu~$v$ je $f'^\Delta(v) = f^\Delta(v) + g^\Delta(v)$. -Pokud tedy zákon platil pro $f$ i~$g$, musí platit i pro~$f'$. - -Uvedenou rovnost ovìøíme takto: Víme, ¾e k~pøebytku vrcholu~$v$ ka¾dá dvojice hran -$uv$ a $vu$ pøispívá hodnotou $\delta = f(uv) - f(vu)$. Nahlédneme, ¾e tato hodnota se zvý¹í -o~$g(uv) - g(vu)$, co¾ je pøesnì pøíspìvek uvedené dvojice hran k~pøebytku~$g^\Delta(v)$: - - \itemize\irtri - \:V~prvním pøípadì na¹í konstrukce se $\delta$ nemìní a $g(uv) = g(vu) = 0$. - \:V~druhém pøípadì se $\delta$ zvìt¹í o~$g(uv) - \varepsilon + \varepsilon = g(uv)$, - pøièem¾ $g(vu)=0$. - \:Tøetí pøípad symetricky. - \:Ve~ètvrtém pøípadì upravíme~$g$ tak, ¾e se nezmìní $g(uv)-g(vu)$ a pokraèujeme - nìkterým z~pøedchozích pøípadù. - \endlist - -Tím jsme dokázali, ¾e~$f'$ je tok v~síti~$S$. - -\>{\I Velikost toku~$f'$:} -Pou¾ijme právì dokázaný vztah pro souèet pøebytkù: +{\I Zjednodu¹ení toku~$g$:} Abychom si usnadnili práci, upravíme nejprve tok~$g$ tak, +aby pro ka¾dou dvojici hran $uv$ a~$vu$ byl tok~$g$ nenulový nejvý¹e na jedné z~nich. +Kdyby toti¾ jak $g(uv)$, tak $g(vu)$ byly kladné, mù¾eme od obou hodnot odeèíst +tu men¹í z~nich. Tím jsme nezmìnili pøebytky vrcholù, tím pádem ani velikost toku, +a~tok po jedné z~hran jsme vynulovali. + +{\I Konstrukce~$f'$:} Pro ka¾dou dvojici hran $uv$ a~$vu$ takovou, ¾e $g(vu)=0$, +definujeme funkci~$f'$ následovnì: +$$\eqalign{ + \delta &:= \min(f(vu), g(uv)) \cr + f'(vu) &:= f(vu) - \delta \cr + f'(uv) &:= f(uv) + g(uv) - \delta \cr +}$$ +(Jinými slovy toté¾ jako pøi zlep¹ování toku ve~Fordovì-Fulkersonovì algoritmu.) + +{\I Proè je to tok:} Funkce~$f'$ jistì není na ¾ádné hranì záporná. Kapacity +také nepøekroèí: na hranì~$vu$ tok pouze sni¾ujeme, na hranì~$uv$ ho zvý¹íme jen +tehdy, kdy¾ $\delta < g(uv)$. Tehdy musí být $\delta = f(vu)$. Vyu¾ijeme toho, ¾e +$g$ je tok v~síti rezerv, tak¾e $g(uv) \le r(uv) = c(uv) - f(uv) + f(vu)$. +Proto $f'(uv) = f(uv) + g(uv) - \delta \le f(uv) + c(uv) - f(uv) + f(vu) - f(vu) += c(uv)$. + +Je¹tì ovìøíme, ¾e $f'$~splòuje Kirchhoffùv zákon. Uká¾eme, ¾e pro ka¾dý vrchol~$v$ +platí $f'^\Delta(v) = f^\Delta(v) + g^\Delta(v)$, tak¾e pokud zákon platil pro $f$ +i~$g$, musí platit i pro~$f'$. V¹imneme si, ¾e za hranu~$uv$ na¹e konstrukce zvý¹í +zvý¹í $f^\Delta(u)$ o~$-g(uv)$ a~$f^\Delta(v)$ o~$g(uv)$. To je pøesnì tolik, èím +tato hrana pøispívá k~$g^\Delta(u)$ a~$g^\Delta(v)$. Pro hranu~$vu$, po které +neteklo nic, platí triviálnì toté¾. + +{\I Velikost toku:} Staèí vyu¾ít toho, ¾e pøebytky se seèetly, abychom získali: $$\vert f' \vert = f'^\Delta(s) = f^\Delta(s) + g^\Delta(s) = \vert f \vert + \vert g \vert.$$ -\qeditem + +{\I Èasová slo¾itost:} Jak zjednodu¹ení toku~$g$, tak výpoèet toku~$f'$ trvají +$\O(1)$ pro ka¾dou hranu, celkovì tedy $\O(m)$. +\qed + +V¹imnìte si, ¾e zlep¹ení po nenasycené cestì je speciálním pøípadem tohoto +postupu -- odpovídá toti¾ toku v~síti rezerv, který je konstantní na oné cestì +a v¹ude jinde nulový. \h{Dinicùv algoritmus} -- 2.39.2