Uprava Makefiles, aby uploadovaly PDF misto PostScriptu.

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

diff --git a/5-mst/5-mst.tex b/5-mst/5-mst.tex
index 327c3255b34dd2d47972c2fcb962e9c806c86b26..257f169620a12003b9e7d8e6229e93290dc2a0fe 100644 (file)
--- a/5-mst/5-mst.tex
+++ b/5-mst/5-mst.tex
@@ -52,6 +52,8 @@ a vynech
 
 \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>.
 
@@ -63,8 +65,6 @@ 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