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