\input ../sgr.tex
-\prednaska{0}{Úvodem}{}
-
-Tento spisek vznikl jako uèební text k~pøedná¹ce z~grafových algoritmù,
-kterou pøedná¹ím na~Katedøe aplikované matematiky MFF UK v~Praze. Rozhodnì
-si neklade za cíl dùkladnì zmapovat celé v~dne¹ní dobì ji¾ znaènì rozko¹atìlé odvìtví
-informatiky zabývající se grafy, spí¹e se sna¾í ukázat nìkteré typické techniky
-a teoretické výsledky, které se pøi návrhu grafových algoritmù pou¾ívají.
-Zkrátka je to takový turistický prùvodce krajinou grafových algoritmù.
-
-Jeliko¾ pøedná¹ka se øadí mezi pokroèilé kursy, dovoluji si i v~tomto
-textu pøedpokládat základní znalosti teorie grafù a grafových algoritmù.
-V~pøípadì pochybností doporuèuji obrátit se na~nìkterou z~knih \cite{kapitoly},
-\cite{demel} a \cite{kucera}. Výbornou referenèní pøíruèkou, ze~které jsem èastokrát èerpal
-i já pøi sestavování pøedná¹ek, je také Schrijverova monumentální monografie
+\prednaska{0}{Úvodem}{}
+
+Tento spisek vznikl jako učební text k~přednášce z~grafových algoritmů,
+kterou přednáším na~Katedře aplikované matematiky MFF UK v~Praze. Rozhodně
+si neklade za cíl důkladně zmapovat celé v~dnešní době již značně rozkošatělé odvětví
+informatiky zabývající se grafy, spíše se snaží ukázat některé typické techniky
+a teoretické výsledky, které se při návrhu grafových algoritmů používají.
+Zkrátka je to takový turistický průvodce krajinou grafových algoritmů.
+
+Jelikož přednáška se řadí mezi pokročilé kursy, dovoluji si i v~tomto
+textu předpokládat základní znalosti teorie grafů a grafových algoritmů.
+V~případě pochybností doporučuji obrátit se na~některou z~knih \cite{kapitoly},
+\cite{demel} a \cite{kucera}. Výbornou referenční příručkou, ze~které jsem častokrát čerpal
+i já při sestavování přednášek, je také Schrijverova monumentální monografie
Combinatorial Optimization~\cite{schrijver}.
-Mé díky patøí studentùm Semináøe z~grafových algoritmù, na~kterém jsem
-na~jaøe 2006 první verzi této pøedná¹ky uvádìl, za~výbornì zpracované
-zápisky, je¾ se staly prazákladem tohoto textu. Jmenovitì:
+Mé díky patří studentům Semináře z~grafových algoritmů, na~kterém jsem
+na~jaře 2006 první verzi této přednášky uváděl, za~výborně zpracované
+zápisky, jež se staly prazákladem tohoto textu. Jmenovitě:
$$\vbox{\halign{\it #\hfil\cr
-Toky, øezy a Fordùv-Fulkersonùv algoritmus: Radovan ©esták \cr
-Dinicùv algoritmus: Bernard Lidický \cr
-Globální souvislost a párování: Jiøí Peinlich a Michal Kùrka \cr
+Toky, řezy a Fordův-Fulkersonův algoritmus: Radovan Šesták \cr
+Dinicův algoritmus: Bernard Lidický \cr
+Globální souvislost a párování: Jiří Peinlich a Michal Kůrka \cr
Gomory-Hu Trees: Milan Straka \cr
-Minimální kostry: Martin Kruli¹, Petr Su¹il, Petr ©koda a Tomá¹ Gavenèiak \cr
-Poèítání na RAMu: Zdenìk Vilu¹ínský \cr
+Minimální kostry: Martin Kruliš, Petr Sušil, Petr Škoda a Tomáš Gavenčiak \cr
+Počítání na RAMu: Zdeněk Vilušínský \cr
Q-Heapy: Cyril Strejc \cr
-Suffixové stromy: Tomá¹ Mikula a Jan Král \cr
-Dekompozice Union-Findu: Ale¹ ©nupárek \cr
+Suffixové stromy: Tomáš Mikula a Jan Král \cr
+Dekompozice Union-Findu: Aleš Šnupárek \cr
}}$$
-Dìkuji také tvùrcùm vektorového editoru Vrr, v~nìm¾ jsem kreslil vìt¹inu obrázkù.
+Děkuji také tvůrcům vektorového editoru Vrr, v~němž jsem kreslil většinu obrázků.
\medskip
-\>V~Praze v~bøeznu 2007
+\>V~Praze v~březnu 2007
-\rightline{Martin Mare¹\qquad\qquad}
+\rightline{Martin Mareš\qquad\qquad}
\bigskip
-\h{Znaèení}
+\h{Značení}
-\>V~celém textu se budeme dr¾et tohoto základního znaèení:
+\>V~celém textu se budeme držet tohoto základního značení:
\itemize\ibull
-\:$G$ bude znaèit koneèný {\I graf} na~vstupu algoritmu (podle potøeby buïto orientovaný
- nebo neorientovaný; multigraf jen bude-li explicitnì øeèeno).
-\:$V$ a $E$ budou mno¾iny {\I vrcholù} a {\I hran} grafu~$G$ (pøípadnì jiného grafu
- uvedeného v~závorkách). Hranu z~vrcholu~$u$
- do~vrcholu~$v$ budeme psát~$uv$, a» u¾ je orientovaná nebo~ne.
-\:$n$ a $m$ bude {\I poèet vrcholù a hran,} tedy $n:=\vert V\vert$, $m:=\vert E\vert$.
-\:Pro libovolnou mno¾inu $X$ vrcholù nebo hran bude $\overline X$ oznaèovat doplnìk
- této mno¾iny; pøitom z~kontextu by mìlo být v¾dy jasné, vzhledem k~èemu.
+\:$G$ bude značit konečný {\I graf} na~vstupu algoritmu (podle potřeby buďto orientovaný
+ nebo neorientovaný; multigraf jen bude-li explicitně řečeno).
+\:$V$ a $E$ budou množiny {\I vrcholů} a {\I hran} grafu~$G$ (případně jiného grafu
+ uvedeného v~závorkách). Hranu z~vrcholu~$u$
+ do~vrcholu~$v$ budeme psát~$uv$, ať už je orientovaná nebo~ne.
+\:$n$ a $m$ bude {\I počet vrcholů a hran,} tedy $n:=\vert V\vert$, $m:=\vert E\vert$.
+\:Pro libovolnou množinu $X$ vrcholů nebo hran bude $\overline X$ označovat doplněk
+ této množiny; přitom z~kontextu by mělo být vždy jasné, vzhledem k~čemu.
\endlist
-\>Také budeme bez újmy na~obecnosti pøedpokládat, ¾e zpracovávaný graf je souvislý
-Èasovou slo¾itost prùchodu grafem do~hloubky èi ¹íøky pak mù¾eme psát jako $\O(m)$,
-proto¾e víme, ¾e $n=\O(m)$.
+\>Také budeme bez újmy na~obecnosti předpokládat, že zpracovávaný graf je souvislý
+Časovou složitost průchodu grafem do~hloubky či šířky pak můžeme psát jako $\O(m)$,
+protože vÃme, že $n=\O(m)$.
\references
\bye
projects / ga.git / blobdiff