2-toky/2-toky.tex

   1 \input ../lecnotes.tex
   2
   3 \def\og{$\buildrel \rightarrow \over G$}
   4 \def\ogm{\buildrel \rightarrow \over G}
   5
   6 \prednaska{2}{Toky v sítích}{(pøedná¹el T. Valla, zapsali K. Vandas a J. Machálek)}
   7
   8 \h{Motivaèní úlohy:}
   9 \itemize\ibull
  10 \:Mìjme orientovaný graf se speciálními vrcholy ®elivka a Kanál pøedstavující pra¾ské vodovody. V tomto grafu budou vrcholy vodovodními stanicemi a hrany trubkami mezi nimi. Kolik vody proteèe ze ®elivky do Kanálu?
  11 \: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ì?
  12 \endlist
  13
  14 \s{Definice:} {\I Sí»} je uspoøádaná ètveøice $(\ogm,z,s,c)$, kde \og{} je orientovaný graf, z~a~s~jsou jeho vrcholy (z(droj) a s(tok)) a c je kapacita sítì, kterou pøedstavuje funkce $c:E(\ogm)\to R_{0}^{+}$.
  15
  16 \par\noindent {\sl Intuice:} Toky v sítích pøedstavují rozvr¾ení, jakým suroviny sítí poteèou...
  17
  18 \figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{3in}
  19
  20 \s{Definice:} {\I Tok} je funkce $E(\ogm)\to R$ taková, ¾e
  21 \numlist{\ndotted}
  22 \:Tok ka¾dé hrany je omezen její kapacitou: $0\le f(e)\le c(e)$
  23 \:\uv{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(\ogm), u\ne z, u\ne s$$
  24 \endlist
  25
  26 \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).
  27
  28 \s{Poznámka:} V angliètinì se obvykle zdroj znaèí \uv{s} a stok \uv{t} (zkratky source a sink, ov¹em dvì stejná písmena by byla ponìkud nepraktická\dots)
  29
  30 \figure{tok.eps}{Pøíklad toku. Èísla pøedstavují ohodnocení funkcí toku (v závorkách jsou kapacity hran).}{4in}
  31
  32 \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)}$$
  33
  34 \s{Vìta:} Pro ka¾dou sí» existuje maximální tok (bez dùkazu).
  35
  36 \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 tokù je spojitá\dots
  37
  38 \>Intuice. Øez grafu je mno¾ina hran oddìlující z(droj) a s(tok).
  39
  40 \s{Definice:} {\I Øez} R v síti $(\ogm,z,s,c)$ je $R\subseteq E(\ogm)$ taková, ¾e $\not\kern -.5ex\exists$ cesta ze z do s v grafu $(V(\ogm),E(\ogm)\setminus R)$.
  41
  42 \s{Definice:} {\I Kapacita øezu} $c(R)=\sum_{(u,v\in R)}{c(u,v)}.$
  43
  44 \s{Vìta (Hlavní vìta o tocích, Ford-Fulkerson):} Mìjme S sí». $$\max_{f\hbox{ tok}}{w(f)=\min_{R\hbox{ øez}}{c(R)}}$$
  45
  46 \par\noindent {\sl Intuice:} Uvá¾íme-li mno¾inu kapacit v¹ech øezù, je zdola omezená mno¾inou hodnot tokù.
  47
  48 \par\noindent {\sl Idea dùkazu:} Dùkaz provedeme pomocí dokázání dvou neostrých nerovností.
  49
  50 \proof
  51
  52 \>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)}.$
  53
  54 {\narrower
  55 \s{Lemma:} $A\subseteq V(\ogm),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)$$
  56
  57 \proof
  58 Dùkaz provedeme pomocí \uv{Kirchhoffova zákonu} a definice velikosti toku:
  59 $$\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$$
  60 $$\sum_{(z,x)\in E}{f(z,x)}-\sum_{(x,z)\in E}{f(x,z)=w(f)}$$
  61
  62 \>Rovnice seèteme:
  63 $$\sum_{u\in A}{\left(\sum_{(u,x)\in E}{f(u,x)}-\sum_{(x,u)\in E}{f(x,u)}\right)}=w(f)$$
  64
  65 \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 vedoucí dovnitø a ven z $V\setminus A$, tak¾e toky vnitøních hran A se \uv{po¾erou}.
  66
  67 \>Z toho plyne:
  68 $$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)$$
  69
  70 \qed
  71
  72 \s{Dùsledek:} Pokud f je tok, R je øez, pak platí:  $w(f)\le c(R)$.
  73
  74 \proof
  75 $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)$
  76
  77 \qed
  78 }
  79
  80 \s{Redefinice:} {\I Cesta} je odteï posloupnost navazujících hran, u kterých ignorujeme orientaci. Tyto cesty se obvykle nazývají \uv{zs-cesty}.
  81
  82
  83 \figure{cesta.eps}{Pøíklad zs-cesty.}{3in}
  84
  85 \s{Definice:} {\I Cesta} P ze z do s je {\I nasycená}, pokud
  86 $$\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.$$
  87 \>Jinak je cesta nenasycená.
  88
  89 \s{Definice:} {\I Tok} je {\I nasycený}, pokud $\forall$ cesta P je nasycená.
  90
  91 \s{Vìta:} Tok f je nasycený $\Leftrightarrow$ f je maximální. Navíc pro $\forall$ maximální tok f $\exists$ øez R, ¾e $w(f)=c(R).$
  92
  93 \proof
  94
  95 \>\uv{$\Leftarrow$} sporem: Mìjme tok f maximální a nenasycený $\Rightarrow \exists$ P nenasycená. Tuto cestu P budeme \uv{vylep¹ovat}.
  96 \>Zvolíme:
  97 $$\varepsilon_1=\min_{e\in P,\hbox{ po smìru}}{\{c(e)-f(e)\}}$$
  98 $$\varepsilon_2=\min_{e\in P,\hbox{ proti smìru}}{\{f(e)\}}$$
  99 $$\varepsilon=\min{\{\varepsilon_1,\varepsilon_2\}}>0$$
 100 \>Poslední ostrá nerovnost vyplývá z definice nenasycené cesty. Nyní vylep¹íme tok f o $\varepsilon$: $f\to f^{'}$:
 101 $$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.$$
 102 \>Nyní je potøeba ovìøit, ¾e $f^{'}$ je skuteènì tok:
 103 $$0\le f^{'}(e)\le c(e)\dots\hbox{platí stále díky volbì }\varepsilon $$
 104
 105 \>Platnost \uv{Kirchhoffova zákonu} ovìøíme rozborem pøípadù:
 106 \figure{kirch.eps}{Rozbor pøípadù.}{4in}
 107
 108 \>$f^{'}$ je tedy tok, ov¹em potom platí:
 109 $$w(f^{'})=w(f)+\varepsilon\Rightarrow w(f^{'})>w(f)\Rightarrow\hbox{SPOR}$$
 110
 111 \>\uv{$\Rightarrow$}: Uvá¾íme $A\subseteq V(\ogm)$, ¾e $\forall\ v\in{} A\ \exists$ nenasycená cesta ze z do v. $z \in A$, $s \not\in A$. $S(A,V\setminus A)$ je hledaný øez R. Podle lemmatu:
 112 $$w(f)=f(A,V\setminus A)-f(V\setminus A,A)=c(A,V\setminus A)=c(R)$$
 113 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í).
 114
 115 \qed
 116
 117 \figure{nenasyc.eps}{Rozdìlení V(\og) na mno¾inu A a V$\setminus$A v dùkazu hlavní vìty o tocích.}{2.5in}
 118
 119 \s{Algoritmus:} (Ford-Fulkerson algoritmus hledání maximálního toku)
 120
 121 \algo
 122 \:$f(e) := 0\ \forall e \in E$
 123 \:while $\exists$ zlep¹ující cesta P, vylep¹i P jako v dùkazu hlavní vìty
 124 \:f je maximální
 125 \endalgo
 126
 127 \h{Cvièení:}
 128 \itemize\ibull
 129 \: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.
 130 \: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ý).
 131 \:Kolik krokù bude muset algoritmus na následující síti maximálnì udìlat, aby úspì¹nì dobìhl? (2M krokù)
 132 \endlist
 133
 134 \figure{2M.eps}{Pøíklad sítì. Kolik krokù musí maximálnì udìlat F.F. algoritmus?}{2in}
 135
 136 \bye