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 zmapovat celé v~dne¹ní dobì ji¾ znaènì rozko¹atìlé odvìtví
+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ì:
$$\vbox{\halign{\it #\hfil\cr
-Toky, øezy a Ford-Fulkersonùv algoritmus: Radovan ©esták \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
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ù.
-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~\cite{schrijver}.
+\medskip
+
+\>V~Praze v~bøeznu 2007
+
+\rightline{Martin Mare¹\qquad\qquad}
+
+\bigskip
\h{Znaèení}
\itemize\ibull
\:$G$ bude znaèit koneèný {\I graf} na~vstupu algoritmu (podle potøeby buïto orientovaný
- nebo neorientovaný; multigraf pouze tehdy, bude-li explicitnì øeèeno).
+ 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~zavorkách). Hranu z~vrcholu~$u$
+ 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
\endlist
\>Také budeme bez újmy na~obecnosti pøedpokládat, ¾e zpracovávaný graf je souvislý
-a ¾e nesouvislé grafy nejprve rozlo¾íme na~komponenty souvislosti. È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)$.
+È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