Mercurial > 13ws.ds
view notes/tex/graphs.tex @ 51:7a8c748e3010
twelfth sheet and notes
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Mon, 20 Jan 2014 23:32:58 +0100 |
parents | d058663d28a8 |
children | 6669987ffd32 |
line wrap: on
line source
\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} }