LaTeX-examples/presentations/Diskrete-Mathematik/LaTeX/Koenigsberger-Brueckenproblem.tex

\subsection{Königsberger Brückenproblem}

\framedgraphic{Königsberg heute}{../images/koenigsberg-bruecken-luftbild}

\framedgraphic{Königsberger Brückenproblem}{../images/Konigsberg_bridges.png}

\framedgraphic{Übersetzung in einen Graphen}{../images/Konigsberg_bridges-graph.png}

\begin{frame}{Übersetzung in einen Graphen}
\begin{center}
\adjustbox{max size={\textwidth}{0.8\textheight}}{
\input{koenigsberg/koenigsberg-1}
}
\end{center}
\end{frame}

\begin{frame}{Eulerscher Kreis}
\begin{block}{Eulerscher Kreis}
Sei $G$ ein Graph und $A$ ein Kreis in $G$.

$A$ heißt \textbf{eulerscher Kreis} $:\Leftrightarrow \forall_{k \in K}: k \in A$.
\end{block}

\begin{block}{Eulerscher Graph}
Ein Graph heißt \textbf{eulersch}, wenn er einen eulerschen Kreis enthält.
\end{block}
\end{frame}

\begin{frame}{Hamiltonkreis}
ACHTUNG, VERWECHSLUNGSGEFAHR:

\begin{block}{Hamiltonkreis}
Sei $G$ ein Graph und $A$ ein Kreis in $G$.

$A$ heißt \textbf{Hamilton-Kreis} $:\Leftrightarrow \forall_{e \in E}: e \in A$.
\end{block}

\begin{block}{Eulerscher Kreis}
Sei $G$ ein Graph und $A$ ein Kreis in $G$.

$A$ heißt \textbf{eulerscher Kreis} $:\Leftrightarrow \forall_{k \in K}: k \in A$.
\end{block}
\end{frame}

\pgfdeclarelayer{background}
\pgfsetlayers{background,main}
\begin{frame}{Eulerscher Kreis}
    \newcommand\n{5}
    \begin{center}
    \adjustbox{max size={\textwidth}{0.8\textheight}}{
    \begin{tikzpicture}
        \foreach \number in {1,...,\n}{
            \node[vertex] (N-\number) at ({\number*(360/\n)}:5.4cm) {};
        }

        \foreach \number in {1,...,\n}{
            \foreach \y in {1,...,\n}{
                \draw (N-\number) -- (N-\y);
            }
        }

        \node<2->[vertex,red] (N-1) at ({1*(360/\n)}:5.4cm) {};

        \begin{pgfonlayer}{background}
            \path<2->[selected edge] (N-1.center) edge node {} (N-2.center);
            \path<3->[selected edge] (N-2.center) edge node {} (N-3.center);
            \path<4->[selected edge] (N-3.center) edge node {} (N-4.center);
            \path<5->[selected edge] (N-4.center) edge node {} (N-5.center);
            \path<6->[selected edge] (N-5.center) edge node {} (N-1.center);
            \path<7->[selected edge] (N-1.center) edge node {} (N-3.center);
            \path<8->[selected edge] (N-3.center) edge node {} (N-5.center);
            \path<9->[selected edge] (N-5.center) edge node {} (N-2.center);
            \path<10->[selected edge] (N-2.center) edge node {} (N-4.center);
            \path<11->[selected edge](N-4.center) edge node {} (N-1.center);
        \end{pgfonlayer}
    \end{tikzpicture}
    }
    \end{center}
\end{frame}

\pgfdeclarelayer{background}
\pgfsetlayers{background,main}
\begin{frame}{Hamilton-Kreis, kein EK}
    \begin{center}
    \adjustbox{max size={\textwidth}{0.8\textheight}}{
      \begin{tikzpicture}
          \node (a)[vertex] at (0,0) {};
          \node (b)[vertex] at (2,0) {};
          \node (c)[vertex] at (2,2) {};
          \node (d)[vertex] at (0,2) {};

          \foreach \from/\to in {a/b,b/c,c/d,d/a,a/c,b/d}
            \draw[line width=2pt] (\from) -- (\to);

        \node<2->[vertex,red] (a) at (0,0) {};
        \node<3->[vertex,red] (b) at (2,0) {};
        \node<4->[vertex,red] (c) at (2,2) {};
        \node<5->[vertex,red] (d) at (0,2) {};
        \begin{pgfonlayer}{background}
            \path<3->[selected edge,black!50] (a.center) edge node {} (b.center);
            \path<4->[selected edge,black!50] (b.center) edge node {} (c.center);
            \path<5->[selected edge,black!50] (c.center) edge node {} (d.center);
            \path<6->[selected edge,black!50] (d.center) edge node {} (a.center);
        \end{pgfonlayer}
      \end{tikzpicture}
    }
    \end{center}
\end{frame}

\pgfdeclarelayer{background}
\pgfsetlayers{background,main}
\begin{frame}{Eulerkreis, kein HK}
    \begin{center}
    \adjustbox{max size={\textwidth}{0.8\textheight}}{
      \begin{tikzpicture}
          \node (a)[vertex] at (0,0) {};
          \node (b)[vertex] at (2,0) {};
          \node (c)[vertex] at (2,2) {};
          \node (d)[vertex] at (0,2) {};
          \node (e)[vertex] at (1,1) {};

          \foreach \from/\to in {a/b,b/c,c/d,d/a,b/e,e/d}
            \draw[line width=2pt] (\from) -- (\to);
          \draw[line width=2pt] (b) to[bend right] (d);
      \end{tikzpicture}
    }
    \end{center}
\end{frame}

\subsection{Satz von Euler}
\begin{frame}{Satz von Euler}
\begin{block}{Satz von Euler}
Wenn ein Graph $G$ eulersch ist, dann hat jede Ecke von $G$ geraden Grad.
\end{block}

\pause

$\Rightarrow$ Wenn $G$ eine Ecke mit ungeraden Grad hat, ist $G$ nicht eulersch.

\pause

\begin{gallery}
    \galleryimage{vollstaendig/k-5}
    \galleryimage{koenigsberg/koenigsberg-1}
\end{gallery}
\end{frame}

\begin{frame}{Beweis: Satz von Euler}
\textbf{Beh.:} $G$ ist eulersch $\Rightarrow \forall e \in E: $ Grad($e$) $\equiv 0 \mod 2$ \pause \\
\textbf{Bew.:} Eulerkreis geht durch jede Ecke $e \in E$\pause,  \\
also geht der Eulerkreis (eventuell mehrfach) in $e$ hinein und hinaus \pause \\
$\Rightarrow$ Grad($e$) $\equiv 0 \mod 2$
\end{frame}

\begin{frame}{Umkehrung des Satzes von Euler}
\begin{block}{Umkehrung des Satzes von Euler}
Wenn in einem zusammenhängenden Graphen $G$ jede Ecke geraden Grad hat, dann 
ist $G$ eulersch.
\end{block}
\pause
\underline{Beweis:} Induktion über Anzahl $m$ der Kanten\\
\pause
\underline{I.A.:} $m=0$: $G$ ist eulersch. \cmark\\
\pause
$m=1$: Es gibt keinen Graphen in dem jede Ecke geraden Grad hat. \cmark\\
\pause
$m=2$: Nur ein Graph möglich. Dieser ist eulersch. \cmark\\ % Anzeichnen
\pause

\underline{I.V.:} Sei $m \in \mathbb{N}_0$ beliebig, aber fest und 
es gelte: Für 
alle zusammenhängenden Graphen $G$ mit höchstens $m$ Kanten, bei 
denen jede Ecke geraden Grad hat, ist $G$ eulersch.

\pause

\underline{I.S.:} Sei $G=(E,K)$ mit $2 \leq m  = |K|$. $G$ ist zus. \pause
$\Rightarrow$ Jede Ecke von $G$ hat min. Grad 2. \pause
$\xRightarrow[]{A. 5}$ Es gibt einen Kreis $C$ in $G$.\pause

\dots

\end{frame}

\begin{frame}{Umkehrung des Satzes von Euler}
\begin{block}{Umkehrung des Satzes von Euler}
Wenn in einem zusammenhängenden Graphen $G$ jede Ecke geraden Grad hat, dann 
ist $G$ eulersch.
\end{block}
\dots

Sei
\[G_C = (E_C, K_C) \]
Graph zu Kreis $C$ und

\[G^* = (E, K \setminus K_C).\] \pause
$\Rightarrow$ Alle Knoten jeder Zusammenhangskomponente in $G^*$ haben geraden Grad\\
\pause
$\xRightarrow[]{IV}$ Alle $n$ Zhsgk. haben Eulerkreise $C_1, \dots, C_n$\\
\pause
$\Rightarrow$ $C_1, \dots, C_n$ können in $C$ \enquote{eingehängt} werden\\
\pause
$\Rightarrow G$ ist eulersch\pause $\Rightarrow $ Beh.
\end{frame}

\begin{frame}{Offene eulersche Linie}
\begin{block}{Offene eulersche Linie}
Sei $G$ ein Graph und $A$ ein Weg, der kein Kreis ist.

$A$ heißt \textbf{offene eulersche Linie} von $G :\Leftrightarrow$ Jede Kante 
in $G$ kommt genau ein mal in $A$ vor.
\end{block}

Ein Graph kann genau dann "`in einem Zug"' gezeichnet werden, wenn er eine 
offene eulersche Linie besitzt.
\end{frame}

\begin{frame}{Offene eulersche Linie}
\begin{block}{Satz 8.2.3}
Sei $G$ ein zusammenhängender Graph.

$G$ hat eine offene eulersche Linie $:\Leftrightarrow G$ hat genau zwei Ecken 
ungeraden Grades.
\end{block}

\pause

\begin{block}{Beweis "`$\Rightarrow"'$}
Sei $G=(E, K)$ ein zusammenhängender Graph und $L = (e_0, \dots, e_s)$ eine offene
eulersche Linie. \pause
Sei $G^* = (E, K \cup \Set{e_s, e_0})$. \pause
Es gibt einen Eulerkreis in $G^*$ \pause \\
$\xLeftrightarrow{\text{Satz von Euler}}$ In $G^*$ hat jede Ecke geraden Grad \pause \\
Der Grad von nur zwei Kanten wurde um jeweils 1 erhöht \pause \\
$\Leftrightarrow$ in $G$ haben genau 2 Ecken ungeraden Grad. Diese heißen $e_0, e_s$. $\blacksquare$
\end{block}

\pause
Rückrichtung analog
\end{frame}

\pgfdeclarelayer{background}
\pgfsetlayers{background,main}
\begin{frame}{Haus des Nikolaus}
    \tikzstyle{selected edge} = [draw,line width=5pt,-,red!50]
    \begin{center}
    \adjustbox{max size={\textwidth}{0.8\textheight}}{
    \begin{tikzpicture}
        \node[vertex] (a) at (0,0) {};
        \node[vertex] (b) at (2,0) {};
        \node[vertex] (c) at (2,2) {};
        \node[vertex] (d) at (0,2) {};
        \node[vertex] (e) at (1,4) {};

        \draw (a) -- (d);
        \draw (d) -- (b);
        \draw (b) -- (c);
        \draw (c) -- (d);
        \draw (d) -- (e);
        \draw (e) -- (c);
        \draw (c) -- (a);
        \draw (a) -- (b);

        \node<2->[vertex, red] (a) at (0,0) {};

        \begin{pgfonlayer}{background}
            \path<2->[selected edge] (a.center) edge node {} (d.center);
            \path<3->[selected edge] (d.center) edge node {} (b.center);
            \path<4->[selected edge] (b.center) edge node {} (c.center);
            \path<5->[selected edge] (c.center) edge node {} (d.center);
            \path<6->[selected edge] (d.center) edge node {} (e.center);
            \path<7->[selected edge] (e.center) edge node {} (c.center);
            \path<8->[selected edge] (c.center) edge node {} (a.center);
            \path<9->[selected edge] (a.center) edge node {} (b.center);
        \end{pgfonlayer}
    \end{tikzpicture}
    }
    \end{center}
\end{frame}