]> mj.ucw.cz Git - ga.git/blob - 11-planar/slides/planar.tex
Planarita: Slidy opraveny a prizpusobeny novym terminum
[ga.git] / 11-planar / slides / planar.tex
1 \documentclass{beamer}
2 \usepackage[latin2]{inputenc}
3 \usepackage[czech]{babel}
4 \usepackage{palatino}
5 \usetheme{Warsaw}
6 \title[Kreslení grafù do roviny]{Kreslení grafù do roviny}
7 \author[Martin Mare¹]{Martin Mare¹\\\texttt{mj@ucw.cz}}
8 \institute{Charles University in Prague\\Faculty of Math and Physics\\Department of Applied Mathematics}
9 \date{}
10 \begin{document}
11 \setbeamertemplate{navigation symbols}{}
12 \setbeamerfont{title page}{family=\rmfamily}
13
14 \begin{frame}{Stavy vrcholù}
15
16 Pøi kreslení vrcholu~$v$ budeme oznaèovat vrcholy v~u¾ nakreslené
17 èásti takto:
18
19 ~
20
21 \begin{itemize}
22
23 \item
24 Vrchol~$w$ je {\bf externí,} pokud z~nìj vede zpìtná hrana do~je¹tì
25 nenakreslené èásti grafu (\uv{nad $v$}), nebo pokud je artikulací,
26 pod ní¾ je pøipojen podgraf obsahující takový vrchol. Ostatní vrcholy
27 jsou {\bf interní.}
28
29 \item
30 Vrchol~$w$ je {\bf ¾ivý,} pokud z~nìj vede zpìtná hrana do~$v$.
31
32 \item
33 Podobnì pro bloky (podle koøene) a zpìtné hrany.
34
35 \end{itemize}
36
37 \end{frame}
38
39 \begin{frame}{Pravidla obcházení}
40
41 {\bf P1:}
42 V~ka¾dém ¾ivém vrcholu zpracováváme:
43 \begin{enumerate}
44 \item zpìtné hrany do~$v$
45 \item podøízené ¾ivé interní bloky
46 \item podøízené ¾ivé externí bloky
47 \end{enumerate}
48
49 ~
50
51 {\bf P2:}
52 Vstoupíme-li do podøízeného bloku, vybereme si smìr:
53 \begin{enumerate}
54 \item k~¾ivému internímu vrcholu
55 \item k~¾ivému externímu vrcholu
56 \end{enumerate}
57
58 Pokud se tento smìr li¹í od~dosavadního, podøízený blok a v¹e pod ním
59 pøeklopíme.
60
61 \end{frame}
62
63 \begin{frame}{Algoritmus}
64
65 \begin{enumerate}
66 \item Pokud má graf více ne¾ $3n-6$ hran $\Rightarrow$ {\sc nerovinný.}
67 \item Prohledáme graf do hloubky: {\it Enter, Ancestor, LowPoint.}
68 \item<3-> Sestrojíme {\it BlockList}y a setøídíme je.
69 \item Pro vrcholy~$v$ v~poøadí klesajících {\it Enter\/}ù kreslíme:
70 \item Nakreslíme stromové hrany z~$v$ dolù jako triviální bloky (2-cykly).
71 \advance\leftskip by 2em
72 \item<4-> Oznaèíme ¾ivý podgraf.
73 \item Pro ka¾dého syna vrcholu~$v$ obcházíme hranici v~obou smìrech
74       a kreslíme zpìtné hrany do~$v$. Øídíme se pravidly {\bf P1} a {\bf P2,}
75       za externím vrcholem se zastavíme.
76 \item Zbývá-li nìjaká zpìtná hrana do~$v$ $\Rightarrow$ {\sc nerovinný.}
77
78 \advance\leftskip by -2em
79 \item<2-> Zorientujeme seznamy sousedù $\Rightarrow$ hotové nakreslení.
80 \end{enumerate}
81
82 \end{frame}
83
84 \end{document}