From 3d84914356a1e777595965ebc392beb92ad66aab Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 4 Nov 2011 19:06:06 +0100 Subject: [PATCH] Toky: Dalsi upravy --- 2-toky/2-toky.tex | 64 ++++++++++++++++++++++++--------------------- 3-dinic/3-dinic.tex | 24 ++++++++++------- 2 files changed, 49 insertions(+), 39 deletions(-) diff --git a/2-toky/2-toky.tex b/2-toky/2-toky.tex index b1d8bc5..06259d8 100644 --- a/2-toky/2-toky.tex +++ b/2-toky/2-toky.tex @@ -1,6 +1,6 @@ \input lecnotes.tex -\prednaska{2}{Toky v sítích}{(zapsala Markéta Popelová)} +\prednaska{2}{Toky v sítích}{} \s{První motivaèní úloha:} {\I Rozvod èajovodu do~v¹ech uèeben.} \smallskip @@ -31,6 +31,10 @@ Jak p \figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{2.5in} +\s{Konvence:} Nebude-li hrozit nedorozumìní, budeme hranu z~vrcholu~$u$ do vrcholu~$v$ +znaèit $uv$ namísto formálnìj¹ího, ale ménì pøehledného $(u,v)$. Podobnì pro neorientovaný +pí¹eme $uv$ namísto $\{u,v\}$. + \s{Definice:} {\I Tok} je funkce $f:E \to {\bb R}_{0}^{+}$ taková, ¾e~platí: \numlist{\ndotted} \:Tok po~ka¾dé hranì je omezen její kapacitou: $\forall e \in E : f(e)\le c(e)$. @@ -83,7 +87,7 @@ toku bude zjevn \s{První pokus:} Hledejme cestu $P$ ze~$z$ do~$s$ takovou, ¾e~$\forall e \in P: f(e) < c(e)$ (po~v¹ech jejích hranách teèe ostøe ménì, ne¾ jim dovolují jejich kapacity). Pak zjevnì mù¾eme tok upravit tak, aby se~jeho velikost -zvìt¹ila. Zvolme $$\varepsilon := \min_{e \in P} (c(e) - f(e)).$$ Nový tok $f'$ +zvìt¹ila. Zvolme $$\varepsilon := \min_{e \in P} \left(c(e) - f(e)\right).$$ Nový tok $f'$ pak definujme jako $f'(e):=f(e) + \varepsilon$. Kapacity nepøekroèíme ($\varepsilon$ je nejvìt¹í mo¾ná hodnota, abychom tok zvìt¹ili, ale nepøekroèili kapacitu ani jedné z~hran cesty $P$) a~Kirchhoffovy zákony zùstanou neporu¹eny, nebo» zdroj @@ -108,7 +112,7 @@ proti sm \s{Definice:} {\I Rezerva hrany} $uv$ je $r(uv):=c(uv) - f(uv) + f(vu).$ \smallskip -Algoritmus bude vypadat následovnì. Postupnì dok¾eme, ¾e je koneèný a ¾e v~ka¾dé +Algoritmus bude vypadat následovnì. Postupnì doká¾eme, ¾e je koneèný a ¾e v~ka¾dé síti najde maximální tok. \s{Algoritmus (Fordùv-Fulkersonùv)} @@ -148,28 +152,24 @@ takov \s{Maximalita:} Kdy¾ se algoritmus zastaví, je tok~$f$ maximální? K~tomu se bude hodit zavést øezy. -\s{Definice:} {\I Øez} je uspoøádaná dvojice mno¾in vrcholù ($A,B$) taková, ¾e -$A$ a $B$ jsou disjunktní, pokrývají v¹echny vrcholy, $A$ obsahuje zdroj a $B$ -obsahuje stok. Neboli $A \cap B = \emptyset$, $A \cup B = V$, $z \in A$, $s \in B$. +\s{Definice:} Pro libovolné dvì mno¾iny vrcholù $A$ a~$B$ budeme znaèit $E(A,B)$ +mno¾inu hran vedoucích z~$A$ do~$B$, tedy $E(A,B) = E\cap (A\times B)$. +Je-li dále $f$ nìjaká funkce pøiøazující hranám èísla, oznaèíme: -\>Ka¾dému øezu pøirozenì pøiøadíme mno¾iny hran: \itemize\ibull -\:$E^+(A,B) = E \cap (A\times B)$ (hrany \uv{zleva doprava}) -\:$E^-(A,B) = E \cap (B\times A)$ (hrany \uv{zprava doleva}) -\:$E^\Delta(A,B) = E^+(A,B) \cup E^-(A,B)$ (v¹echny hrany øezu) +\:$f(A,B) = \sum_{e\in E(A,B)} f(e)$ (prùtok z~$A$ do~$B$) +\:$f^\Delta(A,B) = f(A,B) - f(B,A)$ (èistý prùtok z~$A$ do~$B$) \endlist -\>Také pro libovolnou funkci $f: E\rightarrow {\bb R}$ zavedeme: -\itemize\ibull -\:$f^+(A,B) = \sum_{e\in E^+(A,B)} f(e)$ (prùtok pøes øez zleva doprava) -\:$f^-(A,B) = \sum_{e\in E^-(A,B)} f(e)$ (prùtok zprava doleva) -\:$f^\Delta(A,B) = f^+(A,B) - f^-(A,B)$ (èistý prùtok) -\endlist +\s{Definice:} {\I Øez} je uspoøádaná dvojice mno¾in vrcholù ($A,B$) taková, ¾e +$A$ a $B$ jsou disjunktní, pokrývají v¹echny vrcholy, $A$ obsahuje zdroj a $B$ +obsahuje stok. Neboli $A \cap B = \emptyset$, $A \cup B = V$, $z \in A$, $s \in B$. +Mno¾inì~$A$ budeme øíkat {\I levá mno¾ina,} mno¾inì~$B$ {\I pravá.} -\>{\I Kapacita øezu} budeme øíkat souètu kapacit hran zleva doprava, tedy $c+(A,B)$. +\>{\I Kapacitu øezu} definujeme jako souèet kapacit hran zleva doprava, tedy $c(A,B)$. -\s{Poznámka:} Øezy se~dají definovat více zpùsoby, jedna z~definic je, ¾e~øez -je mno¾ina hran grafu takových, ¾e~po~jejich odebrání se~graf rozpadne na~více +\s{Poznámka:} Øezy se~dají definovat více zpùsoby. Jiná obvyklá definice øezu øíká, +¾e øez je mno¾ina hran grafu, po~jejím¾ odebrání se~graf rozpadne na~více komponent. Tuto vlastnost mají i na¹e øezy, ale opaènì to nemusí platit. \s{Lemma:} Pro ka¾dý øez $(A,B)$ a ka¾dý tok~$f$ platí, ¾e $f^\Delta(A,B) @@ -189,14 +189,14 @@ rovnost je snadn zákona nulový pøebytek. \qed -\s{Dùsledek:} Pro ka¾dý tok~$f$ a ka¾dý øez $(A,B)$ platí $\vert f \vert \le c^+(A,B)$. +\s{Dùsledek:} Pro ka¾dý tok~$f$ a ka¾dý øez $(A,B)$ platí $\vert f \vert \le c(A,B)$. (Velikost ka¾dého toku je shora omezena kapacitou ka¾dého øezu.) \proof -$f^\Delta(A,B) = f^+(A,B) - f^-(A,B) \le f^+(A,B) \le c^+(A,B)$. +$f^\Delta(A,B) = f(A,B) - f(B,A) \le f(A,B) \le c(A,B)$. \qed -\s{Dùsledek:} Pokud $\vert f\vert = c^+(A,B)$, pak je tok~$f$ maximální a øez~$(A,B)$ +\s{Dùsledek:} Pokud $\vert f\vert = c(A,B)$, pak je tok~$f$ maximální a øez~$(A,B)$ minimální. Jinými slovy pokud najdeme dvojici tok a stejnì velký øez, mù¾eme øez pou¾ít jako certifikát maximality toku. Následující vìta nám zaruèí, ¾e je to mo¾né v¾dy: @@ -213,11 +213,11 @@ s~kladnou rezervou, tud a~stávající tok vylep¹il). Dále víme, ¾e~v¹echny hrany øezu mají nulovou rezervu, èili $\forall uv \in -E^+(A,B) : r(uv) = 0$ (kdyby mìla hrana $uv$ rezervu nenulovou, tedy kladnou, +E(A,B) : r(uv) = 0$ (kdyby mìla hrana $uv$ rezervu nenulovou, tedy kladnou, tak by vrchol $v$ patøil do~$A$). Proto po~v¹ech hranách øezu vedoucích z~$A$ do~$B$ teèe tolik, kolik jsou kapacity tìchto hran, a~po~hranách vedoucích z~$B$ do~$A$ neteèe nic, tedy $f(uv) = c(uv)$ a $f(vu) = 0$. Máme øez $(A,B)$ -takový, ¾e~$f^\Delta(A,B) = c^+(A,B)$. To znamená, ¾e~jsme na¹li maximální tok +takový, ¾e~$f^\Delta(A,B) = c(A,B)$. To znamená, ¾e~jsme na¹li maximální tok a~minimální øez. \qed Dokázali jsme tedy následující: @@ -234,7 +234,7 @@ Kdy To, ¾e~umíme najít celoèíselné øe¹ení není úplnì samozøejmé. (U~jiných problémù takové ¹tìstí mít nebudeme.) Uka¾me si rovnou jednu aplikaci, která právì celoèíselný tok vyu¾ije. -\s{Aplikace:} Hledání nejvìt¹ího párování v~bipartitních grafech. +\h{Hledání nejvìt¹ího párování v~bipartitních grafech} \s{Definice:} Mno¾ina hran $F \subseteq E$ se~nazývá {\I párování}, jestli¾e ¾ádné dvì hrany této mno¾iny nemají spoleèný ani jeden vrchol. Neboli $\forall @@ -253,17 +253,21 @@ tak prohl \figure{toky04.eps}{Hledání maximálního párování v~bipartitním grafu.}{2in} -Existuje toti¾ bijekce mezi párováním a~celoèíselnými toky pøi~zachování -velikosti. Z ka¾dého celoèíselného toku na~vý¹e zmínìném grafu (viz obrázek) lze sestrojit +Existuje toti¾ bijekce mezi párováním a~celoèíselnými toky, je¾ zachovává +velikost. Z ka¾dého celoèíselného toku na~vý¹e zmínìném grafu (viz obrázek) lze sestrojit párování o~stejné velikosti (velikost toku zde odpovídá poètu hran bipartitního -grafu, po~kterých poteèe 1) a~naopak. Dùle¾ité je si uvìdomit, ¾e~definice toku +grafu, po~kterých poteèe 1) a~naopak. Dùle¾ité je uvìdomit si, ¾e~definice toku (omezení toku kapacitou a~Kirchhoffovy zákony) nám zaruèují, ¾e~hrany s~nenulovým tokem (tedy jednièkovým) budou tvoøit párování (nestane se, ¾e~by dvì hrany zaèínaly nebo konèily ve~stejném vrcholu, nebo» by se~nutnì poru¹ila jedna ze~dvou podmínek definice toku). Potom i~maximální tok bude odpovídat maximálnímu párování a~naopak. -V~bipartitním grafu najdeme maximální párování v~èase $\O(n \cdot (m+n))$. Fordùv-Fulkersonùv algoritmus stráví jednou iterací èas $\O(m+n)$ (za~prohledání do~¹íøky) a~pøi~jednotkových kapacitách bude iterací nejvý¹e~$n$, proto¾e ka¾dou se~tok zvìt¹í alespoò o~1 a v¹echny toky jsou omezené øezem kolem zdroje, který má kapacitu nejvý¹e~$n$. Výsledná èasová slo¾tost hledání maximálního párování bude tedy $\O(n \cdot (m+n))$. - +V~bipartitním grafu najdeme maximální párování v~èase $\O(n \cdot (m+n))$. +Fordùv-Fulkersonùv algoritmus stráví jednou iterací èas $\O(m+n)$ +(za~prohledání do~¹íøky) a~pøi~jednotkových kapacitách bude iterací +nejvý¹e~$n$, proto¾e ka¾dou se~tok zvìt¹í alespoò o~1 a v¹echny toky jsou +omezené øezem kolem zdroje, který má kapacitu nejvý¹e~$n$. Výsledná èasová +slo¾itost hledání maximálního párování bude tedy $\O(n \cdot (m+n))$. \bye diff --git a/3-dinic/3-dinic.tex b/3-dinic/3-dinic.tex index d451f01..42acc08 100644 --- a/3-dinic/3-dinic.tex +++ b/3-dinic/3-dinic.tex @@ -1,11 +1,20 @@ \input lecnotes.tex -\prednaska{3}{Dinicùv algoritmus}{(zapsala Markéta Popelová)} - - -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. - -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 Budeme k~tomu potøebovat sí» rezerv. +\prednaska{3}{Dinicùv algoritmus}{} + +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. + +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 Budeme k~tomu +potøebovat sí» rezerv. \s{Definice:} {\I Sí» rezerv} k~toku~$f$ v~síti $S=(V,E,z,s,c)$ je sí» $R=(S,f)=(V,E,z,s,r)$, kde~$r(e)$ je rezerva hrany~$e$ v~toku~$f$. @@ -217,7 +226,4 @@ V \s{Poznámka:} Algoritmus nevy¾aduje racionální kapacity! Dal¹í z~dùvodù, proè maximální tok existuje i~v~síti s~iracionálními kapacitami. - -%k,s,v,na,do,ke,pro,pøi,a,u,i,po, - \bye -- 2.39.2