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 vnìj¹í,} pokud z~nìj vede zpìtná hrana do~je¹tì
  25 nenakreslené èásti grafu (\uv{nad $v$}), nebo pokud je akrtikulací,
  26 pod ní¾ je pøipojen podgraf obsahující takový vrchol.
  27
  28 \item
  29 Vrchol~$w$ je {\bf ¾ivý,} pokud z~nìj vede zpìtná hrana do~$v$.
  30
  31 \item
  32 Podobnì pro bloky (podle koøene) a zpìtné hrany.
  33
  34 \end{itemize}
  35
  36 \end{frame}
  37
  38 \begin{frame}{Pravidla obcházení}
  39
  40 {\bf P1:}
  41 V~ka¾dém ¾ivém vrcholu zpracováváme:
  42 \begin{enumerate}
  43 \item zpìtné hrany do~$v$
  44 \item podøízené ¾ivé vnitøní bloky
  45 \item podøízené ¾ivé vnìj¹í bloky
  46 \end{enumerate}
  47
  48 ~
  49
  50 {\bf P2:}
  51 Vstoupíme-li do podøízeného bloku, vybereme si smìr:
  52 \begin{enumerate}
  53 \item k~¾ivému vnitønímu vrcholu
  54 \item k~¾ivému vnìj¹ímu vrcholu
  55 \end{enumerate}
  56
  57 Pokud se tento smìr li¹í od~dosavadního, podøízený blok a v¹e pod ním
  58 pøeklopíme.
  59
  60 \end{frame}
  61
  62 \begin{frame}{Algoritmus}
  63
  64 \begin{enumerate}
  65 \item Pokud má graf více ne¾ $3n-6$ hran $\Rightarrow$ {\sc nerovinný.}
  66 \item Prohledáme graf do hloubky: {\it Enter, Ancestor, LowPoint.}
  67 \item<3-> Sestrojíme {\it BlockList}y a setøídíme je.
  68 \item Pro vrcholy~$v$ v~poøadí klesajících {\it Enter\/}ù kreslíme:
  69 \item Nakreslíme stromové hrany z~$v$ dolù jako triviální bloky (2-cykly).
  70 \advance\leftskip by 2em
  71 \item<4-> Oznaèíme ¾ivý podgraf.
  72 \item Pro ka¾dého syna vrcholu~$v$ obcházíme hranici v~obou smìrech
  73       a kreslíme zpìtné hrany do~$v$. Øídíme se pravidly {\bf P1} a {\bf P2,}
  74       za vnìj¹ím vrcholem se zastavíme.
  75 \item Zbývá-li nìjaká zpìtná hrana do~$v$ $\Rightarrow$ {\sc nerovinný.}
  76
  77 \advance\leftskip by -2em
  78 \item<2-> Zorientujeme seznamy sousedù $\Rightarrow$ hotové nakreslení.
  79 \end{enumerate}
  80
  81 \end{frame}
  82
  83 \end{document}