Strukturen.tex

\subsection{Strukturen in Graphen}
\begin{frame}{Kantenzug, Länge eines Kantenzuges und Verbindung von Ecken}
\begin{block}{Kantenzug, Länge eines Kantenzuges und Verbindung von Ecken}
Sei $G = (E, K)$ ein Graph.

Dann heißt eine Folge $k_1, k_2, \dots, k_s$ von Kanten, zu denen es Ecken
$e_0, e_1, e_2, \dots, e_s$ gibt, so dass
\begin{itemize}
    \item $k_1 = \Set{e_0, e_1}$
    \item $k_2 = \Set{e_1, e_2}$
    \item \dots
    \item $k_s = \Set{e_{s-1}, e_s}$
\end{itemize}
gilt ein \textbf{Kantenzug}, der \textcolor{purple}{$e_0$} und \textcolor{blue}{$e_s$} \textbf{verbindet} und $s$
seine \textbf{Länge}.
\end{block}

\adjustbox{max size={\textwidth}{0.2\textheight}}{
\begin{tikzpicture}
  \node (a)[vertex] at (1,1) {};
  \node (b)[vertex] at (2,5) {};
  \node (c)[vertex] at (3,3) {};
  \node (d)[vertex] at (5,4) {};
  \node (e)[vertex] at (3,6) {};
  \node (f)[vertex] at (5,6) {};
  \node (g)[vertex] at (7,6) {};
  \node (h)[vertex] at (7,4) {};
  \node (i)[vertex] at (6,2) {};
  \node (j)[vertex] at (8,7) {};
  \node (k)[vertex] at (9,5) {};
  \node (l)[vertex] at (13,6) {};
  \node (m)[vertex] at (11,7) {};
  \node (n)[vertex] at (15,7) {};
  \node (o)[vertex] at (16,4) {};
  \node (p)[vertex] at (10,2) {};
  \node (q)[vertex] at (13,1) {};
  \node (r)[vertex] at (16,1) {};
  \node (s)[vertex] at (17,4) {};
  \node (t)[vertex] at (19,6) {};
  \node (u)[vertex] at (18,3) {};
  \node (v)[vertex] at (20,2) {};
  \node (w)[vertex] at (15,4) {};

  \foreach \from/\to in {a/c,c/b,c/d,d/f,f/g,g/h,h/d,d/g,h/f,i/k,k/j,k/l,l/m,m/n,n/o,o/t,t/v,v/u,s/r,o/q,q/p,u/t}
    \draw[line width=2pt] (\from) -- (\to);

  \node (i)[vertex,purple] at (6,2) {};
  \node (v)[vertex,blue] at (20,2) {};
    \draw[line width=4pt, red] (i) -- (k) -- (l) -- (m) -- (n) -- (o) -- (t) -- (v);
\end{tikzpicture}
}
\end{frame}

\begin{frame}{Geschlossener Kantenzug}
\begin{block}{Geschlossener Kantenzug}
Sei $G = (E, K)$ ein Graph und $A = (k_1, k_2, \dots, k_s)$ ein Kantenzug
mit $k_1 = \Set{e_0, e_1}$ und $k_s = \Set{e_{s-1}, e_s}$.

A heißt \textbf{geschlossen} $:\Leftrightarrow e_0 = e_s$ .
\end{block}

Ein Kantenzug wird durch den Tupel $(e_0, \dots, e_s) \in E^{s+1}$
charakterisiert.

\begin{gallery}
    \galleryimage{walks/k-16-walk}
    \galleryimage{walks/star-graph-walk}
    \galleryimage{walks/tree-walk}
    \galleryimage{walks/walk-6}
\end{gallery}
\end{frame}

\begin{frame}{Weg}
\begin{block}{Weg}
Sei $G = (E, K)$ ein Graph und $A = (k_1, k_2 \dots, k_s)$ ein Kantenzug.

A heißt \textbf{Weg} $:\Leftrightarrow \forall_{i, j \in 1, \dots, s}: i \neq j \Rightarrow k_i \neq k_j$ .
\end{block}

\pause

\begin{exampleblock}{Salopp}
Ein Kantenzug, bei dem man keine Kante mehrfach abläuft, ist ein Weg.
\end{exampleblock}

\pause

Achtung: Knoten dürfen mehrfach abgelaufen werden!
\end{frame}

\begin{frame}{Kreis}
\begin{block}{Kreis}
Sei $G = (E, K)$ ein Graph und $A = (k_1, k_2 \dots, k_s)$ ein Kantenzug.

A heißt \textbf{Kreis} $:\Leftrightarrow A$ ist geschlossen und ein Weg.
\end{block}

\pause

Manchmal wird das auch "`einfacher Kreis"' genannt.

\pause

\begin{gallery}
    \galleryimage[Green]{graphs/circle-one-facet}
    \galleryimage[Green]{graphs/circle-two-facets}
\end{gallery}
\end{frame}

\begin{frame}{Aufgabe 5}
\begin{block}{Zeigen Sie: }
Wenn in einem Graphen $G=(E,K)$ jede Ecke min. Grad 2 hat, dann
besitzt $G$ einen Kreis einer Länge $>0$.
\end{block}

\pause

Sei $e_0 \in E$ eine beliebige Ecke aus $G$. Da $e_0$ min. Grad 2 hat,
gibt es eine Kante $k_0$.

\pause

Diese verbindet $e_0$ mit einer weiteren Ecke $e_1$, die wiederum
min. Grad 2 hat usw.

\pause

$G$ hat endlich viele Ecken. Man erreicht also irgendwann eine
Ecke $e_j$, die bereits als $e_i$ durchlaufen wurde. Die Ecken
$e_i, \dots, e_j = e_i$ bilden also eine Kreis $\blacksquare$
\end{frame}

\begin{frame}{Zusammenhängender Graph}
\begin{block}{Zusammenhängender Graph}
Sei $G = (E, K)$ ein Graph.

$G$ heißt \textbf{zusammenhängend} $:\Leftrightarrow \forall e_1, e_2 \in E: $
Es ex. ein Kantenzug, der $e_1$ und $e_2$ verbindet
\end{block}

\begin{gallery}
    \galleryimage[red]{graphs/graph-1}
    \galleryimage[red]{graphs/graph-2}
    \galleryimage[Green]{graphs/k-3-3}
    \galleryimage[Green]{graphs/k-5}\\
    \galleryimage[Green]{graphs/k-16}
    \galleryimage[Green]{graphs/graph-6}
    \galleryimage[Green]{graphs/star-graph}
    \galleryimage[Green]{graphs/tree}
\end{gallery}
\end{frame}