From a52598548cf0eb5503c399d5c113e31669541d17 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 18 Dec 2007 09:13:05 +0100 Subject: [PATCH] Sjednoceni notace v prednaskach o tocich (patch by Honza Volec). --- 2-toky/2-toky.tex | 18 +++++++++--------- 3-dinic/3-dinic.tex | 12 ++++++------ 2 files changed, 15 insertions(+), 15 deletions(-) diff --git a/2-toky/2-toky.tex b/2-toky/2-toky.tex index 6c0b387..af29d1d 100644 --- a/2-toky/2-toky.tex +++ b/2-toky/2-toky.tex @@ -1,4 +1,4 @@ -\input ../lecnotes.tex +\input lecnotes.tex \prednaska{2}{Toky v sítích}{(pøedná¹el T. Valla, zapsali J. Machálek a K. Vandas)} @@ -17,7 +17,7 @@ \s{Definice:} {\I Tok} je funkce $f:E(G)\to\bb R$ taková, ¾e platí: \numlist{\ndotted} \:Tok ka¾dé hrany je omezen její kapacitou: $0\le f(e)\le c(e)$. -\:Kirchhoffùv zákon -- \uv{sí» tìsní}: $$\sum_{(x,u)\in E}{f(x,u)}=\sum_{(u,x)\in E}{f(u,x)}\quad\hbox{pro ka¾dé }u\in V(G), u\ne z,s.$$ +\:Kirchhoffùv zákon -- \uv{sí» tìsní}: $$\sum_{xu \in E}{f(xu)}=\sum_{ux \in E}{f(ux)}\quad\hbox{pro ka¾dé }u\in V(G) \setminus \{z,s\}.$$ \endlist \s{Poznámka:} Pokud bychom se chtìli v definici toku u bodu 2 vyhnout podmínkám pro $z$ a $s$, mù¾eme zdroj a stok vzájemnì propojit (pak jde o tzv. cirkulaci). @@ -26,7 +26,7 @@ \figure{tok.eps}{Pøíklad toku. Èísla pøedstavují ohodnocení funkcí toku a kapacity.}{4in} -\s{Definice:} {\I Velikost toku} $f$ je: $$w(f)=\sum_{(z,x)\in E}{f(z,x)}-\sum_{(x,z)\in E}{f(x,z)}.$$ +\s{Definice:} {\I Velikost toku} $f$ je: $$w(f)=\sum_{zx \in E}{f(zx)}-\sum_{xz \in E}{f(xz)}.$$ \s{Vìta:} Pro ka¾dou sí» existuje maximální tok. @@ -36,14 +36,14 @@ \s{Definice:} {\I Øez} $R$ v síti $(G,z,s,c)$ je mno¾ina hran $R$ taková, ¾e neexistuje cesta ze $z$ do $s$ v grafu $(V(G),E(G)\setminus R)$. -\s{Definice:} {\I Kapacita øezu} $c(R)=\sum_{(u,v)\in R}{c(u,v)}$. +\s{Definice:} {\I Kapacita øezu} $c(R)=\sum_{uv \in R}{c(uv)}$. \s{Vìta (Hlavní vìta o tocích, Ford-Fulkerson):} Mìjme $S$ sí». Platí: $$\max_{f\hbox{ tok}}{w(f)=\min_{R\hbox{ øez}}{c(R)}}.$$ \proof Dùkaz provedeme pomocí dokázání dvou neostrých nerovností. -\>Pomocné znaèení: Jako $S(A,B)$ ({\I separátor}) znaèíme orientované hrany $(u,v)$, $u\in A$, $v\in B$. $f(A,B)=\sum_{(u,v)\in E,u\in A,v\in B}{f(u,v)}.$ +\>Pomocné znaèení: Jako $S(A,B)$ ({\I separátor}) znaèíme orientované hrany $uv$, $u\in A$, $v\in B$. $f(A,B)=\sum_{uv \in E,u\in A,v\in B}{f(uv)}.$ {\narrower \par\noindent {\sl Intuice:} Uvá¾íme-li mno¾inu kapacit v¹ech øezù, je zdola omezená mno¾inou hodnot tokù. @@ -52,16 +52,16 @@ D \proof Dùkaz provedeme pomocí Kirchhoffova zákona a definice velikosti toku: -$$\sum_{(u,x)\in E}{f(u,x)}-\sum_{(x,u)\in E}{f(x,u)}=0\quad\forall u\in A,u\ne z,s.$$ -$$\sum_{(z,x)\in E}{f(z,x)}-\sum_{(x,z)\in E}{f(x,z)=w(f)}.$$ +$$\sum_{ux \in E}{f(ux)}-\sum_{xu \in E}{f(xu)}=0\quad\forall u\in A \setminus \{z,s\}.$$ +$$\sum_{zx \in E}{f(zx)}-\sum_{xz \in E}{f(xz)=w(f)}.$$ \>Rovnice seèteme: -$$\sum_{u\in A}{\left(\sum_{(u,x)\in E}{f(u,x)}-\sum_{(x,u)\in E}{f(x,u)}\right)}=w(f).$$ +$$\sum_{u\in A}{\left(\sum_{ux \in E}{f(ux)}-\sum_{xu \in E}{f(xu)}\right)}=w(f).$$ \s{Poznámka:} Tato rovnice neznamená nic jiného, ne¾ ¾e se hrany vedoucí z~$A$ do $A$ jednou pøiètou a jednou odeètou. Projeví se pouze hrany, které vedou dovnitø a ven z $V\setminus A$, tak¾e toky vnitøních hran $A$ se \uv{po¾erou}. \>Z toho plyne: -$$f(A,V\setminus A)-f(V\setminus A,A)=\sum_{u\in A,v\not\in A}{f(u,v)}-\sum_{u\not\in A,v\in A}{f(u,v)}=w(f).$$ +$$f(A,V\setminus A)-f(V\setminus A,A)=\sum_{u\in A,v\not\in A}{f(uv)}-\sum_{u\not\in A,v\in A}{f(uv)}=w(f).$$ \qed diff --git a/3-dinic/3-dinic.tex b/3-dinic/3-dinic.tex index a7a10d5..74b589c 100644 --- a/3-dinic/3-dinic.tex +++ b/3-dinic/3-dinic.tex @@ -1,4 +1,4 @@ -\input ../lecnotes.tex +\input lecnotes.tex \prednaska{3}{Dinicùv algoritmus}{(zapsali Jakub Melka, Petr Musil)\foot{\rm s~díky Bernardovi Lidickému za obrázky}} @@ -71,7 +71,7 @@ nebo \s{Postup tvorby proèi¹tìné sítì podrobnìji:} prohledáním do~¹íøky vytvoøíme vrstvy $C_i$, zahodíme ty za~spotøebièem, ponecháme pouze hrany mezi $C_i$ a $C_{i+1}$. Je¹tì musíme odstranit slepé ulièky -- cesty, které konèí v~$C_m : m < l$, proto¾e ty urèitì nejsou souèástí nejkrat¹í $z\rightarrow s$ cesty. -Proèi¹tìní zvládneme v~lineárním èase $\O(n+m)$, v~pøípadì souvislého grafu pouze $\O(m)$. +Proèi¹tìní zvládneme v~lineárním èase $\O(N+M)$, v~pøípadì souvislého grafu pouze $\O(M)$. \figure{dinic-neprocistenasit.eps}{Pøíklad neproèi¹tìné sítì}{0.5\hsize} @@ -80,7 +80,7 @@ Na obr \s{Definice:} {\I Fází} algoritmu oznaèíme jeden bìh cyklu -- kroky 3 a¾ 9. -\>Provedeme podrobnou analýzu algoritmu z~hlediska slo¾itosti a uvidíme, ¾e má slo¾itost $\O(n^2m)$. Nejprve analyzujeme hledání +\>Provedeme podrobnou analýzu algoritmu z~hlediska slo¾itosti a uvidíme, ¾e má slo¾itost $\O(N^2M)$. Nejprve analyzujeme hledání blokujícího toku, pak se podíváme, kolik fází maximálnì mù¾e Dinicùv algoritmus mít. @@ -93,9 +93,9 @@ blokuj \::Doèistíme sí» tím, ¾e odstraníme slepé ulièky, které mohly vzniknout smazáním hrany $e$. \endalgo -Pøi ka¾dém prùchodu se sma¾e v¾dy alespoò 1 hrana, tedy maximálnì $m$-krát provádíme $\O(n)$ -- právì tolik trvá nalezení cesty $P$, proto¾e délka cesty bude krat¹í nebo rovna $n$. Èi¹tìní pak maximálnì sma¾e celý graf, jedno mazání nás stojí konstantní èas, tedy celková slo¾itost tohoto algoritmu bude $\O(m n)$. +Pøi ka¾dém prùchodu se sma¾e v¾dy alespoò 1 hrana, tedy maximálnì $M$-krát provádíme $\O(N)$ -- právì tolik trvá nalezení cesty $P$, proto¾e délka cesty bude krat¹í nebo rovna $N$. Èi¹tìní pak maximálnì sma¾e celý graf, jedno mazání nás stojí konstantní èas, tedy celková slo¾itost tohoto algoritmu bude $\O(MN)$. -Doká¾eme si, ¾e poèet fází je men¹í nebo roven $n$. Algoritmus se ukonèí, pokud $l>n$, proto¾e pak u¾ neexistuje nejkrat¹í $z\rightarrow s$ cesta, pro¹li jsme v¹echny vrcholy. +Doká¾eme si, ¾e poèet fází je men¹í nebo roven $N$. Algoritmus se ukonèí, pokud $l>N$, proto¾e pak u¾ neexistuje nejkrat¹í $z\rightarrow s$ cesta, pro¹li jsme v¹echny vrcholy. \s{Lemma:} Pøi ka¾dé fázi $l$ vzroste alespoò o~jedna. @@ -110,7 +110,7 @@ Uva \qeditem \endlist -\s{Vìta:} Dinicùv algoritmus najde maximální tok v~èase $\O(m n^2)$. +\s{Vìta:} Dinicùv algoritmus najde maximální tok v~èase $\O(MN^2)$. \proof Slo¾itost plyne pøímo z~pøedchozího lemmatu a slo¾itosti algoritmu hledání blokujícího toku. -- 2.39.2