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