Mercurial > 13ws.ds
changeset 52:6669987ffd32
thirteenth sheet and notes
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Tue, 28 Jan 2014 00:42:39 +0100 |
| parents | 7a8c748e3010 |
| children | a9b64faf4b8f |
| files | ds13-13.pdf notes/complete_notes.pdf notes/tex/complete_notes.tex notes/tex/graphs.tex notes/tex/preamble.tex notes/tex/ue13_notes.tex notes/ue13_notes.pdf |
| diffstat | 7 files changed, 336 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/notes/tex/complete_notes.tex Mon Jan 20 23:32:58 2014 +0100 +++ b/notes/tex/complete_notes.tex Tue Jan 28 00:42:39 2014 +0100 @@ -71,4 +71,8 @@ \showUnit{spannbaeume} \showUnit{eulertouren} \showUnit{gerichtetegraphen} + +%ue13 +\showUnit{graphfaerbung} +\showUnit{planaritaet} \end{document}
--- a/notes/tex/graphs.tex Mon Jan 20 23:32:58 2014 +0100 +++ b/notes/tex/graphs.tex Tue Jan 28 00:42:39 2014 +0100 @@ -657,3 +657,319 @@ \end{example} \end{frame} } + +\defineUnit{graphfaerbung}{% +\begin{frame} + \frametitle{Graphenfärbung} + + \begin{definition}[$k$-Färbbarkeit] + Ein Graph $G = (V, E)$ heißt \structure{$k$-färbbar}, wenn es eine Abbildung $f : V \to [k]$ gibt, sodass + \begin{align} + \forall v \in V\; \forall w \in \alert{\Gamma(v)}.\; f(v) \alert{\neq} f(w) + \end{align} + Die \structure{chromatische Zahl $\chi(G)$} ist das kleinste $k$, sodass $G$ $k$-färbbar ist. + \end{definition} + + \begin{itemize} + \item Ordne jedem Knoten eine Farbe zu + \item Benachbarte Knoten haben unterschiedliche Farben + \end{itemize} + + \vfill + + \begin{example}[] + \vspace{.5em} + \centering + \begin{columns}[c] + \begin{column}{.35\textwidth} + \begin{itemize} + \item $G$ ist 3-färbbar + \item $G$ ist auch 4-färbbar + \item $\chi(G) = 3$ + \end{itemize} + \end{column} + \begin{column}{.55\textwidth} + \centering + \begin{tikzpicture}[] + \tikzstyle{vertex} = [pretty] + \tikzstyle{blue} = [fill=tumblue] + \tikzstyle{red} = [fill=tumred] + \tikzstyle{green} = [fill=tumgreen] + + \foreach \name/\angle/\dist/\col in { + ia/18/0.8/red, ib/90/0.8/red, ic/162/0.8/blue, id/234/0.8/blue, ie/306/0.8/green, + oa/18/1.6/green, ob/90/1.6/blue, oc/162/1.6/red, od/234/1.6/green, oe/306/1.6/blue} { + \node<1>[vertex] (\name) at (\angle:\dist) {}; + \node<2>[vertex, \col] (\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); + } + \end{tikzpicture} + \end{column} + \end{columns} + \end{example} +\end{frame} +} + +\defineUnit{planaritaet}{% +\begin{frame} + \frametitle{Bipartitheit} + + \begin{definition}[Bipartiter Graph] + Ein Graph $G = (V, E)$ heißt \structure{bipartit} gdw.\ es eine Partitionierung $V = V_1 \uplus V_2$ gibt, sodass jede Kante zwei Knoten in \alert{unterschiedlichen Klassen} verbindet. + \begin{align} + \forall \left\{ v_1, v_2 \right\} \in E.\; v_1 \in V_1 \wedge v_2 \in V_2 + \end{align} + \end{definition} + + \begin{itemize} + \item $G$ ist bipartit gdw. $\chi(G)= 2$ + \end{itemize} + + \vfill + + \begin{example}[] + \vspace{.5em} + \begin{columns} + \begin{column}{.5\textwidth} + \centering + \begin{tikzpicture}[x=2em, y=2em] + \tikzstyle{set} = [rectangle, rounded corners, draw, fill, inner sep=5pt] + \tikzstyle{vertex} = [pretty] + + \draw (0, 0) + +(0, 0) node[vertex] (a1) {} + +(0, 2) node[vertex] (a2) {} + + (2, 0) + +(0, -1) node[vertex] (b1) {} + +(0, 1) node[vertex] (b2) {} + +(0, 3) node[vertex] (b3) {} + + (0, 0) + +(0, -2) node {$V_1$} + (2, 0) + +(0, -2) node {$V_2$}; + + \draw[thick] + (a1) -- (b1) + (a1) -- (b3) + (a2) -- (b2) + (a2) -- (b3); + + \begin{pgfonlayer}{background} + \node[set, tumblue, fill=tumblue!20, fit=(b1.south east) (b3.north west)] {}; + \node[set, tumred, fill=tumred!20, fit=(b1.south east) (b3.north west), shift={(-2, 0)}] {}; + \end{pgfonlayer} + \end{tikzpicture} + \end{column} + \begin{column}{.5\textwidth} + \centering + \begin{tikzpicture}[x=2em, y=2em] + \tikzstyle{set} = [rectangle, rounded corners, draw, fill, inner sep=5pt] + \tikzstyle{vertex} = [pretty] + + \draw (0, 0) + +(0, -1) node[vertex] (a1) {} + +(0, 1) node[vertex] (a2) {} + +(0, 3) node[vertex] (a3) {} + + (2, 0) + +(0, -1) node[vertex] (b1) {} + +(0, 1) node[vertex] (b2) {} + +(0, 3) node[vertex] (b3) {} + + (1, 0) + +(0, -2) node {$K_{3,3}$}; + + \draw[thick] + (a1) -- (b1) + (a1) -- (b2) + (a1) -- (b3) + (a2) -- (b1) + (a2) -- (b2) + (a2) -- (b3) + (a3) -- (b1) + (a3) -- (b2) + (a3) -- (b3); + + \begin{pgfonlayer}{background} + \node[set, tumblue, fill=tumblue!20, fit=(b1.south east) (b3.north west)] {}; + \node[set, tumred, fill=tumred!20, fit=(b1.south east) (b3.north west), shift={(-2, 0)}] {}; + \end{pgfonlayer} + \end{tikzpicture} + \end{column} + \end{columns} + \end{example} +\end{frame} + +\begin{frame} + \frametitle{Planarität} + + \begin{definition}[Planarität] + Ein Graph heißt \structure{planar}, wenn er so in eine Ebene gezeichnet werden kann, dass sich keine Kanten schneiden. + \end{definition} + + \begin{theorem}[Kuratowski] + Ein Graph ist genau dann \structure{nicht planar}, wenn er einen Teilgraphen enthält, der eine \alert{Unterteilung} des \alert{$K_5$} oder des \alert{$K_{3, 3}$} ist. + \end{theorem} + + \begin{example}[] + \begin{columns}[T] + \begin{column}{.5\textwidth} + \centering + Planar\\ + \vspace{1em} + \begin{tikzpicture}[] + \tikzstyle{edge} = [draw, thick, -] + \tikzstyle{vertex} = [pretty] + + \foreach \name/\angle/\dist in { + ia/18/0.6, ib/90/0.6, ic/162/0.6, id/234/0.6, ie/306/0.6, + oa/18/1.2, ob/90/1.2, oc/162/1.2, od/234/1.2, oe/306/1.2} { + \node[vertex] (\name) at (\angle:\dist) {}; + } + + \foreach \from/\to in { + ia/ib, ib/ic, ic/id, id/ie, ie/ia, + oa/ob, ob/oc, oc/od, od/oe, oe/oa, + ia/oa, ib/ob, ic/oc, id/od, ie/oe} { + \draw[edge] (\from) -- (\to); + } + \end{tikzpicture} + \vspace{.5em} + \end{column} + \begin{column}{.5\textwidth} + \centering + Nicht planar\\ + \vspace{1em} + \begin{tikzpicture} + \tikzstyle{edge} = [draw, thick, -] + \tikzstyle{vertex} = [pretty] + + \path[use as bounding box] + (0, 1) -- (4, 1) -- (4, -1.5) -- cycle; + + \draw (0, 0) + +(0, -1) node[vertex] (a1) {} + +(0, 0) node[vertex] (a2) {} + +(0, 1) node[vertex] (a3) {} + + (1, 0) + +(0, -1) node[vertex] (b1) {} + +(0, 0) node[vertex] (b2) {} + +(0, 1) node[vertex] (b3) {} + + (0.5, 0) + +(0, -1.5) node {$K_{3,3}$} + (3, 0) + +(0, -1.5) node {$K_{5}$}; + + \draw[thick] + (a1) -- (b1) + (a1) -- (b2) + (a1) -- (b3) + (a2) -- (b1) + (a2) -- (b2) + (a2) -- (b3) + (a3) -- (b1) + (a3) -- (b2) + (a3) -- (b3); + + \foreach \name/\angle/\dist in { + fa/18/.85, fb/90/.85, fc/162/.85, fd/234/.85, fe/306/.85} { + \draw + (3, 0) + +(\angle:\dist) node[vertex] (\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} + \vspace{.5em} + \end{column} + \end{columns} + \end{example} +\end{frame} + +\begin{frame} + \frametitle{Eulersche Polyederformel} + + \begin{theorem}[Eulersche Polyederformel] + Für einen zusammenhängenden planaren Graphen $G = (V, E)$ gilt + \begin{align} + \structure{\abs{F} - \abs{E} + \abs{V} - 2 = 0} + \end{align} + Dabei ist $\abs{F}$ die Anzahl von Flächen inklusive der äußeren Fläche. + \end{theorem} + + \vfill + + \begin{example}[] + \vspace{.5em} + \centering + \begin{columns}[c] + \begin{column}{.45\textwidth} + \centering + \begin{tikzpicture}[x=3em, y=3em, clip] + \tikzstyle{edge} = [draw, thick, -] + \tikzstyle{vertex} = [pretty, fill=tumblue!30] + + \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/ib, ib/ic, ic/id, id/ie, ie/ia, + oa/ob, ob/oc, oc/od, od/oe, oe/oa, + ia/oa, ib/ob, ic/oc, id/od, ie/oe} { + \draw[edge] (\from) -- (\to); + } + + \begin{pgfonlayer}{background} + \tikzstyle{area} = [draw, fill] + \tikzstyle{green} = [area, tumgreen, fill=tumgreen!60] + \tikzstyle{red} = [area, tumred, fill=tumred!60] + \tikzstyle{blue} = [area, tumblue, fill=tumblue!60] + \tikzstyle{ivory} = [area, tumivory, fill=tumivory!60] + + \node[blue, thick, dashed, fit=(oa)(ob)(oc)(od)(oe)] {}; + \path[green] + (ia.center) -- (ib.center) -- (ob.center) -- (oa.center) -- cycle + (ic.center) -- (id.center) -- (od.center) -- (oc.center) -- cycle; + + \path[red] + (ic.center) -- (ib.center) -- (ob.center) -- (oc.center) -- cycle + (ie.center) -- (id.center) -- (od.center) -- (oe.center) -- cycle; + + \path[ivory] + (ia.center) -- (ie.center) -- (oe.center) -- (oa.center) -- cycle; + + \path[blue] + (ia.center) -- (ib.center) -- (ic.center) -- (id.center) -- (ie.center) -- cycle; + \end{pgfonlayer} + \end{tikzpicture} + \end{column} + \begin{column}{.45\textwidth} + \begin{itemize} + \item $\abs{V} = 10$ + \item $\abs{E} = 15$ + \item $\abs{F} = 7$ + \end{itemize} + \end{column} + \end{columns} + \end{example} +\end{frame} +}
--- a/notes/tex/preamble.tex Mon Jan 20 23:32:58 2014 +0100 +++ b/notes/tex/preamble.tex Tue Jan 28 00:42:39 2014 +0100 @@ -71,3 +71,7 @@ \tikzstyle{every state} = [pretty] \tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] \tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE] + +\pgfdeclarelayer{background} +\pgfdeclarelayer{foreground} +\pgfsetlayers{background,main,foreground}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue13_notes.tex Tue Jan 28 00:42:39 2014 +0100 @@ -0,0 +1,12 @@ +\input{preamble.tex} +\input{frames.tex} + +\title{Übung 13: Graphfärbung \& Planarität} +\subtitle{Diskrete Strukturen im Wintersemester 2013/2014} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} + +\begin{document} +\showUnit{titel} +\showUnit{graphfaerbung} +\showUnit{planaritaet} +\end{document}