Mercurial > latex

changeset 9:e31918783bb4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add lr-order
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 08 May 2012 22:46:33 +0200
parents 68eb440295ea
children a2eb53d53650
files planarity/presentation.tex
diffstat 1 files changed, 117 insertions(+), 21 deletions(-) [+]
line wrap: on
line diff
--- a/planarity/presentation.tex	Tue May 08 16:29:43 2012 +0200
+++ b/planarity/presentation.tex	Tue May 08 22:46:33 2012 +0200
@@ -46,8 +46,11 @@
 \pgfsetlayers{background,main}
 \tikzstyle{vertex}=[circle,draw,fill=blue!25,minimum size=20pt,inner sep=0pt]
 \tikzstyle{selected vertex} = [vertex, fill=red!50]
+\tikzstyle{small vertex} = [vertex, minimum size=12pt]
 \tikzstyle{edge} = [draw,thick,-]
 \tikzstyle{tree edge} = [draw,very thick,->]
+\tikzstyle{left edge} = [draw,thick,->, red]
+\tikzstyle{right edge} = [draw,thick,->, blue]
 \tikzstyle{back edge} = [draw,dashed,arrows={-latex}]
 \tikzstyle{selected edge} = [draw,line width=5pt,-,red!50]
 
@@ -170,7 +173,7 @@
 \end{figure}		
 		\vspace{1em}
 
-		\item<2-> Eine \alert{Zeichnung $\Gamma$} ordnet jedem Knoten Koordinaten und jeder Kante eine offene Jordankurve zu.
+		\item<2-> Eine \alert{Zeichnung} ordnet jedem Knoten Koordinaten und jeder Kante eine offene Jordankurve zu.
 		\item<2-> \alert{planar}: Keine sich überschneidenden Kurven
 		\item<2-> \alert{äquivalent}: Gleiche Reihenfolge der Kanten an Knoten
 	\end{itemize}
@@ -201,7 +204,7 @@
 	\begin{tikzpicture}[auto]
     \foreach \pos/ \name in {{(0,1)/a}, {(1,1)/b}, {(2,1)/c},{(0,2)/d},{(1,2)/e},{(2,2)/f},
                             {(4.164,1)/g}, {(5.464,1)/h}, {(5.626,1.986)/i},{(4.814,2.75)/j},{(4,1.986)/k}}
-        \node[vertex, minimum size=10pt] (\name) at \pos {};
+        \node[small vertex] (\name) at \pos {};
         
     \foreach \source/ \dest in {a/d, a/e, a/f,
                                 b/d, b/e, b/f,
@@ -445,7 +448,7 @@
 				\item Wurzel
 				\item DFS-Baum
 				\item Rückwärtskante
-				\item returning edge
+				\item Rückkehrkante (\emph{returning edge})
 				\vspace{2em}
 				\item<2> DFS-Index
 				\item<2> \alert{lowpoint}\\ $lowpt([5]) = 2$
@@ -489,8 +492,8 @@
 	\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 eingehender Baumkante $e$ und ausgehenden Kanten $e_1$, $e_2$ gilt:
 		\begin{itemize}
-			\item Alle return edges von $e_1$ mit ihrem Ende über $lowpt(e_2)$ gehören zur einen und
-			\item Alle return edges von $e_2$ mit ihrem Ende über $lowpt(e_1)$ gehören zur anderen Klasse.
+			\item Alle Rückkehrkanten von $e_1$ mit ihrem Ende über $lowpt(e_2)$ gehören zur einen und
+			\item Alle Rückkehrkanten von $e_2$ mit ihrem Ende über $lowpt(e_1)$ gehören zur anderen Klasse.
 		\end{itemize}
 	\end{definition}
 \end{frame}
@@ -505,33 +508,126 @@
 	\vspace{2em}	
 		
 	\begin{itemize}
-		\item Jede Rückwärtskante erzeugt einen \alert{fundamentalen Zyklus}
+		\item Jede Rückwärtskante erzeugt einen \alert{Zyklus}
 		\item LR-Partition teilt Zyklen in solche im und gegen den Uhrzeigersinn
 		
 		\vspace{1em}
 		
 		\item Planare Zeichnung $\rightarrow$ LR-Zerlegung ist einfach
-		\item Umkehrung:
-		\begin{itemize}
-			\item Erweiterung um Baumkanten
-			\item Richtige Verschachtelung an Knoten
-		\end{itemize}
-	\end{itemize}
-\end{frame}
-
-\begin{frame}
-	\frametitle{Baumkanten}
-	Hat die Baumkante return edges?
-	\vspace{1.5em}
-	\begin{itemize}
-		\item \textbf{Nein} Seite egal
-		\item \textbf{Ja} Selbe Seite wie eine return-edge zum \alert{highpoint}
 	\end{itemize}
 \end{frame}
 
 \begin{frame}
 	\frametitle{Verschachtelung}
 	
+	\begin{block}{Beobachtung}
+	Baumkante $e_1$ außerhalb von Baumkante $e_2$ wenn
+	\vspace{1.5em}
+	\begin{itemize}
+		\item $lowpt(e_1) < lowpt(e_2)$
+		\item $lowpt(e_1) = lowpt(e_2)$ und $e_2$ eine Sehne besitzt
+	\end{itemize}	
+	\end{block}
+	\begin{center}
+	\begin{figure}
+	\begin{tikzpicture}[auto]
+	\useasboundingbox (-2, 0.5) rectangle (7, 5);	
+	
+    \draw[edge] (0,1) -- (0,3);
+    \draw[edge] (-1.5,4) -- (0,3);
+    \draw[edge] (1.5,4) -- (0,3);
+    
+    \draw[back edge, rounded corners] (-1.5,4) .. controls (4,6) and (1,1) .. (0,1);
+    \draw[back edge] (1.5,4) .. controls (0.5,2) .. (0,2);    
+
+
+    \draw[edge] (4.5,1) -- (4.5,3);
+    \draw[edge] (3,4) -- (4.5,3);
+    \draw[edge] (6,4) -- (4.5,3);
+    
+    \draw[back edge, rounded corners] (3,4) .. controls (8.5,6) and (5.5,1) .. (4.5,1);
+    \draw[back edge] (6,4) .. controls (5,2) .. (4.5,2);   
+    \draw[back edge] (6,4) .. controls (5.5,2) .. (4.5,1);   
+	\end{tikzpicture}
+	\end{figure}
+	\end{center}
+\end{frame}
+
+\begin{frame}
+	\frametitle{Verschachtelung}
+	
+	\begin{definition}
+		Seien $e_1^L,\ldots,e_l^L$ die linken ausgehenden Baumkanten und $e_1^R,\ldots,e_r^R$ die rechten ausgehenden Baumkanten eines Knotens $v$ und $u$ sein Elternknoten. Dann ist die \alert{LR-Ordnung} im Uhrzeigersinn
+		\begin{align*}
+			&(u,v),\\
+			&L(e_l^L),e_l^L,R(e_l^L),\ldots,R(e_1^L),\\
+			&L(e_1^R),\ldots,L(e_r^R),e_r^R,R(e_r^R)
+		\end{align*}
+	\end{definition}
+
+	\alert{$L(e)$} bezeichnet die linken eingehenden Rückwärtskanten deren Kreise sich $e$ teilen.
+\end{frame}
+
+\begin{frame}
+	\frametitle{Verschachtelung}	
+	\begin{block}{Lemma}
+		Eine \alert{LR-Ordnung} stellt eine Planarisierung einer \alert{LR-Zerlegung} dar.
+	\end{block}
+		
+	\vspace{2em}	
+		
+	\begin{columns}[T]
+		\begin{column}{.5\textwidth}
+	\begin{figure}
+	\begin{tikzpicture}[auto, scale=0.5]
+	\useasboundingbox (-5, 0) rectangle (5, 6);	
+	
+	\node[vertex] (u) at (0,0) {$u$};
+	\node[vertex] (v) at (0,3) {$v$};
+	\node[vertex] (w) at (-4,3) {$e_l^L$};
+	\node[vertex] (x) at (-3,5) {$e_2^L$};
+	\node[vertex] (y) at (-1,6) {$e_1^L$};		
+	\node[vertex] (a) at (1,6) {$e_1^R$};	
+	\node[vertex] (b) at (3,5) {$e_2^R$};	
+	\node[vertex] (c) at (4,3) {$e_r^R$};			
+	
+	\path[edge, ->] (u) -- (v);
+	\path[left edge] (v) -- (w);
+	\path[left edge] (v) -- (x);
+	\path[left edge] (v) -- (y);
+	\path[right edge] (v) -- (a);
+	\path[right edge] (v) -- (b);
+	\path[right edge] (v) -- (c);
+	
+	\end{tikzpicture}
+	\end{figure}
+		\end{column}
+		\begin{column}{.5\textwidth}
+	\begin{figure}
+	\begin{tikzpicture}[auto, scale=0.5]
+	\useasboundingbox (-5, 0) rectangle (5, 6);	
+	
+	\node[vertex] (u) at (0,0) {$u$};
+	\node[vertex] (v) at (0,3) {$v$};
+	\node[vertex] (w) at (-2,5) {$e^L$};
+	\node[vertex] (x) at (2, 5) {$e^R$};	
+	
+	\path[edge, ->] (u) -- (v);
+	\path[left edge] (v) -- (w);
+	\path[right edge] (v) -- (x);
+	
+	\draw[edge] (w) -- (-4,7);
+	\draw[left edge] (-4,7) .. controls(-4, 3.5) .. (v);
+	\draw[left edge] (-4,7) .. controls(-2.5, 3.5) .. (v);	
+	\draw[right edge] (-4,7) .. controls(-2, 7) .. (v);	
+	
+	\draw[edge] (x) -- (4,7);
+	\draw[left edge] (4,7) .. controls(4, 3.5) .. (v);	
+	\draw[right edge] (4,7) .. controls(2, 7) .. (v);	
+	\end{tikzpicture}
+	\end{figure}		
+		\end{column}
+	\end{columns}
 \end{frame}
 
 \subsection{Knotenbasiert}