Kostry: Opraven popisek obrazku s prikladem swapovani

[ga.git] / 5-mst / 5-mst.tex

diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex
index 327c3255b34dd2d47972c2fcb962e9c806c86b26..fc83c80cf974d53d5cb8176ce93c52e38ec407d2 100644 (file)
--- a/5-mst/5-mst.tex
+++ b/5-mst/5-mst.tex
@@ -50,21 +50,21 @@ Pokud $e^\prime \not\in T$ a $e\in T[e^\prime]$, je $\<swap>(T,e,e^\prime)$ op
 Staèí si uvìdomit, ¾e pøidáním $e^\prime$ do~$T$ vznikne kru¾nice (konkrétnì $T[e^\prime] + e^\prime$)
 a vynecháním libovolné hrany z~této kru¾nice získáme opìt kostru.
 
-\figure{mst2.eps}{Kostra $T$, cesta $T[e]$ a výsledek operace $\<swap>(T,e,e')$}{\epsfxsize}
+\figure{mst2.eps}{Kostra $T$, cesta $T[e]$ a výsledek operace $\<swap>(T,e',e)$}{\epsfxsize}
+
+\figure{mst1.eps}{Jeden krok dùkazu swapovacího lemmatu}{\epsfxsize}
 
 \s{Lemma o~swapování:}
 Máme-li libovolné kostry $T$ a $T'$, pak lze z~$T$ dostat $T'$ koneèným poètem operací \<swap>.
 
 \proof
 Pokud $T \ne T'$, musí existovat hrana $e' \in T'\setminus T$, proto¾e $\vert T \vert = \vert T' \vert$.
-Kru¾nice $T[e']+e'$ nemù¾e být celá obsa¾ena v~$T$, tak¾e existuje hrana
+Kru¾nice $T[e']+e'$ nemù¾e být celá obsa¾ena v~$T'$, tak¾e existuje hrana
 $e\in T[e']\setminus T'$ a $\check{T} := \<swap>(T,e,e')$ je kostra,
 pro kterou $\vert \check{T} \symdiff T' \vert = \vert T \symdiff T' \vert -2$.
 Po~koneèném poètu tìchto krokù tedy musíme dojít k~$T'$.
 \qed
 
-\figure{mst1.eps}{Jeden krok dùkazu swapovacího lemmatu}{\epsfxsize}
-
 \s{Monotónní lemma o~swapování:}
 Je-li $T$ kostra, k~ní¾ neexistují ¾ádné lehké hrany, a~$T'$ libovolná kostra,
 pak lze od~$T$ k~$T'$ pøejít posloupností swapù, pøi které váha kostry neklesá.
@@ -79,7 +79,7 @@ Aby mohla indukce pokra
 lehké hrany v~$T'\setminus \check{T}$. K~tomu nám pomù¾e zvolit si ze~v¹ech mo¾ných hran~$e'$ tu s~nejmen¹í vahou.
 Uva¾me nyní hranu~$f\in T'\setminus \check{T}$.
 Cesta $\check{T}[f]$ pokrytá touto hranou v~nové kostøe je buïto pùvodní $T[f]$ (to pokud $e\not\in T[f]$)
-nebo $T[f] \symdiff C$, kde $C$ je kru¾nice $T[e']+e$. První pøípad je triviální,
+nebo $T[f] \symdiff C$, kde $C$ je kru¾nice $T[e']+e'$. První pøípad je triviální,
 ve~druhém si staèí uvìdomit, ¾e $w(f)\ge w(e')$ a ostatní hrany na~$C$ jsou lehèí
 ne¾~$e'$.
 \qed
@@ -214,7 +214,7 @@ jedn
 je maximální na~nìjakém cyklu tvoøeném touto hranou a nìjakými døíve pøidanými.
 
 Potøebujeme èas $\O(m \log n)$ na~setøídìní hran a dále datovou strukturu pro udr¾ování komponent souvislosti
-(Union-Find Problem), se~kterou provedeme $m$ operací \<Find> a $n$ operací \<Union>. Nejlep¹í známá implementace
+(Union-Find Problem), se~kterou provedeme $m$~operací \<Find> a $n$ operací \<Union>. Nejlep¹í známá implementace
 této struktury dává slo¾itost obou operací $\O(\alpha(n))$ amortizovanì, tak¾e celkovì hladový algoritmus
 dobìhne v~èase $\O(m \log n + m \alpha(n))$.
 
@@ -224,7 +224,7 @@ Op
 a v¹echny tyto nalezené hrany naráz pøidáme (aplikujeme nìkolik modrých pravidel najednou). Pokud jsou v¹echny váhy rùzné, cyklus
 tím nevznikne.
 
-Poèet stromeèku klesá exponenciálnì $\Rightarrow$ fází je celkem $\log n$. Pokud ka¾dou fázi
+Poèet stromeèkù klesá exponenciálnì $\Rightarrow$ fází je celkem $\log n$. Pokud ka¾dou fázi
 implementujeme lineárním prùchodem celého grafu, dostaneme slo¾itost $\O(m\log n)$.
 Mimo to lze ka¾dou fázi výteènì paralelizovat.
 
@@ -236,7 +236,8 @@ hrany vedouc
 Pøi ¹ikovné implementaci pomocí haldy dosáhneme èasové slo¾itosti $\O(m\log n)$, v~pøí¹tí kapitole uká¾eme implementaci je¹tì ¹ikovnìj¹í.
 
 \s{Cvièení:}
-Naleznìte algoritmus pro výpoèet MST v~grafech ohodnocených vahami $\{1,\ldots k\}$ se slo¾itostí $\O(mk)$.
+Naleznìte jednoduchý algoritmus pro výpoèet MST v~grafech ohodnocených vahami $\{1,\ldots k\}$ se slo¾itostí $\O(mk)$
+nebo dokonce~$\O(m+nk)$.
 
 \references
 \bye