X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=2-toky%2F2-toky.tex;h=31a572119f3298d40e1db917514502a9a967ae2b;hb=9aadd3ff2034c83aa60b7ce1a9c33e2ea9f2f023;hp=0c442bde785f8de86e195ef2061fdbb7a1edb64f;hpb=81383c3b1ab213e35aaaf31e18368dde88b75656;p=ads2.git diff --git a/2-toky/2-toky.tex b/2-toky/2-toky.tex index 0c442bd..31a5721 100644 --- a/2-toky/2-toky.tex +++ b/2-toky/2-toky.tex @@ -1,136 +1,193 @@ -\input ../lecnotes.tex +\input lecnotes.tex -\def\og{$\buildrel \rightarrow \over G$} -\def\ogm{\buildrel \rightarrow \over G} +\prednaska{2}{Toky v sítích}{(pøedná¹el T. Valla, zapsali J. Machálek a K. Vandas)} -\prednaska{2}{Toky v sítích}{(pøedná¹el T. Valla, zapsali K. Vandas a J. Machálek)} - -\h{Motivaèní úlohy:} +\s{Motivaèní úlohy:} \itemize\ibull \: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? -\: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ì? +\: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 $(\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}^{+}$. - -\par\noindent {\sl Intuice:} Toky v sítích pøedstavují rozvr¾ení, jakým suroviny sítí poteèou... +\s{Definice:} {\I Sí»} je uspoøádaná ètveøice $(G,z,s,c)$, kde $G$ je +orientovaný graf, $z$~a~$s$~jsou nìjaké dva jeho vrcholy ({\I zdroj} a {\I stok}) a $c$ je +{\I kapacita hran,} kterou pøedstavuje funkce $c:E(G)\to{\bb +R}_{0}^{+}$. \figure{sit.eps}{Pøíklad sítì. Èísla pøedstavují kapacity jednotlivých hran.}{3in} -\s{Definice:} {\I Tok} je funkce $E(\ogm)\to R$ taková, ¾e +\par\noindent {\sl Intuice:} Toky v sítích pøedstavují rozvr¾ení, jakým suroviny sítí poteèou. + +\s{Definice:} {\I Tok} je funkce $f:E(G)\to{\bb R}_{0}^{+}$ taková, ¾e platí: \numlist{\ndotted} -\:Tok ka¾dé hrany je omezen její kapacitou: $0\le f(e)\le c(e)$ -\:\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$$ +\:Tok po~ka¾dé hranì je omezen její kapacitou: $0\le f(e)\le c(e)$. +\: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). +\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 sink, ov¹em dvì stejná písmena by byla ponìkud nepraktická\dots) +\s{Poznámka:} V angliètinì se obvykle zdroj znaèí \uv{$s$} a stok \uv{$t$} (jako 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í toky po~hranách, v~závorkách jsou 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: $$\vert f\vert:=\sum_{zx \in E}{f(zx)}-\sum_{xz \in E}{f(xz)}.$$ -\s{Vìta:} Pro ka¾dou sí» existuje maximální tok (bez dùkazu). +\>Budeme tedy chtít najít v~zadané síti tok, jeho¾ velikost je maximální. Musí v¾dycky existovat? -\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 +\s{Vìta:} Pro ka¾dou sí» existuje maximální tok. -\>Intuice. Øez grafu je mno¾ina hran oddìlující z(droj) a s(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á (dokonce lineární). -\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)$. +Dobrá, maximální tok v¾dy existuje. Ale kdy¾ nám ho nìkdo uká¾e, umíme poznat, +¾e je skuteènì maximální? K~tomu se budou hodit øezy: -\s{Definice:} {\I Kapacita øezu} $c(R)=\sum_{(u,v\in R)}{c(u,v)}.$ +\par\noindent {\sl Intuice:} Øez v~grafu je mno¾ina hran oddìlující zdroj a stok. -\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)}}$$ +\s{Definice:} {\I Øez} $R$ v síti $(G,z,s,c)$ je mno¾ina hran $R$ taková, ¾e +neexistuje orientovaná cesta ze $z$~do $s$~v~grafu $(V(G),E(G)\setminus R)$. -\par\noindent {\sl Intuice:} Uvá¾íme-li mno¾inu kapacit v¹ech øezù, je zdola omezená mno¾inou hodnot tokù. +\s{Definice:} {\I Kapacita øezu} $c(R)=\sum_{uv \in R}{c(uv)}$. -\par\noindent {\sl Idea dùkazu:} Dùkaz provedeme pomocí dokázání dvou neostrých nerovností. +Nìkdy je lep¹í se na~øezy dívat takto: -\proof +\s{Definice:} Pro dvì disjunktní mno¾iny vrcholù $A,B$, kde $z\in A$ a $s\in B$ zavedeme +{\I separátor} $S(A,B)$, co¾ bude mno¾ina hran vedoucích z~$A$ do~$B$. Pokud je $g$ funkce +definovaná na~hranách (tøeba tok nebo kapacita), definujeme $g(A,B):=\sum_{uv \in E,u\in A,v\in B}{g(uv)}.$ -\>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)}.$ +\s{Pozorování:} Ka¾dý separátor je øezem (libovolná orientovaná cesta ze~$z$ do~$s$ musí +nìkdy opustit mno¾inu~$A$, a to jde pouze po~hranì patøící do~separátoru). Opaènì to sice +platit nemusí, ale platí, ¾e ke~ka¾dému øezu existuje separátor takový, ¾e souèet kapacit +jeho hran je nejvý¹e kapacita daného øezu. Staèí si zvolit mno¾inu $A$ jako vrcholy dosa¾itelné +ze~zdroje po~hranách nele¾icích v~øezu a do~$B$ dát v¹echny ostatní vrcholy. Separátor +$S(A,B)$ pak bude tvoøen výhradnì hranami øezu (ne~nutnì v¹emi) a sám bude øezem. -{\narrower -\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)$$ +\s{Definice:} Pro libovolnou mno¾inu vrcholù $A$ zavedeme její {\I doplnìk} $\overline A:=V(G)\setminus A$. -\proof -Dùkaz provedeme pomocí \uv{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)}$$ +Nyní si v¹imneme, ¾e velikost toku mù¾eme mìøit pøes libovolný separátor: je to mno¾ství +tekutiny, které teèe pøes separátor z~$A$ do~$B$ minus to, které se vrací zpátky +(zatím jsme velikost mìøili u~zdroje, vlastnì na~triviálním separátoru $A=\{z\}$, $B=\overline A).$ -\>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)$$ - -\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}. - -\>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)$$ +\s{Lemma:} Nech» $A\subseteq V(G),z\in A,s\not\in A$ a $f$ je libovolný tok. Potom platí, +¾e: $$\vert f\vert=f(A,\overline A)-f(\overline A,A).$$ +\proof +provedeme pomocí Kirchhoffova zákona a definice velikosti toku: +$$\hbox{Pro ka¾dý vrchol~$u\ne z,s$ platí:~~} \sum_{ux \in E}{f(ux)}-\sum_{xu \in E}{f(xu)}=0,$$ +$$\hbox{pro zdroj pak:~~} \sum_{zx \in E}{f(zx)}-\sum_{xz \in E}{f(xz)=\vert f\vert}.$$ +Rovnice seèteme: +$$\sum_{u\in A}{\left(\sum_{ux \in E}{f(ux)}-\sum_{xu \in E}{f(xu)}\right)}=\vert f\vert.$$ +V¹imneme si, ¾e hrany, jeji¾ oba koncové vrcholy le¾í v~mno¾inì~$A$, pøispívají +k~této sumì jednou kladnì a jednou zápornì, hrany, její¾ ani jeden vrchol nele¾í v~$A$, +nepøispívají vùbec, a koneènì hrany vedoucí z~$A$ do~$B$, resp. opaènì pøispìjí jen jednou +(kladnì, resp. zápornì). Tedy: +$$f(A,\overline A)-f(\overline A,A)=\sum_{u\in A,v\not\in A}{f(uv)}-\sum_{u\not\in A,v\in A}{f(uv)}=\vert f \vert.$$ \qed -\s{Dùsledek:} Pokud f je tok, R je øez, pak platí: $w(f)\le c(R)$. +\s{Dùsledek:} Pokud $f$ je tok, $R$ je øez, pak platí: $\vert f \vert\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)$ - +Doká¾eme pro separátory (u¾ víme, ¾e ke~ka¾dému øezu najdeme stejnì velký nebo men¹í separátor): +$$\vert f \vert=f(A,\overline A)-f(\overline A,A)\le f(A,\overline A)\le c(A,\overline A)\le c(R).$$ \qed -} -\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}. +Nyní víme, ¾e velikost ka¾dého toku je shora omezena velikostí ka¾dého øezu. Kdybychom tedy +k~na¹emu toku umìli najít stejnì velký øez, hned víme, ¾e tok je maximální a øez minimální. +Pøekvapivì platí, ¾e se to povede v¾dy. K~tomu se nám budou hodit zlep¹ující cesty: +\s{Definice:} {\I Zlep¹ující cesta} budeme øíkat takové cestì mezi danými dvìma vrcholy, +která pou¾ívá buïto hrany sítì (hrany orientované po~smìru cesty) nebo hrany k~nim opaèné (v~síti jsou +tedy proti smìru cesty). -\figure{cesta.eps}{Pøíklad zs-cesty.}{3in} +\figure{cesta.eps}{Pøíklad zlep¹ující cesty.}{3in} -\s{Definice:} {\I 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 cesta nenasycená. +\s{Definice:} {\I Zlep¹ující cesta} $P$ ze $z$ do $s$ je {\I nasycená}, pokud: +$$\exists e \in P:\cases{ + f(e)=c(e) & \hbox{je-li $e$ orientovaná po smìru} \cr + f(e)=0 & \hbox{je-li $e$ orientovaná proti smìru} \cr +}$$ +\>Jinak je zlep¹ující cesta nenasycená. -\s{Definice:} {\I Tok} je {\I nasycený}, pokud $\forall$ cesta P je nasycená. +\s{Definice:} {\I Tok je nasycený,} pokud je ka¾dá zlep¹ující cesta $P$ ze $z$ do $s$ nasycená. -\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).$ +\s{Vìta:} Tok $f$ je nasycený $\Leftrightarrow$ $f$ je maximální. Navíc pro ka¾dý maximální tok $f$ existuje øez $R$ takový, ¾e $\vert f \vert=c(R)$. \proof -\>\uv{$\Leftarrow$} sporem: Mìjme tok f maximální a nenasycený $\Rightarrow \exists$ P nenasycená. Tuto cestu P budeme \uv{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$$ -\>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.$$ +\>\uv{$\Leftarrow$} doká¾eme nepøímo -- uká¾eme, ¾e pokud nìjaký tok není nasycený, tak ho +je¹tì lze zlep¹it, proèe¾ nemù¾e být maximální. Mìjme nìjaký nenasycený tok~$f$. Existuje tedy +nenasycená zlep¹ující cesta $P$. Podél této cesty budeme tok vylep¹ovat. +Zvolíme: +$$ +\eqalign{ +\varepsilon_1&:=\min_{e\in P\hbox{\sevenrm~po smìru}}{\{c(e)-f(e)\}}, \cr +\varepsilon_2&:=\min_{e\in P\hbox{\sevenrm~proti smìru}}{\{f(e)\}}, \cr +\varepsilon&:=\min{\{\varepsilon_1,\varepsilon_2\}}. \cr +} +$$ +Jeliko¾ cesta byla nenasycená, musí být $\varepsilon>0$. Nyní z~toku~$f$ vytvoøíme +tok~$f'$ takto: +$$f'(e):=\cases{ + f(e)+\varepsilon & \hbox{je-li $e$ po smìru cesty,} \cr + f(e)-\varepsilon & \hbox{je-li $e$ proti smìru,} \cr + f(e) & \hbox{pokud $e\not\in P$.} \cr +} +$$ \>Nyní je potøeba ovìøit, ¾e $f^{'}$ je skuteènì tok: -$$0\le f^{'}(e)\le c(e)\dots\hbox{platí stále díky volbì }\varepsilon $$ +$$0\le f^{'}(e)\le c(e)\dots\hbox{platí stále díky volbì }\varepsilon.$$ -\>Platnost \uv{Kirchhoffova zákonu} ovìøíme rozborem pøípadù: +\>Platnost Kirchhoffova zákona ovìøíme rozborem pøípadù: \figure{kirch.eps}{Rozbor pøípadù.}{4in} -\>$f^{'}$ je tedy tok, ov¹em potom platí: -$$w(f^{'})=w(f)+\varepsilon\Rightarrow w(f^{'})>w(f)\Rightarrow\hbox{SPOR}$$ +\>Funkce $f'$ je tedy tok. Jeho velikost se ov¹em oproti~$f$ zvý¹ila o~$\varepsilon$, tak¾e~$f$ nebyl maximální. + +\>\uv{$\Rightarrow$}: Uvá¾íme mno¾inu vrcholù $A\subseteq V(G)$ definovanou tak, ¾e $v\in A$ +právì tehdy, kdy¾ existuje nenasycená cesta ze $z$ do $v$. V¹imnìme si, ¾e $z \in A$ a $s \not\in A$. +Potom $S(A,\overline A)$ je øez, který je stejnì velký jako tok~$f$. Jak u¾ víme, pokud k~toku +najdeme stejnì velký øez, je tok maximální. +\qed -\>\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: -$$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í). +\figure{nenasyc.eps}{Rozdìlení $V(G)$ na mno¾inu $A$ a $\overline A$ v dùkazu hlavní vìty o tocích.}{2.5in} +\>To, co jsme o~tocích zjistili, mù¾eme shrnout do~následující \uv{minimaxové} vìty: + +\s{Vìta (Hlavní vìta o tocích, Ford-Fulkerson):} Pro ka¾dou sí» platí: $$\max_{f\hbox{\sevenrm~tok}}{\vert f \vert=\min_{R\hbox{\sevenrm~øez}}{c(R)}}.$$ + +\proof +Nerovnost \uv{$\le$} je ná¹ Dùsledek lemmatu o~tocích a øezech, rovnost +platí proto, ¾e k~maximálnímu toku existuje podle pøedcházející vìty stejnì +velký øez. \qed -\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} +\>Zlep¹ování tokù pomocí zlep¹ujících cest není jen pìkný dùkazový prostøedek, +dá se pomocí nìj také formulovat elegantní algoritmus na~hledání maximálního toku: -\s{Algoritmus:} (Ford-Fulkerson algoritmus hledání maximálního toku) +\s{Algoritmus (hledání maximálního toku v síti, Ford-Fulkerson)} \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í +\:$f \leftarrow \hbox{libovolný tok}$, tøeba v¹ude nulový ($\forall e \in E: f(e) \leftarrow 0 $). +\:Dokud $\exists$ zlep¹ující cesta $P$: vylep¹íme $f$ podél $P$ jako v~dùkazu vìty. +\:Prohlásíme $f$ za~maximální tok. \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ù) +\: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 jedna. Proto¾e máme horní odhad +na velikost maximálního toku (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. +Algoritmus se pøitom chová stejnì jako s~pùvodními kapacitami. +\:A~pro reálné kapacity? Obecnì ne -- zkuste najít sí» s~nìkterými kapacitami +iracionální, kde se algoritmus pøi ne¹ikovné volbì zlep¹ujících cest nikdy +nezastaví a dokonce ani nekonverguje k~maximálnímu toku. +\:Kolik krokù bude muset algoritmus na následující síti maximálnì udìlat, aby +úspì¹nì dobìhl? ($2M$ krokù) +\figure{2M.eps}{Pøíklad sítì. Kolik krokù musí maximálnì udìlat F-F algoritmus?}{2in} +\:Pokud bychom v¾dy hledali {\I nejkrat¹í} zlep¹ující cestu, co¾ je snad +nejpøímoèaøej¹í mo¾ná implementace (prohledávání do ¹íøky), algoritmus by +se zastavil po~$\O(M^2N)$ krocích (tomu se øíká Edmondsùv-Karpùv algoritmus). +To si nebudeme dokazovat a místo toho si na~pøí¹tí pøedná¹ce rovnou odvodíme +efektivnìj¹í Dinicùv algoritmus. \endlist -\figure{2M.eps}{Pøíklad sítì. Kolik krokù musí maximálnì udìlat F.F. algoritmus?}{2in} - \bye