# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1390257178 -3600
# Node ID 7a8c748e3010b93772c0b18ae4980d3362767099
# Parent  d058663d28a8693d0ee3085e65f6f38ae72585ce
twelfth sheet and notes

diff -r d058663d28a8 -r 7a8c748e3010 ds13-12.pdf
Binary file ds13-12.pdf has changed
diff -r d058663d28a8 -r 7a8c748e3010 notes/complete_notes.pdf
Binary file notes/complete_notes.pdf has changed
diff -r d058663d28a8 -r 7a8c748e3010 notes/tex/complete_notes.tex
--- a/notes/tex/complete_notes.tex	Tue Jan 14 00:53:45 2014 +0100
+++ b/notes/tex/complete_notes.tex	Mon Jan 20 23:32:58 2014 +0100
@@ -65,4 +65,10 @@
 %ue11
 \showUnit{graphdefinition}
 \showUnit{pruefercode}
+
+%ue12
+\showUnit{gradfolgen}
+\showUnit{spannbaeume}
+\showUnit{eulertouren}
+\showUnit{gerichtetegraphen}
 \end{document}
diff -r d058663d28a8 -r 7a8c748e3010 notes/tex/graphs.tex
--- a/notes/tex/graphs.tex	Tue Jan 14 00:53:45 2014 +0100
+++ b/notes/tex/graphs.tex	Mon Jan 20 23:32:58 2014 +0100
@@ -337,3 +337,323 @@
     \end{block}
 \end{frame}
 }
+
+\defineUnit{gradfolgen}{%
+\begin{frame}
+    \frametitle{Gradfolge}
+
+    \begin{definition}[Gradfolge]
+        Sei $G=(V, E)$ ein ungerichteter einfacher Graph mit $\abs{V} = n$.\\
+        Seine \structure{Gradfolge} ist ein $n$-Tupel, das seine Grade enthält.
+        \begin{align}
+            \left( \deg(v_1), \deg(v_2), \dots, \deg(v_n) \right)
+        \end{align}
+        Üblicherweise werden Gradfolgen \alert{aufsteigend} sortiert.
+    \end{definition}
+
+    \vfill
+
+    \begin{example}[]
+        \vspace{.5em}
+        \begin{columns}[c]
+            \begin{column}{.45\textwidth}
+                \begin{itemize}
+                    \item $\abs{V} = 7$
+                    \item Gradfolge $\left( 1, 1, 1, 2, 2, 2, 3 \right)$
+                \end{itemize}
+            \end{column}
+            \begin{column}{.45\textwidth}
+                \centering
+                \begin{tikzpicture}[small]
+                    \tikzstyle{vertex} = [pretty]
+                    \tikzstyle{one} = [vertex, tumblue, fill=tumblue!20]
+                    \tikzstyle{two} = [vertex, tumred, fill=tumred!20]
+                    \tikzstyle{three} = [vertex, tumgreen, fill=tumgreen!30]
+                    \tikzstyle{edge} = [draw, thick, -]
+
+                    \draw (0, 0)
+                        +(0, 0) node[three] (v1) {$3$}
+                        +(1, 1) node[two] (v2) {$2$}
+                        +(2.5, 1) node[one] (v3) {$1$}
+                        +(0, -1) node[two] (v4) {$2$}
+                        +(1.5, 0) node[two] (v5) {$2$}
+                        (2.5, -1) node[one] (v6) {$1$}
+                        (3.5, 0) node[one] (v7) {$1$};
+
+                    \draw[edge]
+                        (v1) -- (v2)
+                        (v1) -- (v4)
+                        (v1) -- (v5)
+                        (v2) -- (v3)
+                        (v4) -- (v5)
+                        (v6) -- (v7);
+                \end{tikzpicture}
+            \end{column}
+        \end{columns}
+    \end{example}
+\end{frame}
+}
+
+\defineUnit{spannbaeume}{%
+\begin{frame}
+    \frametitle{Teilgraph}
+
+    \begin{definition}[Teilgraph]
+        Seien $G = (V, E)$ und $G^\prime = (V^\prime, E^\prime)$ Graphen.\\
+        Zu $G$ heißt $G^\prime$
+        \begin{description}[Induzierter Teilgraph]
+            \item[Teilgraph] wenn $V^\prime \subseteq V$ und $E^\prime \subseteq E$.
+            \item[Induzierter Teilgraph] wenn $V^\prime \subseteq V$ und $E^\prime = \binom{V^\prime}{2} \cap E$.
+        \end{description}
+    \end{definition}
+
+    \begin{itemize}
+        \item Der induzierte Teilgraph ist der zu einer Knotenmenge kantenmaximale Teilgraph.
+    \end{itemize}
+
+    \begin{example}[]
+        \vspace{.5em}
+        \begin{columns}[c]
+            \begin{column}{.45\textwidth}
+                \begin{itemize}
+                    \item Petersen-Graph $G$
+                    \item Induzierter Teilgraph \alert{$G^\prime$}
+                \end{itemize}
+            \end{column}
+            \begin{column}{.45\textwidth}
+                \centering
+                \begin{tikzpicture}[]
+                    \tikzstyle{vertex} = [pretty]
+                    \tikzstyle{blue} = []
+                    \tikzstyle{red} = [fill=tumred!20]
+
+                    \foreach \name/\angle/\dist/\col in {
+                        ia/18/0.8/red, ib/90/0.8/blue, ic/162/0.8/red, id/234/0.8/blue, ie/306/0.8/red,
+                        oa/18/1.6/red, ob/90/1.6/blue, oc/162/1.6/blue, od/234/1.6/blue, oe/306/1.6/red} {
+                        \node[vertex,\col] (\name) at (\angle:\dist) {};
+                    }
+
+                    \foreach \from/\to in {
+                        ic/ie, ia/ic,
+                        ie/oe, ia/oa, oe/oa} {
+                        \draw[line width=2pt, tumred!80] (\from) -- (\to);
+                    }
+
+                    \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}
+
+\begin{frame}
+    \frametitle{Spannbaum}
+
+    \begin{definition}[Spannbaum]
+        Ein Teilgraph $T^\prime = \left( V^\prime, E^\prime \right)$ heißt \structure{Spannbaum} von $G = \left( V, E \right)$ wenn $T^\prime$ ein \alert{Baum} ist und $\alert{\abs{V^\prime} = \abs{V}}$ gilt.
+    \end{definition}
+    \begin{itemize}
+        \item Spannbäume sind nicht eindeutig
+        \item Jeder zusammenhängende Graph hat mindestens einen Spannbaum
+    \end{itemize}
+
+    \vfill
+
+    \begin{example}[]
+        \vspace{.5em}
+        \centering
+        \begin{columns}[c]
+            \begin{column}{.45\textwidth}
+                \centering
+                \begin{tikzpicture}[]
+                    \tikzstyle{vertex} = [pretty]
+                    \tikzstyle{blue} = []
+                    \tikzstyle{red} = [fill=tumred!20]
+
+                    \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/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);
+                    }
+
+                    \foreach \from/\to in {
+                        ia/oa, ib/ob, ic/oc, id/od, ie/oe,
+                        od/oc, oa/oe, ie/ib, id/ib} {
+                        \draw[very thick, tumred] (\from) -- (\to);
+                    }
+                \end{tikzpicture}
+            \end{column}
+            \begin{column}{.45\textwidth}
+                \centering
+                \begin{tikzpicture}[]
+                    \tikzstyle{vertex} = [pretty]
+                    \tikzstyle{blue} = []
+                    \tikzstyle{red} = [fill=tumred!20]
+
+                    \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/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);
+                    }
+
+                    \foreach \from/\to in {
+                        ia/ic, ic/ie, ie/ib, ib/id, id/od,
+                        od/oc, oc/ob, ob/oa, oa/oe} {
+                        \draw[very thick, tumred] (\from) -- (\to);
+                    }
+                \end{tikzpicture}
+            \end{column}
+        \end{columns}
+    \end{example}
+\end{frame}
+}
+
+\defineUnit{eulertouren}{%
+\begin{frame}
+    \frametitle{Euler-Tour}
+
+    \begin{definition}[Euler-Tour]
+        Eine \structure{Euler-Tour} in einem Graphen ist ein Weg, der jede Kante \alert{genau einmal} enthält und dessen Anfangs- und Endknoten identisch sind.\\
+        Ein Graph, der eine Euler-Tour besitzt, heißt \structure{eulersch}.
+    \end{definition}
+
+    \begin{theorem}[Euler]
+        Ein zusammenhängender Graph besitzt genau dann eine \structure{Euler-Tour}, wenn alle Knoten des Graphen \alert{geraden Grad} haben.
+    \end{theorem}
+
+    \vfill
+
+    \begin{example}[]
+        \vspace{.5em}
+        \begin{columns}[c]
+            \begin{column}{.45\textwidth}
+                \begin{itemize}
+                    \item Eulertour
+                        \begin{align}
+                            ( &v_1, v_2, v_4, v_5, v_2, v_3,\\&v_4, v_1, v_6, v_3, v_1)
+                        \end{align}
+                \end{itemize}
+            \end{column}
+            \begin{column}{.45\textwidth}
+                \centering
+                \begin{tikzpicture}[small]
+                    \tikzstyle{vertex} = [pretty]
+                    % see http://tex.stackexchange.com/q/141378
+                    \tikzset{edge/.style={
+                            postaction={
+                                decorate,
+                                decoration={
+                                    markings,
+                                    mark=between positions 0 and \pgfdecoratedpathlength step 0.5pt with {
+                                        \pgfmathsetmacro\myval{multiply(divide(
+                                            \pgfkeysvalueof{/pgf/decoration/mark info/distance from start}, \pgfdecoratedpathlength),100)};
+                                        \pgfsetfillcolor{tumblue!\myval!tumgreen};
+                                        \pgfpathcircle{\pgfpointorigin}{.8pt};
+                                        \pgfusepath{fill};}
+                                }}}}
+
+                    \draw (0, 0)
+                        +(1, 1) node[vertex] (v1) {$v_1$}
+                        +(-1, 1) node[vertex] (v2) {$v_2$}
+                        +(1, -1) node[vertex] (v3) {$v_3$}
+                        +(-1, -1) node[vertex] (v4) {$v_4$}
+                        +(-2, 0) node[vertex] (v5) {$v_5$}
+                        +(2, 0) node[vertex] (v6) {$v_6$};
+
+                    \draw[edge]
+                        (v1) -- (v2) -- (v4) -- (v5) -- (v2) --
+                        (v3) -- (v4) -- (v1) -- (v6) -- (v3) --
+                        (v1);
+
+                    % Just draw the nodes again to fix the overlap
+                    \draw (0, 0)
+                        +(1, 1) node[vertex] (v1) {$v_1$}
+                        +(-1, 1) node[vertex] (v2) {$v_2$}
+                        +(1, -1) node[vertex] (v3) {$v_3$}
+                        +(-1, -1) node[vertex] (v4) {$v_4$}
+                        +(-2, 0) node[vertex] (v5) {$v_5$}
+                        +(2, 0) node[vertex] (v6) {$v_6$};
+                \end{tikzpicture}
+            \end{column}
+        \end{columns}
+    \end{example}
+\end{frame}
+}
+
+\defineUnit{gerichtetegraphen}{%
+\begin{frame}
+    \frametitle{Gerichteter Graph}
+
+    \begin{definition}[Gerichteter Graph]
+        Ein (einfacher) \structure{gerichteter Graph $G = (V, E)$} ist ein Zweitupel aus \structure{Knotenmenge $V$} und \structure{Kantenmenge $E \subseteq V \times V$}.\\
+        Dabei bezeichnet ein Tupel $(v_1, v_2) \in E$ eine Kante von $v_1$ nach $v_2$.
+    \end{definition}
+    \begin{itemize}
+        \item Schleifen sind erlaubt
+        \item Kanten in beide Richtungen sind erlaubt
+    \end{itemize}
+
+    \vfill
+
+    \begin{example}[]
+        \vspace{.5em}
+        \begin{columns}[c]
+            \begin{column}{.45\textwidth}
+                \begin{align}
+                    G &= (V, E) \\
+                    V &= \left\{ v_1, v_2, v_3, v_4, v_5, v_6, v_7 \right\} \\
+                    E &= \{ \left( 1, 1 \right), \left( 1, 2 \right), \left( 2, 3 \right),\\
+                        &\qquad\!\left( 2, 3 \right), \left( 3, 2 \right), \left( 1, 5 \right),\\
+                        &\qquad\!\left( 4, 1 \right), \left( 5, 4 \right), \left( 6, 7 \right),\\
+                        &\qquad\!\left( 7, 6 \right)\}
+                \end{align}
+            \end{column}
+            \begin{column}{.45\textwidth}
+                \begin{tikzpicture}[small]
+                    \tikzstyle{vertex} = [pretty]
+                    \tikzstyle{every edge} = [edge, thick]
+
+                    \draw (0, 0)
+                        +(0, 0) node[vertex] (v1) {$v_1$}
+                        +(1, 1) node[vertex] (v2) {$v_2$}
+                        +(2.5, 1) node[vertex] (v3) {$v_3$}
+                        +(0, -1) node[vertex] (v4) {$v_4$}
+                        +(1.5, 0) node[vertex] (v5) {$v_5$}
+                        (2.5, -1) node[vertex] (v6) {$v_6$}
+                        (3.5, 0) node[vertex] (v7) {$v_7$};
+
+                    \draw[]
+                        (v1) edge[loop left] (v1)
+                        (v1) edge (v2)
+                        (v2) edge[bend left] (v3)
+                        (v3) edge[bend left] (v2)
+                        (v1) edge (v5)
+                        (v4) edge (v1)
+                        (v5) edge (v4)
+                        (v6) edge[bend left] (v7)
+                        (v7) edge[bend left] (v6);
+                \end{tikzpicture}
+            \end{column}
+        \end{columns}
+    \end{example}
+\end{frame}
+}
diff -r d058663d28a8 -r 7a8c748e3010 notes/tex/preamble.tex
--- a/notes/tex/preamble.tex	Tue Jan 14 00:53:45 2014 +0100
+++ b/notes/tex/preamble.tex	Mon Jan 20 23:32:58 2014 +0100
@@ -25,6 +25,8 @@
 \usetikzlibrary{positioning}
 \usetikzlibrary{chains}
 \usetikzlibrary{fit}
+\usetikzlibrary{decorations}
+\usetikzlibrary{decorations.markings}
 
 \usepackage{amsmath}
 \usepackage{mathdots}
diff -r d058663d28a8 -r 7a8c748e3010 notes/tex/ue12_notes.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue12_notes.tex	Mon Jan 20 23:32:58 2014 +0100
@@ -0,0 +1,14 @@
+\input{preamble.tex}
+\input{frames.tex}
+
+\title{Übung 12: Mehr Graphentheorie}
+\subtitle{Diskrete Strukturen im Wintersemester 2013/2014}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+\showUnit{titel}
+\showUnit{gradfolgen}
+\showUnit{spannbaeume}
+\showUnit{eulertouren}
+\showUnit{gerichtetegraphen}
+\end{document}
diff -r d058663d28a8 -r 7a8c748e3010 notes/ue12_notes.pdf
Binary file notes/ue12_notes.pdf has changed