]> mj.ucw.cz Git - ga.git/blob - 0-intro/0-intro.tex
Merge branch 'master' of git+ssh://git.ucw.cz/home/mj/GIT/ga
[ga.git] / 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