From ec0ea2d5b751e2d6bb288dddf84a962b7043e65f Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 1 Nov 2007 11:31:42 +0100 Subject: [PATCH] Revize druhe prednasky, vesmes opravy preklepu. --- 2-toky/2-toky.tex | 62 +++++++++++++++++++++++------------------------ 1 file changed, 31 insertions(+), 31 deletions(-) diff --git a/2-toky/2-toky.tex b/2-toky/2-toky.tex index 1d6c612..6c0b387 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}{(pøedná¹el T. Valla, zapsali K. Vandas a J. Machálek)} +\prednaska{2}{Toky v sítích}{(pøedná¹el T. Valla, zapsali J. Machálek a K. Vandas)} \h{Motivaèní úlohy:} \itemize\ibull @@ -8,7 +8,7 @@ \:Mìjme orientovaný graf pøedstavující ¾eleznièní sí»; graf má význaèné vrcholy Moskva a Fronta, ka¾dá hrana grafu má kapacitu, kterou mù¾e uvézt. Kolik vojákù je schopna sí» pøevézt z Moskvy a spotøebovat na Frontì? \endlist -\s{Definice:} {\I Sí»} je uspoøádaná ètveøice $(G,z,s,c)$, kde $G$ je orientovaný graf, $z$~a~$s$~jsou jeho vrcholy (zdroj a stok) a $c$ je kapacita sítì, kterou pøedstavuje funkce $c:E(G)\to\bb R_{0}^{+}$. +\s{Definice:} {\I Sí»} je uspoøádaná ètveøice $(G,z,s,c)$, kde $G$ je orientovaný graf, $z$~a~$s$~jsou jeho vrcholy ({\I zdroj} a {\I stok}) a $c$ je kapacita sítì, kterou pøedstavuje funkce $c:\break E(G)\to{\bb R}_{0}^{+}$. \figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{3in} @@ -17,46 +17,46 @@ \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 -- nikde se neztrácejí suroviny: $$\sum_{(x,u)\in E}{f(x,u)}=\sum_{(u,x)\in E}{f(u,x)}\quad \forall u\in V(G), u\ne z, u\ne s.$$ +\: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.$$ \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). \s{Poznámka:} V angliètinì se obvykle zdroj znaèí \uv{$s$} a stok \uv{$t$} (zkratky source a~target). -\figure{tok.eps}{Pøíklad toku. Èísla pøedstavují ohodnocení funkcí toku (v závorkách jsou kapacity hran).}{4in} +\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{Vìta:} Pro ka¾dou sí» existuje maximální tok (bez dùkazu). +\s{Vìta:} Pro ka¾dou sí» existuje maximální tok. -\par\noindent {\sl Idea dùkazu:} Doká¾e se pomocí metod matematické analýzy s tím, ¾e mno¾ina tokù je kompaktní a funkce velikosti toku je spojitá. +\par\noindent {\sl Idea dùkazu:} Doká¾e se pomocí metod matematické analýzy s tím, ¾e mno¾ina tokù je kompaktní a funkce velikosti toku je spojitá (dokonce lineární). -\par\noindent {\sl Intuice:} Øez grafu je mno¾ina hran oddìlující zdroj a stok. +\par\noindent {\sl Intuice:} Øez v grafu je mno¾ina hran oddìlující zdroj a stok. -\s{Definice:} {\I Øez} $R$ v síti $(G,z,s,c)$ je $R\subseteq E(G)$ taková, ¾e neexistuje cesta ze $z$ do $s$ v grafu $(V(G),E(G)\setminus R)$. +\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_{(u,v)\in R}{c(u,v)}$. -\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)}}$$ +\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í: Zaveïme konvenci, ¾e existují-li orientované hrany $(u,v)$, $u\in A$, $v\in B$, znaèíme je $S(A,B)$ (separátor). $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 $(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)}.$ {\narrower \par\noindent {\sl Intuice:} Uvá¾íme-li mno¾inu kapacit v¹ech øezù, je zdola omezená mno¾inou hodnot tokù. -\s{Lemma:} $A\subseteq V(G),z\in A,s\not\in A,f\hbox{ je tok}$. Potom platí, ¾e $$w(f)=f(A,V\setminus~A)-f(V\setminus~A,A)$$ +\s{Lemma:} $A\subseteq V(G),z\in A,s\not\in A,f\hbox{ je tok}$. Potom platí, ¾e $$w(f)=f(A,V\setminus~A)-f(V\setminus~A,A).$$ \proof -Dùkaz provedeme pomocí Kirchhoffova zákonu 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\neq z,u\neq s$$ -$$\sum_{(z,x)\in E}{f(z,x)}-\sum_{(x,z)\in E}{f(x,z)=w(f)}$$ +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)}.$$ \>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_{(u,x)\in E}{f(u,x)}-\sum_{(x,u)\in E}{f(x,u)}\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}. @@ -68,30 +68,30 @@ $$f(A,V\setminus A)-f(V\setminus A,A)=\sum_{u\in A,v\not\in A}{f(u,v)}-\sum_{u\n \s{Dùsledek:} Pokud $f$ je tok, $R$ je øez, pak platí: $w(f)\le c(R)$. \proof -$w(f)=f(A,V\setminus A)-f(V\setminus A,A)\le f(A,V\setminus A)\le c(A,V\setminus A)\le c(R)$ +$$w(f)=f(A,V\setminus A)-f(V\setminus A,A)\le f(A,V\setminus A)\le c(A,V\setminus A)\le c(R).$$ \qed -\s{Definice:} {\I Zs-cesta} je posloupnost navazujících hran, u kterých ignorujeme orientaci. +\s{Definice:} {\I Zlep¹ující cesta} je posloupnost navazujících hran, u kterých ignorujeme orientaci. -\figure{cesta.eps}{Pøíklad zs-cesty.}{3in} +\figure{cesta.eps}{Pøíklad zplep¹ující cesty.}{3in} -\s{Definice:} {\I Zs-cesta} $P$ ze $z$ do $s$ je {\I nasycená}, pokud +\s{Definice:} {\I Zlep¹ující cesta} $P$ ze $z$ do $s$ je {\I nasycená}, pokud $$\exists\ e \in P\left\{{f(e)=c(e)\dots \hbox{orientovaná po smìru}}\atop{f(e)=0\dots \hbox{orientovaná proti smìru}}\right.$$ -\>Jinak je zs-cesta nenasycená. +\>Jinak je zlep¹ující cesta nenasycená. -\s{Definice:} {\I Tok} je {\I nasycený}, pokud $\forall$ zs-cesta $P$ ze $z$ do $s$ je nasycená. +\s{Definice:} {\I Tok} je {\I nasycený}, pokud je ka¾dá zple¹ující cesta $P$ ze $z$ do $s$ nasycená. \s{Vìta:} Tok $f$ je nasycený $\Leftrightarrow$ $f$ je maximální. Navíc pro ka¾dý maximální tok $f$ existuje øez $R$, ¾e $w(f)=c(R)$. \proof -\>\uv{$\Leftarrow$} sporem: Mìjme tok $f$ maximální a nenasycený. Existuje tedy zs-cesta $P$ nenasycená. Tuto cestu $P$ budeme vylep¹ovat. +\>\uv{$\Leftarrow$} sporem: Mìjme tok $f$ maximální a nenasycený. Existuje tedy nenasycená zlep¹ující cesta $P$. Tuto cestu $P$ budeme vylep¹ovat. \>Zvolíme: -$$\varepsilon_1=\min_{e\in P,\hbox{ po smìru}}{\{c(e)-f(e)\}}$$ -$$\varepsilon_2=\min_{e\in P,\hbox{ proti smìru}}{\{f(e)\}}$$ -$$\varepsilon=\min{\{\varepsilon_1,\varepsilon_2\}}>0$$ +$$\varepsilon_1=\min_{e\in P,\hbox{ po smìru}}{\{c(e)-f(e)\}},$$ +$$\varepsilon_2=\min_{e\in P,\hbox{ proti smìru}}{\{f(e)\}},$$ +$$\varepsilon=\min{\{\varepsilon_1,\varepsilon_2\}}>0.$$ \>Poslední ostrá nerovnost vyplývá z definice nenasycené cesty. Nyní vylep¹íme tok $f$ o $\varepsilon$: $f\to f^{'}$: $$f^{'}(e)=\left\{{\displaystyle f(e)+\varepsilon \dots e\in P\hbox{ po smìru}\hfill}\atop{{\displaystyle f(e)-\varepsilon \dots e\in P\hbox{ proti smìru}\hfill}\atop{\displaystyle f(e) \dots e\not\in P\hfill}}\right.$$ \>Nyní je potøeba ovìøit, ¾e $f^{'}$ je skuteènì tok: @@ -104,7 +104,7 @@ $$0\le f^{'}(e)\le c(e)\dots\hbox{plat $$w(f^{'})=w(f)+\varepsilon\Rightarrow w(f^{'})>w(f)\Rightarrow\hbox{SPOR.}$$ \>\uv{$\Rightarrow$}: Uvá¾íme $A\subseteq V(G)$, ¾e $\forall\ v\in{} A$ existuje nenasycená cesta ze $z$ do $v$. $z \in A$, $s \not\in A$. $S(A,V\setminus A)$ je hledaný øez $R$. Podle lemmatu: -$$w(f)=f(A,V\setminus A)-f(V\setminus A,A)=c(A,V\setminus A)=c(R)$$ +$$w(f)=f(A,V\setminus A)-f(V\setminus A,A)=c(A,V\setminus A)=c(R).$$ Víme, ¾e $w(f)\le c(R)$. Staèilo uvá¾it nasycený tok $f$. Pak jsme sestrojili øez $R$ a~výraz pøe¹el v rovnost $c(R)=w(f)$ (a tedy je tok $f$ maximální). \qed @@ -118,16 +118,16 @@ Posledn \s{Algoritmus:} (Fordùv-Fulkersonùv algoritmus hledání maximálního toku) \algo -\:$f(e) := 0\ \forall e \in E$ -\:while $\exists$ zlep¹ující cesta $P$, vylep¹i $P$ jako v dùkazu hlavní vìty -\:f je maximální +\:pøiøad $f$ nulový tok ($f(e) := 0$ pro v¹echny $e \in E$). +\:while $\exists$ zlep¹ující cesta $P$, vylep¹i $f$ podél $P$ jako v dùkazu hlavní vìty. +\:$f$ je maximální. \endalgo \h{Cvièení:} \itemize\ibull \:Je pro pøirozené kapacity F-F algoritmus koneèný? Ano -- v ka¾dém zlep¹ujícím kroku algoritmu se celkový tok zvìt¹í aspoò o 1. Proto¾e máme horní odhad na maximální tok (napø. souèet kapacit v¹ech hran), máme i~horní odhad na dobu bìhu algoritmu. \:Je F-F algoritmus koneèný pro racionální kapacity hran? Ano -- v¹echny kapacity vynásobíme spoleèným jmenovatelem a pøevedeme na pøedchozí pøípad (pro obecné kapacity ov¹em takto definovaný F-F algoritmus nemusí být koneèný). -\:Kolik krokù bude muset algoritmus na následující síti maximálnì udìlat, aby úspì¹nì dobìhl? (2M krokù) +\:Kolik krokù bude muset algoritmus na následující síti maximálnì udìlat, aby úspì¹nì dobìhl? ($2M$ krokù) \endlist \figure{2M.eps}{Pøíklad sítì. Kolik krokù musí maximálnì udìlat F-F algoritmus?}{2in} -- 2.39.2