X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=1-toky%2F1-toky.tex;h=da0df3d69c0b637ffefe16096ba30a17fffacc15;hb=c3ea83834b9874fc87dcf228ad47ec0fe9d74bcf;hp=f3bb242efeb9e88302c5f7e9aa58886f4b6d766c;hpb=eeb2fb289328b332bffe643178e0fcd321e8a256;p=ads2.git

diff --git a/1-toky/1-toky.tex b/1-toky/1-toky.tex
index f3bb242..da0df3d 100644
--- a/1-toky/1-toky.tex
+++ b/1-toky/1-toky.tex
@@ -80,7 +80,7 @@ Uka
 \:Dokud $\exists P$ cesta ze $z$ do $s$ taková, ¾e~$\forall e \in P: r(e) > 0$, opakujeme:
 \::$\varepsilon \leftarrow \min \{r(e) \mid e \in P\}$.
 \::Pro v¹echny hrany $uv \in P$:
-\:::$\delta \leftarrow \min \{f(uv),\varepsilon\}$
+\:::$\delta \leftarrow \min \{f(vu),\varepsilon\}$
 \:::$f(vu) \leftarrow f(vu) - \delta$
 \:::$f(uv) \leftarrow f(uv) + \varepsilon - \delta$
 \:Prohlásíme $f$ za~maximální tok.
@@ -123,15 +123,15 @@ Za
 
 Pøedstavme si, ¾e~máme ji¾ libovolný øez ($A,B$) a~pøesouváme vrchol $v$ z~$A$ do~$B$. Tedy $A' = A \setminus \{v\}$ a $B' = B \cup \{v\}$.
 
-Uvìdomme si, ¾e~v¹echny hrany jednoho typu (napø. vedoucí z~$A$ do~$v$) se~chovají stejnì, tak¾e staèí uva¾ovat hrany pouze 4 typù:
+Uvìdomme si, ¾e~v¹echny hrany jednoho typu (napø. vedoucí z~$A$ do~$v$) se~chovají stejnì, tak¾e staèí uva¾ovat hrany pouze 4 typù (+ ostatní hrany (ty, které pøesun neovlivní) oznaèíme $\varepsilon$):
 \itemize\ibull
 \:$\alpha$ -- hrany vedoucí z~$A$ do~$v$
 \:$\beta$ -- hrany vedoucí z~$v$ do~$B$
 \:$\gamma$ -- hrany vedoucí z~$v$ do~$A$
 \:$\delta$ -- hrany vedoucí z~$B$ do~$v$
-\:$\varepsilon$ -- hrany øezu stejné pøed pøesunem i~po~pøesunu
 \endlist
 
+
 \figure{toky03.eps}{Pøesun vrcholu $v$ z~$A$ do~$B$.}{1in}
 
 Pøed pøesunem ($v \in A$) se~$f(A,B)$ skládá z~$\varepsilon + \beta - \delta$. Po~pøesunu ($v \in B$) se~$f(A',B')$ skládá z~$\varepsilon + \alpha - \gamma$. Rozdíl tìchto hodnot je $\alpha + \delta - \beta - \gamma$.
@@ -151,7 +151,7 @@ Nech
 
 Uvìdomme si, ¾e~($A,B$) je øez, nebo» $z \in A$ (ze~$z$ do~$z$ existuje cesta délky 0) a~$s \notin B$ (kdyby $s \in B$, tak by musela existovat cesta ze~$z$ do~$s$ s~kladnou rezervou, tudí¾ by algoritmus neskonèil, nýbr¾ tuto cestu vzal a~stávající tok vylep¹il). 
 
-Dále víme, ¾e~v¹echny hrany øezu mají nulovou rezervu, neboli $\forall uv \in E(A,B) : r(uv) = 0$ (kdyby mìla hrana $uv$ rezervu nenulovou, tedy kladnou, tak by vrchol $v$ patøil do~$B$). 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(A,B) = c(A,B)$. To znamená, ¾e~jsme na¹li maximální tok a~minimální øez.
+Dále víme, ¾e~v¹echny hrany øezu mají nulovou rezervu, neboli $\forall uv \in 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(A,B) = c(A,B)$. To znamená, ¾e~jsme na¹li maximální tok a~minimální øez.
 \qed
 
 Zformulujme si, co jsme zjistili a~dokázali o~algoritmu pánù Forda a~Fulkersona.
@@ -184,6 +184,9 @@ M
 
 \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 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 (omezení toku kapacitou a~Kirchhofovy 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.
+Existuje toti¾ bijekce mezi párováním a~celoèíselnými toky pøi~zachování velikosti. Z ka¾dé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 (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))$. Forù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))$.
+
 
 \bye