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}