0-intro/0-intro.tex

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