# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1390866159 -3600
# Node ID 6669987ffd3251e1d6c324120b41a29bcedef998
# Parent  7a8c748e3010b93772c0b18ae4980d3362767099
thirteenth sheet and notes

diff -r 7a8c748e3010 -r 6669987ffd32 ds13-13.pdf
Binary file ds13-13.pdf has changed
diff -r 7a8c748e3010 -r 6669987ffd32 notes/complete_notes.pdf
Binary file notes/complete_notes.pdf has changed
diff -r 7a8c748e3010 -r 6669987ffd32 notes/tex/complete_notes.tex
--- a/notes/tex/complete_notes.tex	Mon Jan 20 23:32:58 2014 +0100
+++ b/notes/tex/complete_notes.tex	Tue Jan 28 00:42:39 2014 +0100
@@ -71,4 +71,8 @@
 \showUnit{spannbaeume}
 \showUnit{eulertouren}
 \showUnit{gerichtetegraphen}
+
+%ue13
+\showUnit{graphfaerbung}
+\showUnit{planaritaet}
 \end{document}
diff -r 7a8c748e3010 -r 6669987ffd32 notes/tex/graphs.tex
--- a/notes/tex/graphs.tex	Mon Jan 20 23:32:58 2014 +0100
+++ b/notes/tex/graphs.tex	Tue Jan 28 00:42:39 2014 +0100
@@ -657,3 +657,319 @@
     \end{example}
 \end{frame}
 }
+
+\defineUnit{graphfaerbung}{%
+\begin{frame}
+    \frametitle{Graphenfärbung}
+
+    \begin{definition}[$k$-Färbbarkeit]
+        Ein Graph $G = (V, E)$ heißt \structure{$k$-färbbar}, wenn es eine Abbildung $f : V \to [k]$ gibt, sodass
+        \begin{align}
+            \forall v \in V\; \forall w \in \alert{\Gamma(v)}.\; f(v) \alert{\neq} f(w)
+        \end{align}
+        Die \structure{chromatische Zahl $\chi(G)$} ist das kleinste $k$, sodass $G$ $k$-färbbar ist.
+    \end{definition}
+
+    \begin{itemize}
+        \item Ordne jedem Knoten eine Farbe zu
+        \item Benachbarte Knoten haben unterschiedliche Farben
+    \end{itemize}
+
+    \vfill
+
+    \begin{example}[]
+        \vspace{.5em}
+        \centering
+        \begin{columns}[c]
+            \begin{column}{.35\textwidth}
+                \begin{itemize}
+                    \item $G$ ist 3-färbbar
+                    \item $G$ ist auch 4-färbbar
+                    \item $\chi(G) = 3$
+                \end{itemize}
+            \end{column}
+            \begin{column}{.55\textwidth}
+                \centering
+                \begin{tikzpicture}[]
+                    \tikzstyle{vertex} = [pretty]
+                    \tikzstyle{blue} = [fill=tumblue]
+                    \tikzstyle{red} = [fill=tumred]
+                    \tikzstyle{green} = [fill=tumgreen]
+
+                    \foreach \name/\angle/\dist/\col in {
+                        ia/18/0.8/red, ib/90/0.8/red, ic/162/0.8/blue, id/234/0.8/blue, ie/306/0.8/green,
+                        oa/18/1.6/green, ob/90/1.6/blue, oc/162/1.6/red, od/234/1.6/green, oe/306/1.6/blue} {
+                        \node<1>[vertex] (\name) at (\angle:\dist) {};
+                        \node<2>[vertex, \col] (\name) at (\angle:\dist) {};
+                    }
+
+                    \foreach \from/\to in {
+                        ia/oa, ib/ob, ic/oc, id/od, ie/oe,
+                        oa/ob, ob/oc, oc/od, od/oe, oe/oa,
+                        ia/ic, ic/ie, ie/ib, ib/id, id/ia} {
+                        \draw[thick] (\from) -- (\to);
+                    }
+                \end{tikzpicture}
+            \end{column}
+        \end{columns}
+    \end{example}
+\end{frame}
+}
+
+\defineUnit{planaritaet}{%
+\begin{frame}
+    \frametitle{Bipartitheit}
+
+    \begin{definition}[Bipartiter Graph]
+        Ein Graph $G = (V, E)$ heißt \structure{bipartit} gdw.\ es eine Partitionierung $V = V_1 \uplus V_2$ gibt, sodass jede Kante zwei Knoten in \alert{unterschiedlichen Klassen} verbindet.
+        \begin{align}
+            \forall \left\{ v_1, v_2 \right\} \in E.\; v_1 \in V_1 \wedge v_2 \in V_2
+        \end{align}
+    \end{definition}
+
+    \begin{itemize}
+        \item $G$ ist bipartit gdw. $\chi(G)= 2$
+    \end{itemize}
+
+    \vfill
+
+    \begin{example}[]
+        \vspace{.5em}
+        \begin{columns}
+            \begin{column}{.5\textwidth}
+                \centering
+                \begin{tikzpicture}[x=2em, y=2em]
+                    \tikzstyle{set} = [rectangle, rounded corners, draw, fill, inner sep=5pt]
+                    \tikzstyle{vertex} = [pretty]
+
+                    \draw (0, 0)
+                    +(0, 0) node[vertex] (a1) {}
+                    +(0, 2) node[vertex] (a2) {}
+
+                    (2, 0)
+                    +(0, -1) node[vertex] (b1) {}
+                    +(0, 1) node[vertex] (b2) {}
+                    +(0, 3) node[vertex] (b3) {}
+
+                    (0, 0)
+                    +(0, -2) node {$V_1$}
+                    (2, 0)
+                    +(0, -2) node {$V_2$};
+
+                    \draw[thick]
+                        (a1) -- (b1)
+                        (a1) -- (b3)
+                        (a2) -- (b2)
+                        (a2) -- (b3);
+
+                    \begin{pgfonlayer}{background}
+                        \node[set, tumblue, fill=tumblue!20, fit=(b1.south east) (b3.north west)] {};
+                        \node[set, tumred, fill=tumred!20, fit=(b1.south east) (b3.north west), shift={(-2, 0)}] {};
+                    \end{pgfonlayer}
+                \end{tikzpicture}
+            \end{column}
+            \begin{column}{.5\textwidth}
+                \centering
+                \begin{tikzpicture}[x=2em, y=2em]
+                    \tikzstyle{set} = [rectangle, rounded corners, draw, fill, inner sep=5pt]
+                    \tikzstyle{vertex} = [pretty]
+
+                    \draw (0, 0)
+                    +(0, -1) node[vertex] (a1) {}
+                    +(0, 1) node[vertex] (a2) {}
+                    +(0, 3) node[vertex] (a3) {}
+
+                    (2, 0)
+                    +(0, -1) node[vertex] (b1) {}
+                    +(0, 1) node[vertex] (b2) {}
+                    +(0, 3) node[vertex] (b3) {}
+
+                    (1, 0)
+                    +(0, -2) node {$K_{3,3}$};
+
+                    \draw[thick]
+                        (a1) -- (b1)
+                        (a1) -- (b2)
+                        (a1) -- (b3)
+                        (a2) -- (b1)
+                        (a2) -- (b2)
+                        (a2) -- (b3)
+                        (a3) -- (b1)
+                        (a3) -- (b2)
+                        (a3) -- (b3);
+
+                    \begin{pgfonlayer}{background}
+                        \node[set, tumblue, fill=tumblue!20, fit=(b1.south east) (b3.north west)] {};
+                        \node[set, tumred, fill=tumred!20, fit=(b1.south east) (b3.north west), shift={(-2, 0)}] {};
+                    \end{pgfonlayer}
+                \end{tikzpicture}
+            \end{column}
+        \end{columns}
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Planarität}
+
+    \begin{definition}[Planarität]
+        Ein Graph heißt \structure{planar}, wenn er so in eine Ebene gezeichnet werden kann, dass sich keine Kanten schneiden.
+    \end{definition}
+
+    \begin{theorem}[Kuratowski]
+        Ein Graph ist genau dann \structure{nicht planar}, wenn er einen Teilgraphen enthält, der eine \alert{Unterteilung} des \alert{$K_5$} oder des \alert{$K_{3, 3}$} ist.
+    \end{theorem}
+
+    \begin{example}[]
+        \begin{columns}[T]
+            \begin{column}{.5\textwidth}
+                \centering
+                Planar\\
+                \vspace{1em}
+                \begin{tikzpicture}[]
+                    \tikzstyle{edge} = [draw, thick, -]
+                    \tikzstyle{vertex} = [pretty]
+
+                    \foreach \name/\angle/\dist in {
+                        ia/18/0.6, ib/90/0.6, ic/162/0.6, id/234/0.6, ie/306/0.6,
+                        oa/18/1.2, ob/90/1.2, oc/162/1.2, od/234/1.2, oe/306/1.2} {
+                        \node[vertex] (\name) at (\angle:\dist) {};
+                    }
+
+                    \foreach \from/\to in {
+                        ia/ib, ib/ic, ic/id, id/ie, ie/ia,
+                        oa/ob, ob/oc, oc/od, od/oe, oe/oa,
+                        ia/oa, ib/ob, ic/oc, id/od, ie/oe} {
+                        \draw[edge] (\from) -- (\to);
+                    }
+                \end{tikzpicture}
+                \vspace{.5em}
+            \end{column}
+            \begin{column}{.5\textwidth}
+                \centering
+                Nicht planar\\
+                \vspace{1em}
+                \begin{tikzpicture}
+                    \tikzstyle{edge} = [draw, thick, -]
+                    \tikzstyle{vertex} = [pretty]
+
+                    \path[use as bounding box]
+                        (0, 1) -- (4, 1) -- (4, -1.5) -- cycle;
+
+                    \draw (0, 0)
+                    +(0, -1) node[vertex] (a1) {}
+                    +(0, 0) node[vertex] (a2) {}
+                    +(0, 1) node[vertex] (a3) {}
+
+                    (1, 0)
+                    +(0, -1) node[vertex] (b1) {}
+                    +(0, 0) node[vertex] (b2) {}
+                    +(0, 1) node[vertex] (b3) {}
+
+                    (0.5, 0)
+                    +(0, -1.5) node {$K_{3,3}$}
+                    (3, 0)
+                    +(0, -1.5) node {$K_{5}$};
+
+                    \draw[thick]
+                        (a1) -- (b1)
+                        (a1) -- (b2)
+                        (a1) -- (b3)
+                        (a2) -- (b1)
+                        (a2) -- (b2)
+                        (a2) -- (b3)
+                        (a3) -- (b1)
+                        (a3) -- (b2)
+                        (a3) -- (b3);
+
+                    \foreach \name/\angle/\dist in {
+                        fa/18/.85, fb/90/.85, fc/162/.85, fd/234/.85, fe/306/.85} {
+                        \draw
+                        (3, 0)
+                        +(\angle:\dist) node[vertex] (\name) {};
+                    }
+
+                    \foreach \a/\b in {
+                        fa/fb, fa/fc, fa/fd, fa/fe,
+                        fb/fc, fb/fd, fb/fe,
+                        fc/fd, fc/fe,
+                        fd/fe} {
+                        \draw[edge] (\a) -- (\b);
+                    }
+                \end{tikzpicture}
+                \vspace{.5em}
+            \end{column}
+        \end{columns}
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Eulersche Polyederformel}
+
+    \begin{theorem}[Eulersche Polyederformel]
+        Für einen zusammenhängenden planaren Graphen $G = (V, E)$ gilt
+        \begin{align}
+            \structure{\abs{F} - \abs{E} + \abs{V} - 2 = 0}
+        \end{align}
+        Dabei ist $\abs{F}$ die Anzahl von Flächen inklusive der äußeren Fläche.
+    \end{theorem}
+
+    \vfill
+
+    \begin{example}[]
+        \vspace{.5em}
+        \centering
+        \begin{columns}[c]
+            \begin{column}{.45\textwidth}
+                \centering
+                \begin{tikzpicture}[x=3em, y=3em, clip]
+                    \tikzstyle{edge} = [draw, thick, -]
+                    \tikzstyle{vertex} = [pretty, fill=tumblue!30]
+
+                    \foreach \name/\angle/\dist in {
+                        ia/18/0.8, ib/90/0.8, ic/162/0.8, id/234/0.8, ie/306/0.8,
+                        oa/18/1.6, ob/90/1.6, oc/162/1.6, od/234/1.6, oe/306/1.6} {
+                        \node[vertex] (\name) at (\angle:\dist) {};
+                    }
+
+                    \foreach \from/\to in {
+                        ia/ib, ib/ic, ic/id, id/ie, ie/ia,
+                        oa/ob, ob/oc, oc/od, od/oe, oe/oa,
+                        ia/oa, ib/ob, ic/oc, id/od, ie/oe} {
+                        \draw[edge] (\from) -- (\to);
+                    }
+
+                    \begin{pgfonlayer}{background}
+                        \tikzstyle{area} = [draw, fill]
+                        \tikzstyle{green} = [area, tumgreen, fill=tumgreen!60]
+                        \tikzstyle{red} = [area, tumred, fill=tumred!60]
+                        \tikzstyle{blue} = [area, tumblue, fill=tumblue!60]
+                        \tikzstyle{ivory} = [area, tumivory, fill=tumivory!60]
+
+                        \node[blue, thick, dashed, fit=(oa)(ob)(oc)(od)(oe)] {};
+                        \path[green]
+                        (ia.center) -- (ib.center) -- (ob.center) -- (oa.center) -- cycle
+                        (ic.center) -- (id.center) -- (od.center) -- (oc.center) -- cycle;
+
+                        \path[red]
+                        (ic.center) -- (ib.center) -- (ob.center) -- (oc.center) -- cycle
+                        (ie.center) -- (id.center) -- (od.center) -- (oe.center) -- cycle;
+
+                        \path[ivory]
+                        (ia.center) -- (ie.center) -- (oe.center) -- (oa.center) -- cycle;
+
+                        \path[blue]
+                        (ia.center) -- (ib.center) -- (ic.center) -- (id.center) -- (ie.center) -- cycle;
+                    \end{pgfonlayer}
+                \end{tikzpicture}
+            \end{column}
+            \begin{column}{.45\textwidth}
+                \begin{itemize}
+                    \item $\abs{V} = 10$
+                    \item $\abs{E} = 15$
+                    \item $\abs{F} = 7$
+                \end{itemize}
+            \end{column}
+        \end{columns}
+    \end{example}
+\end{frame}
+}
diff -r 7a8c748e3010 -r 6669987ffd32 notes/tex/preamble.tex
--- a/notes/tex/preamble.tex	Mon Jan 20 23:32:58 2014 +0100
+++ b/notes/tex/preamble.tex	Tue Jan 28 00:42:39 2014 +0100
@@ -71,3 +71,7 @@
 \tikzstyle{every state} = [pretty]
 \tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
 \tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE]
+
+\pgfdeclarelayer{background}
+\pgfdeclarelayer{foreground}
+\pgfsetlayers{background,main,foreground}
diff -r 7a8c748e3010 -r 6669987ffd32 notes/tex/ue13_notes.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue13_notes.tex	Tue Jan 28 00:42:39 2014 +0100
@@ -0,0 +1,12 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 13: Graphfärbung \& Planarität}
+\subtitle{Diskrete Strukturen im Wintersemester 2013/2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{graphfaerbung}
+\showUnit{planaritaet}
+\end{document}
diff -r 7a8c748e3010 -r 6669987ffd32 notes/ue13_notes.pdf
Binary file notes/ue13_notes.pdf has changed