Mercurial > latex
changeset 31:58f40757c8a7
replace lr-partition by lr-zerlegung everywhere
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Tue, 22 May 2012 01:01:52 +0200 |
parents | fde4d86d62f8 |
children | 4eda7e5c49d7 |
files | planarity/presentation.pdf planarity/presentation.tex |
diffstat | 2 files changed, 7 insertions(+), 7 deletions(-) [+] |
line wrap: on
line diff
--- a/planarity/presentation.tex Mon May 21 23:58:31 2012 +0200 +++ b/planarity/presentation.tex Tue May 22 01:01:52 2012 +0200 @@ -399,17 +399,17 @@ \path<3>[right edge] (\source) -- (\dest); \draw<2> (0,0) node {DFS}; - \draw<3> (0,0) node {LR-Partition}; + \draw<3> (0,0) node {LR-Zerlegung}; \end{tikzpicture} \end{figure} \end{frame} \begin{frame} - \frametitle{LR-Partition} + \frametitle{LR-Zerlegung} \begin{itemize} \item Jede Rückwärtskante erzeugt einen \alert{Zyklus} - \item LR-Partition teilt Zyklen in solche im und gegen den Uhrzeigersinn + \item LR-Zerlegung teilt Zyklen in solche im und gegen den Uhrzeigersinn \item Quelle \alert{außen} \item \alert{Verschachtelung} nur bei gleicher Orientierung \end{itemize} @@ -439,10 +439,10 @@ \end{frame} \begin{frame} - \frametitle{LR-Partition} + \frametitle{LR-Zerlegung} \begin{definition} - Sei $G = (V, T \uplus B)$ ein \alert{DFS-orientierter} Graph. Eine Partition $B = L \uplus R$ seiner Rückwärtskanten heißt \alert{Links-Rechts-Partition} wenn für jeden Knoten mit ausgehenden Kanten $e_1$, $e_2$ gilt: + Sei $G = (V, T \uplus B)$ ein \alert{DFS-orientierter} Graph. Eine Zerlegung $B = L \uplus R$ seiner Rückwärtskanten heißt \alert{Links-Rechts-Zerlegung} wenn für jeden Knoten mit ausgehenden Kanten $e_1$, $e_2$ gilt: \begin{itemize} \item Alle Rückwärtskanten von $e_1$ mit ihrem Ende über $lowpt(e_2)$ gehören zur einen und \item Alle Rückwärtskanten von $e_2$ mit ihrem Ende über $lowpt(e_1)$ gehören zur anderen Klasse. @@ -474,10 +474,10 @@ \end{frame} \begin{frame} - \frametitle{LR-Partition} + \frametitle{LR-Zerlegung} \begin{theorem} - Ein Graph ist genau dann planar, wenn er eine \alert{LR-Partition} zulässt. + Ein Graph ist genau dann planar, wenn er eine \alert{LR-Zerlegung} zulässt. \end{theorem} \vspace{2em}