--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/bayesian_networks/term_paper.bib	Wed Feb 06 21:13:59 2013 +0100
@@ -0,0 +1,7 @@
+@unpublished{Bra09,
+    author =        {Ulrik Brandes},
+    title =     {The left-right planarity test},
+    year =      {2009},
+    note =      {Manuscript submitted for publication},
+    ee =        {http://www.inf.uni-konstanz.de/algo/publications/b-lrpt-sub.pdf}
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/bayesian_networks/term_paper.tex	Wed Feb 06 21:13:59 2013 +0100
@@ -0,0 +1,164 @@
+\documentclass[12pt,a4paper]{article}
+
+\usepackage[ngerman]{babel}
+\usepackage[T1]{fontenc}
+\usepackage[utf8]{inputenc}
+
+\usepackage{amsmath}
+\usepackage[thmmarks]{ntheorem}
+\usepackage[pdftex]{hyperref}
+\usepackage{tikz}
+\usepackage{subfig}
+\usepackage{wrapfig}
+\usepackage{url}
+\usepackage{tabu}
+
+\usepackage{parskip}
+\usepackage{graphicx}
+\usepackage[figure, vlined, german]{algorithm2e}
+\usepackage{todonotes}
+
+\usetikzlibrary{calc}
+\usetikzlibrary{shapes.geometric}
+\tikzstyle{edge} = [draw,very thick,->,>=latex]
+\tikzstyle{selected edge} = [edge, tumred]
+\tikzstyle{circular node} = [circle,thick,draw,fill=tumblue!20,minimum size=12pt,inner sep=0pt,font=\bfseries]
+\tikzstyle{net node} = [ellipse, draw, thick, fill=tumblue!20, minimum width=6em, minimum height=2.5em, node distance=10em, inner sep = 0]
+\tikzstyle{selected net node} = [net node, fill=tumred!20]
+\def \netvspace {7em}
+\tikzstyle{net cpt} = [draw, thick, fill = tumgreen!20, font=\scriptsize, node distance=3em, inner sep = 2pt]
+
+\xdefinecolor{tumblue}     {RGB}{0,101,189}
+\xdefinecolor{tumgreen}    {RGB}{162,173,0}
+\xdefinecolor{tumred}      {RGB}{229,52,24}
+\xdefinecolor{tumivory}    {RGB}{218,215,203}
+\xdefinecolor{tumorange}   {RGB}{227,114,34}
+\xdefinecolor{tumlightblue}{RGB}{152,198,234}
+
+\newtheorem{definition}{Definition}
+\newtheorem{lemma}[definition]{Lemma}
+\newtheorem{theorem}[definition]{Theorem}
+\newtheorem{proof}[definition]{Beweis}
+\newtheorem{observation}[definition]{Beobachtung}
+
+\newcommand{\N}       {\mathbb{N}}
+\newcommand{\Z}       {\mathbb{Z}}
+\newcommand{\R}       {\mathbb{R}}
+\newcommand{\Oh}      {\mathcal{O}}
+
+\sloppy
+
+
+\begin{document}
+\input{titlepage}
+
+\setcounter{tocdepth}{3}
+\setcounter{secnumdepth}{3}
+\tableofcontents
+
+\newpage
+
+
+\section{Planarität}
+Ein \emph{Graph} $G = (V, E)$ ist ein Tupel der endlichen \emph{Knotenmenge} $V$ und \emph{Kantenmenge} $E$ aus Paaren von Knoten $(u, v)$. Im Weiteren werden nur \emph{einfache} Graphen ohne Mehrfachkanten oder Schleifen, also Kanten mit selben Anfangs- und Endknoten betrachtet, da diese keinen Einfluss auf die Planarität eines Graphen haben. Außerdem bezeichnet $n = |V|$ und $m = |E|$.
+
+Eine \emph{Zeichnung} eines Graphen ordnet jedem Knoten Koordinaten auf einer Ebene und jeder Kante eine Kurve zwischen ihren Endknoten zu. Eine Zeichnung heißt \emph{planar} wenn sich keine Kanten schneiden. Zwei Zeichnungen heißen \emph{äquivalent}, wenn ihre Reihenfolge der Kanten um jeden Knoten gleich ist. Diese Äquivalenzklasse von Zeichnungen wird \emph{Einbettung} genannt und ist planar falls eine ihrer Zeichnungen planar ist.
+
+\begin{definition}
+Ein Graph heißt \emph{planar}, wenn für ihn eine planare Zeichnung existiert.
+\end{definition}
+
+Zeichnungen unterteilen die Ebene in \emph{Flächen} mit $f$ als der Anzahl der Flächen. Es existieren abgeschlossene \emph{innere} Flächen und genau eine offene \emph{äußere} Fläche. Der eulersche Polyedersatz stellt einen Zusammenhang her zwischen der Anzahl Knoten, Kanten und Flächen in einer planaren Zeichnung.
+
+\begin{theorem}[Eulerscher Polyersatz]
+Für zusammenhängende planare Graphen gilt in jeder Zeichnung $n - m + f = 2$
+\end{theorem}
+
+Daraus ergibt sich direkt ein Kriterium zur Planaritätsprüfung anhand der Kantenanzahl.
+
+\begin{lemma}
+Für jeden planaren Graphen gilt $m \leq 3n - 6$
+\end{lemma}
+\begin{proof}
+Jede Kante kann maximal zwei Flächen begrenzen. Außerdem wird eine Fläche von mindestens drei Kanten begrenzt. Daraus ergibt sich $f \leq \frac{2m}{3}$ und $m \leq 3n - 6$.
+\end{proof}
+Dieses Lemma stellt außerdem für planare Graphen einen linearen Zusammenhang zwischen Kanten und Knoten her, es gilt $m \in \Oh(n)$, während für allgemeine Graphen nur $m \in \Oh(n^2)$ gilt.
+
+\subsection{Die Sätze von Kuratowski und Wagner}
+In den 1930er Jahren haben Kuratowski\cite{Kur30} und Wagner\cite{Wag37} erste Charakterisierungen für planare Graphen gefunden. Diese Charakterisierungen basieren auf \emph{Unterteilungen} und \emph{Minoren}. Eine Unterteilung eines Graphen entsteht durch beliebig häufiges Einfügen von neuen Knoten auf vorhandenen Kanten. Ein Graph ist Minor eines anderen Graphen, wenn er sich durch Löschen von Knoten oder Kanten oder Kantenkontraktion gewinnen lässt.
+
+\begin{theorem}
+Ein Graph ist genau dann planar wenn er keinen Teilgraphen (\emph{Kuratowski}) enthält, der eine Unterteilung von $K_5$ oder $K_{3,3}$ ist und er nicht Minor (\emph{Wagner}) eines dieser Graphen ist.
+\end{theorem}
+
+\begin{figure}[h]
+    \centering
+    \begin{tikzpicture}
+        \node [net node] (schlange) {Schlange};
+        \node [net node] (mensa) at ($(schlange.center) + (-4em,\netvspace)$) {Mensa};
+        \node [net node] (schlafen) at ($(schlange.center) + (4em,\netvspace)$) {Schlafen};
+
+        \node [net node] (hotdog) at ($(schlange.center) - (0,\netvspace)$) {Hotdog};
+
+        \foreach \src/\dest in {mensa/schlange, schlafen/schlange,
+        schlange/hotdog}
+        \path [edge] (\src) -- (\dest);
+
+        \node [net cpt] at ($(schlafen.center)-(-3em,2.2em)$)
+        {$V \sim GV(0,100)$};
+
+        \node [net cpt] at ($(mensa.center)-(1em,3em)$)
+        {\begin{tabu}{c}
+            $\Pr[M]$ \\     \tabucline{-}
+            $0.4$ \\
+        \end{tabu}};
+
+        \node [net cpt] at ($(schlange.center)-(5em,3em)$)
+        {\begin{tabu}{c|c}
+            M & $S$ \\  \tabucline{-}
+            F & $S \sim N(\mu_t(v),\sigma_t)$ \\
+            T & $S \sim N(\mu_f(v),\sigma_f)$ \\
+        \end{tabu}};
+
+        \node [net cpt] at ($(hotdog.center)-(-1em,2.2em)$)
+        {$\Pr[h \mid S = s] = \Phi(\frac{-s + \mu}{\sigma})$};
+    \end{tikzpicture}
+    \caption{Echt hübsches Netz}
+    \label{fig:bn}
+\end{figure}
+
+$K_5$ und $K_{3,3}$ sind also die kleinstmöglichen nicht planaren Graphen. Dieses Kriterium ist einfach zu verstehen, würde aber bei direkter Anwendung zu mindestens exponentiellen Algorithmen führen und ist deswegen zum Testen auf Planarität ungeeignet.
+
+Wurst
+
+\begin{algorithm}
+    \KwData{this text}
+    \KwResult{how to write algorithm with \LaTeX2e }
+    initialization\;
+    \While{not at end of this document}{%
+        read current\;
+        \eIf{understand}{%
+            go to next section\;
+            current section becomes this one\;
+        }{%
+            go back to the beginning of current section\;
+        }
+    }
+    \caption{SOM-Lernalgorithmus}
+    \label{jayjay}
+\end{algorithm}
+
+Salat
+
+\subsection{Geschichte der Planaritätsprüfung}
+Während die Formulierung des Problems einfach ist und Kuratowski und Wagner in den dreißiger Jahren eine Charakterisierung für planare Graphen finden konnten, war längere Zeit kein effizienter Algorithmus zum Testen auf Planarität bekannt. Erst 1961 fanden Auslander und Parter\cite{AP61} einen Polynomialzeitalgorithmus basierend auf der Unterteilung von Kreisen. 1974 stellten Hopcroft und Tarjan\cite{HT74} einen ersten Linearzeitalgorithmus vor, der auf dem Betrachten einzelner Pfade im Graphen aufbaut. Diese Algorithmen verwenden jedoch meist komplexe Datenstrukturen und sind relativ schwer zu implementieren.
+
+Im Folgenden soll das \emph{LR-Planaritätskriterium} vorgestellt werden, das auf der Tiefensuche basiert und ursprünglich von de Fraysseix, Ossona de Mendez und Rosenstiehl 2006\cite{FMR06} veröffentlicht und 2009 von Brandes\cite{Bra09} näher beschrieben wurde.
+
+
+\newpage
+\addcontentsline{toc}{section}{Literatur}
+\bibliographystyle{alpha}
+\bibliography{term_paper}
+
+\end{document}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/bayesian_networks/titlepage.tex	Wed Feb 06 21:13:59 2013 +0100
@@ -0,0 +1,67 @@
+  \hoffset=5mm
+
+  \input{tumlogo}
+
+  \thispagestyle{empty}
+
+  \begin{center}
+
+    \bigskip \bigskip \bigskip
+    \textcolor{tumblue}{\oTUM{6.0cm}}\\
+    \vspace*{0.8cm}
+    {\huge \bf Technische Universit"at}\\
+    \bigskip
+    {\huge \bf M"unchen}\\
+    \bigskip \bigskip \bigskip
+    {\huge \bf Fakult"at f"ur Informatik}\\
+    \bigskip \bigskip
+    {\Large \bf Forschungs- und Lehreinheit Informatik VI}\\
+    \bigskip \bigskip \bigskip \bigskip \bigskip
+
+%
+%
+% TITEL DER ARBEIT
+%
+%
+    {\Large Bayesnetze}\\
+    \bigskip \bigskip \bigskip \bigskip \bigskip
+    {\Large Seminar Kognitive Robotik (WS12)}\\
+    \bigskip \bigskip \bigskip \bigskip
+
+%
+%
+% NAME DES STUDENTEN (auf Titelblatt)
+%
+%
+    {\Large \bf Markus Kaiser}
+
+  \end{center}
+
+  \vfill
+  \begin{tabular}{ll}
+
+%
+%
+% NAME DES BETREUERS
+%
+%
+    {\Large \bf Betreuer:} &
+    {\Large Alexander Perzylo}\\
+    \\
+
+
+    {\Large \bf Leitung:} &
+    {\Large Prof. Alois Knoll}\\
+    \\
+
+%
+%
+% ABGABETERMIN
+%
+%
+    {\Large \bf Abgabetermin:} &
+    {\Large 10. Februar 2013}
+
+  \end{tabular}
+  \cleardoublepage
+  \hoffset=0mm

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/bayesian_networks/tumlogo.tex	Wed Feb 06 21:13:59 2013 +0100
@@ -0,0 +1,61 @@
+% This is tumlogo.tex
+%
+% Neues TUM-Logo in TeX
+%   by G. Teege, 19.10.89
+% Benutzung:
+%   Am Anfang des Dokuments (TeX oder LaTeX):
+%     \input tumlogo
+%   Dann beliebig oft:
+%     \TUM{<breite>}
+%   bzw.
+%     \oTUM{<breite>}
+%   \TUM setzt das Logo mit der Breite <breite> und der entsprechenden Hoehe.
+%   <breite> muss eine <dimen> sein. \oTUM erzeugt eine "outline"-Version
+%   des Logos, d.h. weiss mit schwarzem Rand. Bei \TUM ist es ganz schwarz.
+%   \oTUM entspricht damit der offiziellen Version des Logos.
+%   Das Logo kann wie ein einzelnes Zeichen verwendet werden.
+%   Beispiel:
+%     Dies ist das TUM-Logo: \oTUM{1cm}.
+%
+\def\TUM#1{%
+\dimen1=#1\dimen1=.1143\dimen1%
+\dimen2=#1\dimen2=.419\dimen2%
+\dimen3=#1\dimen3=.0857\dimen3%
+\dimen4=\dimen1\advance\dimen4 by\dimen2%
+\setbox0=\vbox{\hrule width\dimen3 height\dimen1 depth0pt\vskip\dimen2}%
+\setbox1=\vbox{\hrule width\dimen1 height\dimen4 depth0pt}%
+\setbox2=\vbox{\hrule width\dimen3 height\dimen1 depth0pt}%
+\setbox3=\hbox{\copy0\copy1\copy0\copy1\box2\copy1\copy0\copy1\box0\box1}%
+\leavevmode\vbox{\box3}}
+%
+\def\oTUM#1{%
+\dimen1=#1\dimen1=.1143\dimen1%
+\dimen2=#1\dimen2=.419\dimen2%
+\dimen3=#1\dimen3=.0857\dimen3%
+\dimen0=#1\dimen0=.018\dimen0%
+\dimen4=\dimen1\advance\dimen4 by-\dimen0%
+\setbox1=\vbox{\hrule width\dimen0 height\dimen4 depth0pt}%
+\advance\dimen4 by\dimen2%
+\setbox8=\vbox{\hrule width\dimen0 height\dimen4 depth0pt}%
+\advance\dimen4 by-\dimen2\advance\dimen4 by-\dimen0%
+\setbox4=\vbox{\hrule width\dimen4 height\dimen0 depth0pt}%
+\advance\dimen4 by\dimen1\advance\dimen4 by\dimen3%
+\setbox6=\vbox{\hrule width\dimen4 height\dimen0 depth0pt}%
+\advance\dimen4 by\dimen3\advance\dimen4 by\dimen0%
+\setbox9=\vbox{\hrule width\dimen4 height\dimen0 depth0pt}%
+\advance\dimen4 by\dimen1%
+\setbox7=\vbox{\hrule width\dimen4 height\dimen0 depth0pt}%
+\dimen4=\dimen3%
+\setbox5=\vbox{\hrule width\dimen4 height\dimen0 depth0pt}%
+\advance\dimen4 by-\dimen0%
+\setbox2=\vbox{\hrule width\dimen4 height\dimen0 depth0pt}%
+\dimen4=\dimen2\advance\dimen4 by\dimen0%
+\setbox3=\vbox{\hrule width\dimen0 height\dimen4 depth0pt}%
+\setbox0=\vbox{\hbox{\box9\lower\dimen2\copy3\lower\dimen2\copy5%
+\lower\dimen2\copy3\box7}\kern-\dimen2\nointerlineskip%
+\hbox{\raise\dimen2\box1\raise\dimen2\box2\copy3\copy4\copy3%
+\raise\dimen2\copy5\copy3\box6\copy3\raise\dimen2\copy5\copy3\copy4\copy3%
+\raise\dimen2\box5\box3\box4\box8}}%
+\leavevmode\box0}
+% End of tumlogo.tex
+