\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
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ů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
Q-Heapy: Cyril Strejc \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ů.

\medskip

\>V~Praze v~březnu 2007

\rightline{Martin Mareš\qquad\qquad}

\bigskip

\h{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.
\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)$.

\references
\bye
