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 8c27cf3572414fce2b1c6710aef25ad10c6d3bb2..257f169620a12003b9e7d8e6229e93290dc2a0fe 100644 (file)
--- a/5-mst/5-mst.tex
+++ b/5-mst/5-mst.tex
@@ -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))$.