Mercurial > 13ws.ds
changeset 50:d058663d28a8
eleventh sheet and notes
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Tue, 14 Jan 2014 00:53:45 +0100 |
| parents | 76b3c3727653 |
| children | 7a8c748e3010 |
| files | ds13-11.pdf notes/tex/complete_notes.tex notes/tex/frames.tex notes/tex/graphs.tex notes/tex/ue11_notes.tex notes/ue11_notes.pdf |
| diffstat | 6 files changed, 356 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/notes/tex/complete_notes.tex Wed Jan 08 21:14:44 2014 +0100 +++ b/notes/tex/complete_notes.tex Tue Jan 14 00:53:45 2014 +0100 @@ -61,4 +61,8 @@ %ue10 \showUnit{inklusionexklusion} \showUnit{stirlingzahlen} + +%ue11 +\showUnit{graphdefinition} +\showUnit{pruefercode} \end{document}
--- a/notes/tex/frames.tex Wed Jan 08 21:14:44 2014 +0100 +++ b/notes/tex/frames.tex Tue Jan 14 00:53:45 2014 +0100 @@ -12,3 +12,4 @@ \input{logic.tex} \input{growth.tex} \input{combinatorics.tex} +\input{graphs.tex}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/graphs.tex Tue Jan 14 00:53:45 2014 +0100 @@ -0,0 +1,339 @@ +\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} +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue11_notes.tex Tue Jan 14 00:53:45 2014 +0100 @@ -0,0 +1,12 @@ +\input{preamble.tex} +\input{frames.tex} + +\title{Übung 11: Graphen \& Bäume} +\subtitle{Diskrete Strukturen im Wintersemester 2013/2014} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} + +\begin{document} +\showUnit{titel} +\showUnit{graphdefinition} +\showUnit{pruefercode} +\end{document}