Mercurial > latex

changeset 17:b81399bc8f54

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Automated merge with https://hg.zfix.org/latex
author Markus Kaiser <markus.kaiser@in.tum.de>
date Sun, 20 May 2012 19:08:02 +0200
parents c5994931304f (current diff) 5f2c6173f5e3 (diff)
children 113dbe6b1869
files
diffstat 1 files changed, 92 insertions(+), 124 deletions(-) [+]
line wrap: on
line diff
--- a/planarity/presentation.tex	Sun May 13 21:18:46 2012 +0100
+++ b/planarity/presentation.tex	Sun May 20 19:08:02 2012 +0200
@@ -68,11 +68,11 @@
 %    \tableofcontents[currentsection]
 %  \end{frame}
 %}
-\AtBeginSection[]{
-	\begin{frame}[plain]
-		\begin{center} \LARGE\insertsectionhead \end{center} 	
-	\end{frame}
-}
+%\AtBeginSection[]{
+%	\begin{frame}[plain]
+%		\begin{center} \LARGE\insertsectionhead \end{center} 	
+%	\end{frame}
+%}
 
 \begin{document}
 
@@ -81,13 +81,11 @@
 \end{frame}
 
 % Inhaltsverzeichnis
-\begin{frame}
-  \frametitle{Inhalt}
-  \tableofcontents
-\end{frame}
+%\begin{frame}
+%  \frametitle{Inhalt}
+%  \tableofcontents
+%\end{frame}
 
-\section{Planarität}
-\subsection{Definitionen}
 \begin{frame}
 	\frametitle{Grundlegendes}
 	\begin{itemize}
@@ -98,8 +96,7 @@
 		\item<2-> \alert{einfach}: Keine Schleifen oder Mehrfachkanten
 		\item<2-> \alert{zusammenhängend}: Es existiert ein Pfad von jedem Knoten zu jedem Knoten
 		\item<2-> \alert{Baum}: Zyklenfreier zusammenhängender Graph
-		\item<2-> \alert{$k$-zusammenhängend}: Zusammenhängend nach Entfernen von $k$ Knoten
-		\item<2-> \alert{bipartit}: Aufteilung der Knoten in zwei Teilmengen ohne Kanten innerhalb der Mengen (\emph{zweifärbbar})
+		\item<2-> \alert{$k$-zusammenhängend}: Zusammenhängend nach Entfernen von $k-1$ Knoten
 	\end{itemize}
 \end{frame}
 
@@ -173,22 +170,13 @@
 \end{figure}		
 		\vspace{1em}
 
-		\item<2-> Eine \alert{Zeichnung} ordnet jedem Knoten Koordinaten und jeder Kante eine offene Jordankurve zu.
+		\item<2-> Eine \alert{Zeichnung} ordnet in $\R^2$ jedem Knoten Koordinaten und jeder Kante eine offene Jordankurve zu.
+		\item<2-> \alert{äquivalent}: Gleiche Reihenfolge der Kanten an Knoten
+		\vspace{2em}
 		\item<2-> \alert{planar}: Keine sich überschneidenden Kurven
-		\item<2-> \alert{äquivalent}: Gleiche Reihenfolge der Kanten an Knoten
 	\end{itemize}
 \end{frame}
 
-%\begin{frame}
-%	\frametitle{Eigenschaften}
-%	\begin{itemize}
-%		\item Planare Graphen sind \alert{4-färbbar},
-%		\item \alert{3-Färbbarkeit} linear
-%		\item \alert{$k$-Cliquen} polynomiell (da $k \leq 4$)
-%		\item \alert{Isomorphismus} linear
-%	\end{itemize}
-%\end{frame}
-
 \begin{frame}
 	\frametitle{Charakterisierung}
 	
@@ -221,37 +209,6 @@
 	\end{figure}
 \end{frame}
 
-\subsection{Erkennungsproblem}
-\begin{frame}
-	\frametitle{Erkennungsproblem}
-	\begin{itemize}
-		\item Ist ein gegebener Graph \alert{planar}?
-	\end{itemize}
-	\vspace{2em}
-	Damit verwandt:
-	\begin{itemize}
-		\item Wie sieht eine Planare Zeichnung (\emph{embedding}) aus?
-		\item Ausstellen von Zertifikaten zur Nichtplanarität
-		\item Was ist der maximale planare Teilgraph? (NP vollständig)
-	\end{itemize}
-\end{frame}
-
-\begin{frame}
-	\frametitle{Erweiterte Probleme}
-	\begin{itemize}
-		\item Vorgegebene Eigenschaften
-		\begin{itemize}
-			\item Knoten auf selber Facette
-			\item Knoten nebeneinander
-			\item Vorgezeichnete Teilgraphen
-		\end{itemize}
-		\item Äußere Planarität (\emph{outerplanarity})
-		\item Gerichtete Planarität
-	\end{itemize}
-\end{frame}
-
-\section{Algorithmen}
-\subsection{Vorüberlegungen}
 \begin{frame}
 	\frametitle{Vorüberlegungen}
 	\begin{columns}[T]
@@ -325,23 +282,19 @@
 \end{frame}
 
 \begin{frame}
-	\frametitle{Beispiel}
-	Dummy.
-\end{frame}
-
-\subsection{Kreisbasiert}
-\begin{frame}[plain]
-	\begin{center} \LARGE Kreisbasierte Algorithmen \end{center} 	
-\end{frame}
-\begin{frame}
-	\frametitle{Idee}
-	\begin{itemize}
-		\item Kreisfreie Graphen sind Wälder und planar.
-		\item Alle betrachteten Graphen sind \alert{2-zusammenhängend} (\emph{biconnected})
+	\frametitle{Algorithmen}
+	\begin{itemize}	
+		\item \alert{Knotenbasiert}
+		\begin{itemize}
+			\item Ein Graph bleibt planar wenn man einzelne Knoten entfernt
+			\item Prozess kann umgekehrt werden
+		\end{itemize}
 		\vspace{2em}
-		\item<2> Zyklen sind (geschlossene) Jordankurven
-		\item<2> Jede \alert{Jordankurve} teilt die Ebene in zwei Bereiche
-		\item<2> Teilgraphen müssen komplett inner- oder außerhalb des Zyklus sein
+		\item \alert{Kreisbasiert}
+		\begin{itemize}
+			\item Nur Graphen mit Zyklen können nicht planar sein
+			\item Zyklen trennen Ebene in zwei Bereiche
+		\end{itemize}
 	\end{itemize}
 \end{frame}
 
@@ -413,7 +366,6 @@
 	\end{theorem}
 \end{frame}
 
-\subsubsection{Auslander-Parter}
 \begin{frame}
 	\frametitle{Auslander-Parter}
 	\begin{block}{Algorithmus}
@@ -432,9 +384,8 @@
 	\end{itemize}
 \end{frame}
 
-\subsubsection{de Fraysseix-Ossona de Mendez-Rosenstiehl}
 \begin{frame}
-	\frametitle{FMR}
+	\frametitle{LR-Algorithmus}
 	\begin{itemize}
 		\item Auslander-Parter global, schwer zu implementieren
 		\vspace{2em}
@@ -453,7 +404,6 @@
 				\item Wurzel
 				\item DFS-Baum
 				\item Rückwärtskante
-				\item Rückkehrkante (\emph{returning edge})
 				\vspace{2em}
 				\item<2> DFS-Index
 				\item<2> \alert{lowpoint}\\ $lowpt([5]) = 2$
@@ -485,7 +435,6 @@
     \foreach \source/\dest/\ctrl in {{f/b/(2.5, 9.2)}, {g/c/(0.5,5)}, {d/a/(-2,2)},
                                      {j/b/(4.5, 3)}, {k/b/(6,3)}}
         \path[back edge] (\source) .. controls \ctrl .. (\dest);         
-        
 \end{tikzpicture}
 \end{figure}
 \vspace{1em}
@@ -494,13 +443,56 @@
 \end{frame}
 
 \begin{frame}
+	\frametitle{Beispiel}
+	
+\begin{figure}
+\begin{tikzpicture}[auto, scale=1.3]
+	\useasboundingbox (-4,0) rectangle (4,6);
+
+    \foreach \pos/\name in {{(0,1)/a},{(0,2)/b},{(1,3)/c},{(0.75,4)/d},{(-0.5,4.5)/e},
+                            {(-1.5,3.5)/f}, {(1.25,5.25)/g},
+                            {(0,5.5)/h}, {(2.5,6)/i}, {(4,5)/j},{(2.5,4.5)/k},
+                            {(-2,6)/l}, {(-2.5,5)/m}, {(-4,5)/n}}
+        \node[small vertex] (\name) at \pos {};
+        
+    
+    \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g,
+                                e/h, h/i, i/j, j/k,
+                                h/l, l/m, m/n}
+        \path<1>[edge] (\source) -- (\dest);
+        
+    \foreach \source/ \dest in {a/b, b/c, c/d, d/e, e/f, e/g,
+                                e/h, h/i, i/j, j/k,
+                                h/l, l/m, m/n}
+        \path<2->[tree edge] (\source) -- (\dest);        
+        
+    \foreach \source/ \dest in {f/b, k/c, k/i, j/a, g/d, m/e, n/l, n/a}
+        \path<1>[edge] (\source) -- (\dest);      
+        
+    \foreach \source/ \dest in {f/b, k/c, k/i, j/a, g/d, m/e, n/l, n/a}
+        \path<2>[back edge] (\source) -- (\dest); 
+        
+    \foreach \source/ \dest in {f/b, m/e, n/a}
+        \path<3>[left edge] (\source) -- (\dest);     
+        
+    \foreach \source/ \dest in {k/c, k/i, j/a, g/d, n/l}
+        \path<3>[right edge] (\source) -- (\dest); 
+        
+    \draw<1> (0,0) node {Graph};                     
+    \draw<2> (0,0) node {DFS};
+    \draw<3> (0,0) node {LR-Partition};
+\end{tikzpicture}
+\end{figure}
+\end{frame}
+
+\begin{frame}
 	\frametitle{LR-Partition}
 	
 	\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 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.
+			\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.
 		\end{itemize}
 	\end{definition}
 \end{frame}
@@ -525,11 +517,6 @@
 \end{frame}
 
 \begin{frame}
-	\frametitle{Beispiel}
-	Dummy.
-\end{frame}
-
-\begin{frame}
 	\frametitle{Verschachtelung}
 	
 	\begin{block}{Beobachtung}
@@ -636,8 +623,8 @@
 	\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);	
+	\draw[right edge] (4,7) .. controls(4, 3.5) .. (v);	
+	\draw[left edge] (4,7) .. controls(2, 7) .. (v);	
 	\end{tikzpicture}
 	\end{figure}		
 		\end{column}
@@ -657,17 +644,6 @@
 
 \begin{frame}
 	\frametitle{Algorithmus}
-	\begin{block}{Korollar}
-		Seien $b_1 = (u_1, v_1)$ und $b_2 = (u_2, v_2)$ \alert{zwei Rückwärtskanten} mit überlappenden Zyklen und sei $(u, v)$, $(v, w_1)$, $(v, w_2)$ ihre Gabelung. Dann gilt:
-		\begin{itemize}
-			\item $b_1$ und $b_2$ gehören zu \alert{verschiedenen} Klassen wenn $lowpt(w_2) < v_1$ und $lowpt(w_1) < v_2$
-			\item $b_1$ und $b_2$ gehören zur \alert{selben} Klasse wenn es eine Kante $e' = (x, y)$ gibt, sodass $x \in C(b_1) \cap C(b_2)$ und $y \not\in C(b_1) \cap C(b_2)$ und  $lowpt(y) < min\{v_1, v_2\}$
-		\end{itemize}
-	\end{block}
-\end{frame}
-
-\begin{frame}
-	\frametitle{Algorithmus}
 	
 	\begin{columns}[T]
 		\begin{column}{.33\textwidth}
@@ -739,6 +715,17 @@
 
 \begin{frame}
 	\frametitle{Algorithmus}
+	\begin{block}{Korollar}
+		Seien $b_1 = (u_1, v_1)$ und $b_2 = (u_2, v_2)$ \alert{zwei Rückwärtskanten} mit überlappenden Zyklen und sei $(u, v)$, $(v, w_1)$, $(v, w_2)$ ihre Gabelung. Dann gilt:
+		\begin{itemize}
+			\item $b_1$ und $b_2$ gehören zu \alert{verschiedenen} Klassen wenn $lowpt(w_2) < v_1$ und $lowpt(w_1) < v_2$
+			\item $b_1$ und $b_2$ gehören zur \alert{selben} Klasse wenn es eine Kante $e' = (x, y)$ gibt, sodass $x \in C(b_1) \cap C(b_2)$ und $y \not\in C(b_1) \cap C(b_2)$ und  $lowpt(y) < min\{v_1, v_2\}$
+		\end{itemize}
+	\end{block}
+\end{frame}
+
+\begin{frame}
+	\frametitle{Algorithmus}
 
 	\begin{itemize}
 		\item Die Bedingungen lassen sich in einem \alert{Constraint Graphen} darstellen
@@ -752,7 +739,7 @@
 \end{frame}
 
 \begin{frame}
-	\frametitle{FMR}
+	\frametitle{LR-Algorithmus}
 	
 	\begin{block}{Algorithmus}
 		\begin{itemize}
@@ -770,24 +757,16 @@
 	\end{itemize}
 \end{frame}
 
-\subsection{Knotenbasiert}
-\begin{frame}[plain]
-	\begin{center} \LARGE Knotenbasierte Algorithmen\end{center} 	
+\begin{frame}
+	\frametitle{Q \& A}
+
+	\begin{center} \LARGE Danke für die Aufmerksamkeit!\end{center} 	
+	\vspace{1em}	
+	\begin{center} \LARGE Fragen?\end{center} 	
 \end{frame}
 
 \begin{frame}
-	\frametitle{Idee}
-	\begin{itemize}
-		\item Ein Graph bleibt planar wenn man einzelne Knoten \alert{entfernt}
-		\vspace{1.5em}
-		\item Prozess kann \alert{umgekehrt} werden
-		\item Graph knotenweise vergrößern
-		\item Noch hinzuzufügender Graph muss zusammenhängend sein
-	\end{itemize}
-\end{frame}
-
-\begin{frame}
-	\frametitle{Praktische Eigenschaften}
+	\frametitle{Knotenbasierte Algorithmen}
 	\begin{itemize}
 		\item Es existiert immer eine \alert{Kette} von Planaren Graphen
 		\item Einmal \alert{geschlossene Facetten} bleiben geschlossen
@@ -816,15 +795,4 @@
 	\end{tikzpicture}
 	\end{figure}		
 \end{frame}
-
-\begin{frame}
-	\frametitle{Boyer-Myrvold}
-	\begin{itemize}
-		\item Kurz erklären?
-		\item Kleines Beispiel?
-		\item Weglassen?
-	\end{itemize}
-\end{frame}
-
-\section{Q\&A}
 \end{document}