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