\defineUnit{graphdefinition}{%
\begin{frame}
    \frametitle{Graphen}

    \begin{definition}[Graph]
        Ein (einfacher, ungerichteter) \structure{Graph $G = (V, E)$} ist ein Zweitupel aus \structure{Knotenmenge $V$} und \structure{Kantenmenge $E \subseteq \binom{V}{2}$}.
    \end{definition}
    \begin{itemize}
        \item $\binom{V}{2}$ ist Notation für alle zweielementigen Teilmengen.
        \item V für \structure{Vertices}, E für \structure{Edges}
    \end{itemize}

    \vfill

    \begin{example}[]
        \vspace{.5em}
        \begin{columns}[c]
            \begin{column}{.50\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\{ v_1, v_2 \right\}, \left\{ v_1, v_4 \right\}, \\
                        &\qquad\!\left\{ v_1, v_5 \right\}, \left\{ v_2, v_3 \right\},\\
                        &\qquad\!\left\{ v_4, v_5 \right\}, \left\{ v_6, v_7 \right\} \}
                \end{align}
            \end{column}
            \begin{column}{.45\textwidth}
                \begin{tikzpicture}[small]
                    \tikzstyle{vertex} = [pretty]
                    \tikzstyle{edge} = [draw, 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[edge]
                        (v1) -- (v2)
                        (v1) -- (v4)
                        (v1) -- (v5)
                        (v2) -- (v3)
                        (v4) -- (v5)
                        (v6) -- (v7);
                \end{tikzpicture}
            \end{column}
        \end{columns}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Vollständige Graphen}

    \begin{definition}[Vollständiger Graph]
        Im \structure{vollständigen Graphen $K_n$} mit $n$ Knoten sind alle Knoten durch Kanten verbunden.\\
    \end{definition}
    \begin{itemize}
        \item Er enthält $\binom{n}{2} = \frac{n(n-1)}{2}$ Kanten.
    \end{itemize}

    \vfill

    \begin{example}[]
        \centering
        \begin{tikzpicture}
            \tikzstyle{edge} = [draw, thick, -]
            \def\dx{2.2}
            \def\ly{-.6}

            \draw
                (0, 0)
                +(0.5, 0) node[pretty] (ea) {}
                +(0.5, \ly) node {$K_1$}
                (\dx, 0)
                +(0.5, 0) node[pretty] (za) {}
                +(0.5, 1) node[pretty] (zb) {}
                +(0.5, \ly) node {$K_2$}
                ++(\dx, 0)
                +(0, 0) node[pretty] (da) {}
                +(1, 0) node[pretty] (db) {}
                +(0.5, 1) node[pretty] (dc) {}
                +(0.5, \ly) node {$K_3$}
                ++(\dx, 0)
                +(0, 0) node[pretty] (va) {}
                +(1, 0) node[pretty] (vb) {}
                +(0, 1) node[pretty] (vc) {}
                +(1, 1) node[pretty] (vd) {}
                +(0.5, \ly) node {$K_4$}
                ++(\dx, 0) node (k5) {}
                +(0.5, \ly) node {$K_5$};
            \draw[edge]
                (za) -- (zb)
                (da) -- (db) -- (dc) -- (da)
                (va) -- (vb) -- (vc) -- (vd) -- (va) -- (vc) (vb) -- (vd);

            \foreach \name/\angle/\dist in {
                fa/18/.85, fb/90/.85, fc/162/.85, fd/234/.85, fe/306/.85} {
                \draw
                (k5)
                ++(54:.85)
                +(\angle:\dist) node[pretty] (\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}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Wege, Pfade und Kreise}

    \begin{definition}[$k$-Weg]
        Ein \structure{$k$-Weg} in einem Graphen $G=(V,E)$ ist eine nichtleere Folge von Knoten $\structure{(v_0, \dots, v_k)} \in V^{k+1}$ von $k+1$ Knoten, sodass zwischen aufeinanderfolgenden Knoten Kanten existieren.
        \begin{align}
            \forall i \in \Z_k. \left\{ v_i, v_{i+1} \right\} \in E
        \end{align}
        $(v_0)$ bezeichnet einen $0$-Weg.
    \end{definition}

    \vfill

    \begin{definition}[$k$-Pfad]
        Ein \structure{$k$-Pfad} in $G$ ist ein $k$-Weg in $G$, in dem kein Knoten mehrfach vorkommt.
    \end{definition}

    \vfill

    \begin{definition}[$k$-Kreis]
        Ein \structure{$k$-Kreis} ($k \geq 3$) in $G$ ist ein $k$-Weg $(v_0, \ldots, v_k)$ in $G$, wobei $v_0, \dots, v_{k-1}$ paarweise verschieden sind und $v_0 = v_k$ gilt.
    \end{definition}
\end{frame}

\begin{frame}
    \frametitle{Nachbarschaft und Grad}

    Sei $G = (V, E)$ ein Graph und $v \in V$.
    \begin{definition}[Nachbarschaft]
        Die \structure{Nachbarschaft $\Gamma(v)$} eines Knotens $v$ ist die Menge aller Knoten, die mit $v$ über eine Kante verbunden sind.
        \begin{align}
            \Gamma(v) = \left\{ u \in V \mid \left\{ v, u \right\} \in E \right\}
        \end{align}
    \end{definition}

    \vfill

    \begin{definition}[Grad]
        Der \structure{Grad $\deg(v)$} bezeichnet die Anzahl der Nachbarn von $v$.
        \begin{align}
            \deg(v) = \abs{\Gamma(v)}
        \end{align}
        Aus $v$ führen genau $\deg(v)$ Kanten heraus.
    \end{definition}

    \vfill

    \begin{definition}[$k$-regulär]
        Haben alle Knoten in $G$ den Grad $k$, so nennen wir $G$ \structure{$k$-regulär}.
    \end{definition}
\end{frame}

\begin{frame}
    \frametitle{Erreichbarkeit und Zusammenhang}

    Sei $G = (V, E)$ ein Graph.
    \begin{definition}[Erreichbarkeit]
        Ein Knoten $u \in V$ ist von $v \in V$ \structure{erreichbar}, wenn es in $G$ einen Pfad von $u$ nach $v$ gibt.
    \end{definition}

    \begin{definition}[Zusammenhangskomponente]
        Eine \structure{Zusammenhangskomponente} ist eine \alert{maximale} Teilmenge von Knoten in der sich alle Knoten erreichen.\\
        $G$ heißt \structure{zusammenhängend}, wenn nur eine solche Komponente existiert.
    \end{definition}

    \begin{example}[]
        \vspace{.5em}
        \begin{columns}[c]
            \begin{column}{.50\textwidth}
                \begin{itemize}
                    \item $G$ hat zwei Komponenten
                        \begin{align}
                            &\alert{\left\{ v_1, v_2, v_3, v_4, v_5 \right\}},\\
                            &\structure{\left\{ v_6, v_7 \right\}}
                        \end{align}
                    \item $G$ ist nicht zusammenhängend
                \end{itemize}
            \end{column}
            \begin{column}{.45\textwidth}
                \begin{tikzpicture}[]
                    \tikzstyle{vertex} = [pretty]
                    \tikzstyle{edge} = [draw, thick, -]

                    % This is _really_ ugly!
                    \draw[thick, rounded corners, tumred, fill=tumred!20]
                        (-.5, 0) -- (0.9, 1.4) -- (2.9, 1.4) -- (2.9, 0.8) -- (0.7, -1.4) -- (-.5, -1.4) -- cycle;
                    \draw[thick, rounded corners, tumblue, fill=tumblue!20]
                        (2, -1.4) -- (2, -1) -- (3.2, 0.4) -- (3.9, 0.4) -- (3.9, -0.2) -- (2.9, -1.4) -- cycle;

                    \draw[small]
                        (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[edge]
                        (v1) -- (v2)
                        (v1) -- (v4)
                        (v1) -- (v5)
                        (v2) -- (v3)
                        (v4) -- (v5)
                        (v6) -- (v7);

                \end{tikzpicture}
            \end{column}
        \end{columns}
    \end{example}
\end{frame}

\begin{frame}
    \frametitle{Baum}

    \begin{definition}[Baum]
        Ein ungerichteter Graph heißt \structure{Baum}, falls er zusammenhängend und kreisfrei ist.
    \end{definition}
    \begin{definition}[Wald]
        Ein ungerichteter Graph heißt \structure{Wald}, wenn seine Zusammenhangskomponenten Bäume sind.
    \end{definition}
    \begin{itemize}
        \item Wir nennen Knoten von Grad 1 \structure{Blätter}
        \item Alle anderen Knoten heißen \structure{innere Knoten}
    \end{itemize}

    \vfill

    \begin{example}[]
        \centering
        \begin{tikzpicture}[]
            \tikzstyle{every node} = [pretty];

            \draw
                (4, 0)
                +(0, 0) node (a) {}
                +(0, -1) node (b) {}
                +(0, 1) node (c) {}
                +(-1, 0) node (d) {}
                +(1, 0) node (e) {}
                (6, -0.5)
                +(0, 0) node (f) {}
                +(1, 1) node (g) {}
                +(2, 1) node (h) {}
                +(1, 0) node (i) {}
                +(2, 0) node (j) {}
                +(3, 1) node (k) {}
                (0, 0)
                +(0, 0) node (l) {}
                (1, 0)
                +(0, 0) node (m) {}
                +(1, 0) node (n) {};

            \draw[thick]
                (a) -- (b)
                (a) -- (c)
                (a) -- (d)
                (a) -- (e)
                (f) -- (g)
                (g) -- (h)
                (g) -- (i)
                (h) -- (j)
                (h) -- (k)
                (m) -- (n);
        \end{tikzpicture}
    \end{example}
\end{frame}
}

\defineUnit{pruefercode}{%
\begin{frame}[c]
    \frametitle{Prüfercode}

    \begin{block}{Prüfercode}
        Der \structure{Prüfer-Code} zu einem Baum $T = (V, E)$ mit Knotenmenge $V = [n]$ ist ein $(n-2)$-Tupel mit Elementen aus $V$.\\
        Es gilt
        \begin{itemize}
            \item Jedem Baum kann genau ein Prüfer-Code zugeordnet werden
            \item Jeder Prüfer-Code stellt genau einen Baum dar
        \end{itemize}
        Damit wird eine Bijektion zwischen Tupeln und Bäumen definiert.
    \end{block}

    \begin{theorem}[Satz von Cayley]
        Es gibt genau $n^{n-2}$ Bäume mit n Knoten.
    \end{theorem}
\end{frame}

\renewcommand{\algorithmiccomment}[1]{\hfill \structure{##1}}
\begin{frame}
    \frametitle{Prüfercode}

    \begin{block}{Baum $\to$ Code}
        Gegeben ein Baum $T = (V, E)$ mit $\abs{V} = n$, finde Code $(c_1, \dots, c_{n-2})$.
        \vspace{.5em}
        \begin{algorithmic}
            \For{$i \gets 1, n-2 $}
                \State $m \gets \min \left\{ v \in V \mid v \text{ ist Blatt} \right\}$ \Comment{Finde kleinstes Blatt}
                \State $V \gets V \setminus \left\{ m \right\}$ \Comment{Entferne es aus $T$}
                \State $c_i \gets \text{parent}(m)$ \Comment{Addiere seinen Vater zum Code}
            \EndFor
        \end{algorithmic}
    \end{block}

    \begin{block}{Code $\to$ Baum}
        Gegeben ein Code $(c_1, \dots, c_{n-2})$, finde Baum $T = (V, E)$.
        \vspace{.5em}
        \begin{algorithmic}
            \State $V \gets [n]$ \Comment{$n$ Knoten}
            \State $E \gets \emptyset$ \Comment{Keine Kanten}
            \State $M \gets \emptyset$ \Comment{Keine markierten Knoten}
            \For{$i \gets 1, n-2$}
                \State $X_i \gets \left\{ c_i, \dots, c_{n-2} \right\} \cup M$ \Comment{Finde unmögliche Knoten}
                \State $v_i \gets \min \left( [n] \setminus X_i \right)$ \Comment{Finde kleinsten möglichen Knoten}
                \State $E \gets E \cup \left\{ \left\{ c_i, v_i \right\} \right\}$ \Comment{Füge Kante $\left\{ c_i, v_i \right\}$ hinzu}
                \State $M \gets M \cup \left\{ v_i \right\}$ \Comment{Markiere $v_i$}
            \EndFor
            \State $E \gets E \cup \left( V \setminus M \right)$ \Comment{Verbinde die 2 unmarkierten Knoten}
        \end{algorithmic}
    \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}
}

\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}
}