From 6f15ac12d97a3607b5a27a475c752072079c6794 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sun, 20 May 2007 22:28:14 +0200
Subject: [PATCH] Korekce preklepu.

---
 12-kostry/12-kostry.tex | 96 ++++++++++++++++++++---------------------
 1 file changed, 47 insertions(+), 49 deletions(-)

diff --git a/12-kostry/12-kostry.tex b/12-kostry/12-kostry.tex
index 6b0c726..6e12cec 100644
--- a/12-kostry/12-kostry.tex
+++ b/12-kostry/12-kostry.tex
@@ -1,11 +1,11 @@
 \input lecnotes.tex
 
-\prednaska{10}{Problém minimálni kostry}{(zapsali K. Ka¹èák a M. Vachna)}
+\prednaska{12}{Problém minimální kostry}{(zapsali K. Ka¹èák a M. Vachna)}
 
-Pro zaèátek si definujme, co budeme dìlat, v jakých grafech budeme minimálni kostru hledat.
+Pro zaèátek si definujme, co budeme dìlat, v jakých grafech budeme minimální kostru hledat.
 
 \s{Zadání úlohy:} Pro neorientovaný graf $G$ s ohodnocením hran $w: E(G) \rightarrow R$,
-chceme najít kostru $T$ s minimálnim ohodnocením $w(T)=\sum_{e\in E(T)} w(e)$.
+chceme najít kostru $T$ s minimálním ohodnocením $w(T)=\sum_{e\in E(T)} w(e)$.
 
 \s{Pøedpoklady úlohy:}
 \itemize\ibull
@@ -13,7 +13,7 @@ chceme naj
 \:$\forall e,f \in E(G$) : $e\neq f \Rightarrow w(e)\neq w(f)$
 \endlist
 
-Nyní si uká¾eme tøi algoritmy øe¹íci zadanú úlohu, konkrétne se jedná o Jarníkùv, Borùvkùv a Kruskalùv
+Nyní si uká¾eme tøi algoritmy øe¹ící zadanou úlohu, konkrétnì se jedná o Jarníkùv, Borùvkùv a Kruskalùv
 algoritmus.
 
 \s{Algoritmus:} (Jarníkùv)
@@ -27,36 +27,36 @@ algoritmus.
 \:		$T\leftarrow T+uv$
 \endalgo
 
-\s{Vìta:} Jarníkùv algorimtus se zastaví po maximálne $n$ iteracích a vydá minimálni kostru grafu $G$.
+\s{Vìta:} Jarníkùv algoritmus se zastaví po maximálnì $n$ iteracích a vydá minimální kostru grafu $G$.
 
 \proof
-Koneènost - pøi ka¾dé iteraci se pøidá jeden vrchol $\Rightarrow$ po maximálne $n$ iteracích se zastaví.
-Vydaný graf je strom, proto¾e se stále pøidáva list k ji¾ existujícimu stromu. Vydaný graf má $n$
-vrcholù $\Rightarrow$ vydaný graf je kostra. Ostáva nám u¾ jen dokázat, ¾e kostra je minimálni. To
-dokazuje nesledujíci Lemma.
+Koneènost - pøi ka¾dé iteraci se pøidá jeden vrchol $\Rightarrow$ po maximálnì $n$ iteracích se zastaví.
+Vydaný graf je strom, proto¾e se stále pøidává list k ji¾ existujícímu stromu. Vydaný graf má $n$
+vrcholù $\Rightarrow$ vydaný graf je kostra. Zbývá nám u¾ jen dokázat, ¾e kostra je minimální. To
+dokazuje následující Lemma.
 \qed
 
-Proto aby jsme byli schopni sformulovat i dokázat Lemma, je nutná je¹tì vysvìtlit pojem øez v grafu.
+Proto aby jsme byli schopni zformulovat i dokázat Lemma, je nutná je¹tì vysvìtlit pojem øez v grafu.
 
 \s{Definice:} Øez v grafu $G=(V,E)$ je mno¾ina hran $F\subseteq E$ taková, ¾e $\exists  U\subset V$ :
 $F=\left\{uv\in E \vert u\in U, v\notin U \right\}$.
 
 \s{Lemma:} Pokud $G$ je graf, $w$ jeho prosté ohodnocení, $F$ je øez v grafu $G$ a $f$ je nejlehèí hrana v øezu
-$F$, pak pro ka¾dou minimálni kostru $G$ je $f\in E(T)$.
+$F$, pak pro ka¾dou minimální kostru $G$ je $f\in E(T)$.
 
 \proof
-Buï $T$ kostra a $f\notin E(T)$, pak $\exists$ cesta $P\subseteq T$ spojujíci $u$ a $v$ (vrcholy hrany $f$).
+Buï $T$ kostra a $f\notin E(T)$, pak $\exists$ cesta $P\subseteq T$ spojující $u$ a $v$ (vrcholy hrany $f$).
 Cesta musí øez alespoò jednou projít. $\exists e\in P \cap F$ taková, ¾e $w(e) > w(f)$. Uva¾me $T'=T-e+f$.
-$T'$ je rovne¾ kostra grafu $G$, proto¾e odebraním hrany $e$ se graf rozpadne na dvì komponenty a pøidáním
+$T'$ je rovnì¾ kostra grafu $G$, proto¾e odebraním hrany $e$ se graf rozpadne na dvì komponenty a pøidáním
 hrany $f$ se opìt spojí. $w(T')=w(T)-w(e)+w(f)<w(T)$
 \qed
 
-\s{Dùsledky:} Graf $G$ s prostým ohodnocením ma pravì 1 minimálni kostru. Minimálni kostra je
-jednoznaène urèená lineárnim uspoøádaním hran.
+\s{Dùsledky:} Graf $G$ s prostým ohodnocením má pravì 1 minimální kostru. Minimální kostra je
+jednoznaènì urèená lineárním uspoøádáním hran.
 
 \s{Implementace:}
 \itemize\ibull
-\:Pøímoèaøá - pamatujeme si, které vrcholy a hrany jsou v kostøe $T$ a které ne. Èasová slo¾itost je $\O(nm)$
+\:Pøímoèará - pamatujeme si, které vrcholy a hrany jsou v kostøe $T$ a které ne. Èasová slo¾itost je $\O(nm)$
 \:Pro $v\notin V(T)$ si pamatujeme $D(v)=$min$\left\{uv, u\in T\right\}$. Èasová slo¾itost je $\O(n^2+m)=\O(n^2)$
 \endlist
 
@@ -71,19 +71,19 @@ jednozna
 \:		V¹echny hrany $t_i$ pøidáme do $F$.
 \endalgo
 
-\s{Vìta:} Borùvkùv algorimtus se zastaví po $\left\lceil \log_2 n\right\rceil$ iteracích a vydá minimálni kostru grafu $G$.
+\s{Vìta:} Borùvkùv algoritmus se zastaví po $\left\lceil \log_2 n\right\rceil$ iteracích a vydá minimální kostru grafu $G$.
 
 \proof
-Po $k$ iteracích mají v¹echny stromy minimálne $2^k$ vrcholù, $\forall$ i : $\vert T_i\vert \geq 2^k$.
+Po $k$ iteracích mají v¹echny stromy minimálnì $2^k$ vrcholù, $\forall$ i : $\vert T_i\vert \geq 2^k$.
 Indukcí podle $k$: ka¾dá incidentní hrana vede z $T_i$ do $T_j$. Po $k$ iteracích pøidáním incidentní hrany
-spojíme 2 stromy s alespoò $2^k$ vrcholama, tím vznikne strom s $2^{k+1}$ vrcholama.
-Algoritmus vydá kostru, staèí nahlédnout, zda je minimálni. To se lehce uká¾e u¾itím pøedchozí Lemmy.
-V¾dy pøidávame hranu, která je minimálni mezi $T$ a ostatními vrcholy grafu $G$.
+spojíme 2 stromy s alespoò $2^k$ vrcholy, tím vznikne strom s $2^{k+1}$ vrcholy.
+Algoritmus vydá kostru, staèí nahlédnout, zda je minimální. To se lehce uká¾e u¾itím pøedchozí Lemmy.
+V¾dy pøidáváme hranu, která je minimální mezi $T$ a ostatními vrcholy grafu $G$.
 \qed
 
-\s{Implemntace:}
+\s{Implementace:}
 \itemize\ibull
-\:Inicializace pøímoèaøá.
+\:Inicializace pøímoèará.
 \:Pomocí DFS rozlo¾íme les na komponenty. $\forall$ vrchol si pamatujeme èíslo komponenty.
 \:Pro $\forall$ hranu zjistíme, do které komponenty patøí a pro ka¾dou komponentu
 jsi uchováme nejlehèí hranu.
@@ -96,26 +96,26 @@ Rozlo
 \def\concat{\mathop{\hbox{.}}}
 
 \algo
-\:Zetøídime v¹echny hrany z $E$ : $w(e_1)<...<w(e_m)$.
+\:Setøídíme v¹echny hrany z $E$ : $w(e_1)<...<w(e_m)$.
 \:$F\leftarrow (V(G),\emptyset)$.
 \:Pro $i=1$ do $m$ :
 \:		pokud $F+e_i$ je acyklický :
 \:		$F\leftarrow F+e_i$
 \endalgo
 
-\s{Vìta:} Kruskalùv `hladový` algorimtus se zastaví po $m$ iteracích a vydá minimálni kostru grafu $G$.
+\s{Vìta:} Kruskalùv `hladový` algoritmus se zastaví po $m$ iteracích a vydá minimální kostru grafu $G$.
 
 \proof
-Podle Lemmy strom, který je výstupem algorimtu, je minimálni kostra. Indukcí snadno doká¾eme, ¾e
-stále platí $F\subseteq$ $minimálni$ $kostry$ a v¾dy do $F$ pøidávame hranu $f$, která je minimálni v øezu
+Podle Lemmy strom, který je výstupem algoritmu, je minimální kostra. Indukcí snadno doká¾eme, ¾e
+stále platí $F\subseteq$ $minimálni$ $kostry$ a v¾dy do $F$ pøidáváme hranu $f$, která je minimální v øezu
 a spojuje dvì komponenty.
 \qed
 
-\s{Implemntace:}
+\s{Implementace:}
 \itemize\ibull
-\:Zotøídení $\O(m\log n)$.
+\:Setøídìní $\O(m\log n)$.
 \:Kdy¾ si pamatuji vrcholy $v$ poli:
-Find(u,v) zistí zda vrcholy $u$ a $v$ le¾í v stejné komponente. Jedna operace má èasovou slo¾itost $\O(1)$. Find
+Find(u,v) zjistí zda vrcholy $u$ a $v$ le¾í v stejné komponente. Jedna operace má èasovou slo¾itost $\O(1)$. Find
 se provede $m-$krát, proto je èasová slo¾itost celkem $\O(m)$.
 Union(u,v) pøidá hranu a tím spojí dvì komponenty. Jedna operace má èasovou slo¾itost $\O(n)$. Union se provede
 $n-$krát, proto je èasová slo¾itost celkem $\O(n^2)$.
@@ -125,53 +125,53 @@ V
 svého otce, $\forall$ koøen si pamatuje velikost komponenty.
 Find(u,v) najde koøeny a porovná je. Èasová slo¾itost je $\O(hloubka$ $komponenty)$.
 Union(u,v) najde koøeny a pøipojí men¹í komponentu pod vìt¹í (logaritmická hloubka). Èasová slo¾itost je $\O(hloubka$ $komponenty)$.
-Find a Union mají teda èasovou slo¾itost $\O(\log n)$. Výslední èasová slo¾itost je $\O(m\log n)$.
+Find a Union mají tedy èasovou slo¾itost $\O(\log n)$. Výslední èasová slo¾itost je $\O(m\log n)$.
 \endlist
 
 \s{Lemma:} Strom hloubky $h$ má alespoò $2^h$ prvkù.
 
 \proof
-Pokud Union spojí stromy jeden s hloubkou $h$ a druhý s hloubkou men¹í ne¾ $h$, pak hloubka výsledního
-stromu zústava $h$. Pokud spojuje dva stromy hloubky $h$, pak vyslední strom má hloubku $h+1$. Jak ji¾
-víme, strom hloubky $h$ má minimálne $2^h$, proto výslednej strom hloubky $h+1$ má $2^{h+1}$ vrcholù.
+Pokud Union spojí stromy jeden s hloubkou $h$ a druhý s hloubkou men¹í ne¾ $h$, pak hloubka výsledného
+stromu zùstává $h$. Pokud spojuje dva stromy hloubky $h$, pak výsledný strom má hloubku $h+1$. Jak ji¾
+víme, strom hloubky $h$ má minimálnì $2^h$, proto výsledný strom hloubky $h+1$ má $2^{h+1}$ vrcholù.
 \qed
 
 \h{Èerveno-èerné stromy}
 
-\s{Definice:} Èerveno-èerný strom je binárny vyhledávaci strom s barevnými(èervenými a èernými) vrcholy a
-externými vrcholy. Kdy¾ vrchol nemá nìkterého ze synú, na jeho míste je externý vrchol.
+\s{Definice:} Èerveno-èerný strom je binární vyhledávací strom s barevnými(èervenými a èernými) vrcholy a
+externími vrcholy. Kdy¾ vrchol nemá nìkterého ze synù, na jeho místì je externí vrchol.
 
 \s{Axiomy:}
 \itemize\ibull
-\:Koøen a externé vrcholy sú èerné.
+\:Koøen a externí vrcholy jsou èerné.
 \:Otec èerveného vrcholu je èerný.
 \:Na v¹ech cestách z koøene do externího vrcholu je stejný poèet èerných vrcholù.
 \endlist
 
 \s{Vìta:} Èerveno-èerný strom na $n$ vrcholech má hloubku $\O(\log n)$.
 
-K této vìtì nabízime dva dùkazy.
+K této vìtì nabízíme dva dùkazy.
 
 \proof
-1. Skomprimujeme hrany èerný-èervený a èerné vrcholy, které májí dva èervené syny, na vrchol.
-Vznikne $2,4-$strom, který ma hloubku $\log n$, a proto je èerveno-èerný strom maximálne
+1. Zkomprimujeme hrany èerný-èervený a èerné vrcholy, které mají dva èervené syny, na vrchol.
+Vznikne $2,4-$strom, který má hloubku $\log n$, a proto je èerveno-èerný strom maximálnì
 2x vìt¹í.
 \qed
 
 \proof
-2. Pøedpokladejme, ¾e $T$ je èerveno-èerný strom, který má na cestì z koøene do listu
-$k$ èerných vrcholù. Pak pre poèet vrcholù stromu $T$ platí $2^k-1\leq n \leq 2^{2k}-1$. Nejmen¹í takový strom má v¹echny vrcholy obarvené èernì a je to úplný
-pravidelný binární strom o hloubce $k-1$, co¾ dáva dolní odhad. Nejvìt¹í takový strom má v¹echny vrcholy v sudých hladinách obarveny èervenì a v lichých hladinách èernì, je to ùplný pravidelný binární strom o hloubce $2k-1$ a tím je dán horní odhad. Tedy $k\leq 1+\log n$. Z vlastností èerveno-èerných stromù plyne, ¾e $k\leq hloubka(T) \leq 2k$.
+2. Pøedpokládejme, ¾e $T$ je èerveno-èerný strom, který má na cestì z koøene do listu
+$k$ èerných vrcholù. Pak pro poèet vrcholù stromu $T$ platí $2^k-1\leq n \leq 2^{2k}-1$. Nejmen¹í takový strom má v¹echny vrcholy obarvené èernì a je to úplný
+pravidelný binární strom o hloubce $k-1$, co¾ dává dolní odhad. Nejvìt¹í takový strom má v¹echny vrcholy v sudých hladinách obarveny èervenì a v lichých hladinách èernì, je to úplný pravidelný binární strom o hloubce $2k-1$ a tím je dán horní odhad. Tedy $k\leq 1+\log n$. Z vlastností èerveno-èerných stromù plyne, ¾e $k\leq hloubka(T) \leq 2k$.
 \qed
 
-Niní si uká¾eme a rozebereme vkládaní do èerveno-èerných stromù.
+Nyní si uká¾eme a rozebereme vkládaní do èerveno-èerných stromù.
 
-\s{Insert:} (v èerveno-èernom strome)
+\s{Insert:} (v èerveno-èerném strome)
 BÚNO nový uzel $t$ bude èervený.
-Vlo¾íme uzel do stromu jako do standartního binárního vyhledávacího stromu.
+Vlo¾íme uzel do stromu jako do standardního binárního vyhledávacího stromu.
 Jestli¾e je pøedek èerný, jsme hotovi (viï obr. 1).
 \figure{01.eps}{obr. 1}{2in}
-Jestli¾e nikoliv, mù¾u nastat tøi nasledujíci pøípady:
+Jestli¾e nikoliv, mù¾u nastat tøi následující pøípady:
 \itemize\ibull
 \:Je-li vrchol $t$ èervený a jeho otec je také èervený, pak øekneme, ¾e $t$ je porucha. Je-li $t$ porucha,
 pak ji musíme nìjak opravit. Situace je na obrázku 2 - nejprve zále¾í na tom, jakou barvu má $s$, strýc $t$:
@@ -190,6 +190,4 @@ Pro spln
 \endalgo
 \endlist
 
-
-
 \bye
-- 
2.39.2