CoCalc -- Ende.tex

📚 The CoCalc Library - books, templates and other resources
cocalc-examples / martinthoma-latex-examples / presentations / Diskrete-Mathematik / LaTeX / Ende.tex
¹³²⁹³⁰ views
License: OTHER
1
\subsection{Aufgabe 3}
2
\begin{frame}{Aufgabe 3}
3
Zeigen Sie: Wenn der Graph eines Kreises bipartit ist, dann hat der Kreis gerade Länge.
4
\end{frame}
5

6
\pgfdeclarelayer{background}
7
\pgfsetlayers{background,main}
8
\begin{frame}{Aufgabe 3 - Lösung}
9
Idee: Knoten abwechselnd färben
10

11
    \tikzstyle{selected edge} = [draw,line width=5pt,-,black!50]
12
    \begin{center}
13
    \adjustbox{max size={\textwidth}{0.8\textheight}}{
14
    \begin{tikzpicture}
15
        \node[vertex] (a) at (0,0) {};
16
        \node[vertex] (b) at (2,0) {};
17
        \node[vertex] (c) at (2,2) {};
18
        \node[vertex] (d) at (0,2) {};
19
        \node[vertex] (e) at (1,4) {};
20

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

23
        \node<2->[vertex, red] (a) at (0,0) {};
24
        \node<3->[vertex, blue] (b) at (2,0) {};
25
        \node<4->[vertex, red] (c) at (2,2) {};
26
        \node<5->[vertex, blue] (e) at (1,4) {};
27
        \node<6->[vertex, red] (d) at (0,2) {};
28

29
        \begin{pgfonlayer}{background}
30
            \path<3->[selected edge] (a.center) edge node {} (b.center);
31
            \path<4->[selected edge] (b.center) edge node {} (c.center);
32
            \path<5->[selected edge] (c.center) edge node {} (e.center);
33
            \path<6->[selected edge] (e.center) edge node {} (d.center);
34
            \path<7->[selected edge,lime] (d.center) edge node {} (a.center);
35
        \end{pgfonlayer}
36
    \end{tikzpicture}
37
    }
38
    \end{center}
39
\end{frame}
40

41
\subsection{Aufgabe 4}
42
\begin{frame}{Aufgabe 4}
43
Zeigen Sie: Ein Graph $G$ ist genau dann bipartit, wenn er nur Kreise
44
gerade Länge hat.
45
\end{frame}
46

47
\begin{frame}{Aufgabe 4: Lösung, Teil 1}
48
\underline{Vor.:} Sei $G = (E, K)$ ein zus. Graph. \pause
49

50
\underline{Beh.:} $G$ ist bipartit $\Rightarrow G$ hat keine Kreis ungerader Länge \pause
51

52
\underline{Bew.:} durch Widerspruch \pause
53

54
\underline{Annahme:} $G$ hat Kreis ungerader Länge \pause
55

56
$\xRightarrow[]{A.4}$ Ein Subgraph von $G$ ist nicht bipartit \pause
57

58
$\Rightarrow$ Widerspruch zu \enquote{$G$ ist bipartit} \pause
59

60
$\Rightarrow$ $G$ hat keinen Kreis ungerader Länge $\blacksquare$
61
\end{frame}
62

63
\begin{frame}{Aufgabe 4: Lösung, Teil 2}
64
\underline{Vor.:} Sei $G = (E, K)$ ein zus. Graph. \pause
65

66
\underline{Beh.:} $G$ hat keinen Kreis ungerader Länge $\Rightarrow G$ ist bipartit \pause
67

68
\underline{Bew.:} Konstruktiv \pause
69

70
Färbe Graphen mit Breitensuche $\blacksquare$
71
\end{frame}
72

73
\pgfdeclarelayer{background}
74
\pgfsetlayers{background,main}
75
\begin{frame}{Aufgabe 4 - Beispiel}
76
    \tikzstyle{selected edge} = [draw,line width=5pt,-,black!50]
77
    \begin{center}
78
    \adjustbox{max size={\textwidth}{0.8\textheight}}{
79
    \begin{tikzpicture}
80
        \node[vertex] (a) at (1,1) {};
81
        \node[vertex] (b) at (2,0) {};
82
        \node[vertex] (c) at (4,0) {};
83
        \node[vertex] (d) at (1,2) {};
84
        \node[vertex] (e) at (2,2) {};
85
        \node[vertex] (f) at (3,2) {};
86
        \node[vertex] (g) at (2,4) {};
87
        \node[vertex] (h) at (3,3) {};
88
        \node[vertex] (i) at (4,2) {};
89
        \node[vertex] (j) at (1,3) {};
90

91
        \draw (a) -- (b);
92
        \draw (a) -- (d);
93
        \draw (b) -- (e);
94
        \draw (b) -- (c);
95
        \draw (c) -- (f);
96
        \draw (d) -- (e);
97
        \draw (d) -- (j);
98
        \draw (e) -- (f);
99
        \draw (f) -- (i);
100
        \draw (g) -- (j);
101
        \draw (g) -- (h);
102

103
        \node<2->[vertex, red]  (a) at (1,1) {};
104
        \node<3->[vertex, blue] (b) at (2,0) {};
105
        \node<3->[vertex, blue] (d) at (1,2) {};
106
        \node<4->[vertex, red]  (c) at (4,0) {};
107
        \node<4->[vertex, red]  (e) at (2,2) {};
108
        \node<4->[vertex, red]  (j) at (1,3) {};
109
        \node<5->[vertex, blue] (f) at (3,2) {};
110
        \node<5->[vertex, blue] (g) at (2,4) {};
111
        \node<6->[vertex, red]  (h) at (3,3) {};
112
        \node<6->[vertex, red]  (i) at (4,2) {};
113

114
        \begin{pgfonlayer}{background}
115
            \path<3->[selected edge] (a.center) edge node {} (b.center);
116
            \path<3->[selected edge] (a.center) edge node {} (d.center);
117
            \path<4->[selected edge] (b.center) edge node {} (c.center);
118
            \path<4->[selected edge] (b.center) edge node {} (e.center);
119
            \path<4->[selected edge] (d.center) edge node {} (j.center);
120
            \path<4->[selected edge] (d.center) edge node {} (e.center);
121
            \path<5->[selected edge] (j.center) edge node {} (g.center);
122
            \path<5->[selected edge] (e.center) edge node {} (f.center);
123
            \path<5->[selected edge] (c.center) edge node {} (f.center);
124
            \path<6->[selected edge] (g.center) edge node {} (h.center);
125
            \path<6->[selected edge] (f.center) edge node {} (i.center);
126
        \end{pgfonlayer}
127
    \end{tikzpicture}
128
    }
129
    \end{center}
130
\end{frame}
131

132
\subsection{Aufgabe 9}
133
\begin{frame}{Aufgabe 9, Teil 1}
134
Im folgenden sind die ersten drei Graphen $G_1, G_2, G_3$ einer
135
Folge $(G_n)$ aus Graphen abgebildet. Wie sieht $G_4$ aus?
136

137
\begin{gallery}
138
    \galleryimage{graphs/triangular-1}
139
    \galleryimage{graphs/triangular-2}
140
    \galleryimage{graphs/triangular-3}
141
\end{gallery}
142
\end{frame}
143

144
\begin{frame}{Aufgabe 9, Teil 1 (Lösung)}
145
    \begin{center}
146
        \input{graphs/triangular-4}
147
    \end{center}
148
\end{frame}
149

150
\begin{frame}{Aufgabe 9, Teil 1 (Lösung)}
151
    \begin{center}
152
        \input{graphs/triangular-5}
153
    \end{center}
154
\end{frame}
155

156
\begin{frame}{Aufgabe 9, Teil 1 (Lösung)}
157
    \begin{center}
158
        \input{graphs/triangular-6}
159
    \end{center}
160
\end{frame}
161

162
\begin{frame}{Aufgabe 9, Teil 2}
163
Wie viele Ecken und wie viele Kanten hat $G_i$?
164

165
\begin{gallery}
166
    \galleryimage{graphs/triangular-1}
167
    \galleryimage{graphs/triangular-2}
168
    \galleryimage{graphs/triangular-3}
169
\end{gallery}
170
\end{frame}
171

172
\begin{frame}{Aufgabe 9, Teil 2: Antwort}
173
Ecken:
174

175
\[|E_n| = |E_{n-1}| + (n+1) = \sum_{i=1}^{n+1} i = \frac{n^2 + 2n+2}{2}\]
176

177
Kanten:
178

179
\begin{align}
180
|K_n| &= |K_{n-1}| + \underbrace{((n+1)-1)+2}_{\text{außen}} + (n-1) \cdot 2\\
181
    &= |K_{n-1}| + n+2+2n-2\\
182
    &= |K_{n-1}| + 3n\\
183
    &= \sum_{i=1}^{n} 3i = 3 \sum_{i=1}^{n} i \\
184
    &= 3 \frac{n^2 + n}{2}
185
\end{align}
186
\end{frame}
187

188
\begin{frame}{Aufgabe 9, Teil 3}
189
Gebe $G_i$ formal an.
190

191
\begin{gallery}
192
    \galleryimage{graphs/triangular-1}
193
    \galleryimage{graphs/triangular-2}
194
    \galleryimage{graphs/triangular-3}
195
\end{gallery}
196
\end{frame}
197

198
\begin{frame}{Aufgabe 9, Teil 3 (Lösung)}
199
Gebe $G_n$ formal an.
200

201
\begin{gallery}
202
    \galleryimage{graphs/triangular-1}
203
    \galleryimage{graphs/triangular-2}
204
    \galleryimage{graphs/triangular-3}
205
\end{gallery}
206

207
\begin{align*}
208
    E_n &= \Set{e_{x,y} | y \in 1, \dots, n;\; x \in y, \dots, 2 \cdot n - y \text{ mit } x-y \equiv 0 \mod 2}\\
209
    K_n &= \Set{\Set{e_{x,y}, e_{i,j}} \in E_n^2 | (x+2=i \land y=j) \lor (x+1=i \land y\pm1=j)}\\
210
    G_n &= (E_n, K_n)
211
\end{align*}
212

213
\end{frame}
214

215
\begin{frame}{{\sc RectangleFreeColoring}}
216
    \begin{block}{{\sc RectangleFreeColoring}}
217
        Gegeben ist $n, m \in \mathbb{N}_{\geq 1}$ und ein
218
        ungerichteter Graph $G = (E, K)$ mit
219
            \[E = \Set{e_{x,y} | 1 \leq x \leq n \land 1 \leq y \leq m}\]
220
        und
221
            \[K = \Set{k=\Set{e_{x,y}, e_{x',y'}} \in E \times E : |x-x'| + |y-y'| = 1} \]
222

223
        Färbe die Ecken von $G$ mit einer minimalen Anzahl von Farben so, dass gilt:
224
		\begin{align*}
225
			\forall e_{x,y}, e_{x',y'} \in E: (x \neq x' \land y \neq y') \Rightarrow\\
226
			\neg \left (c(e_{x,y}) = c(e_{x',y'}) = c(e_{x',y}) = c(e_{x,y'}) \right )
227
		\end{align*}
228
    \end{block}
229
\end{frame}
230

231
\begin{frame}{{\sc RectangleFreeColoring}}
232
    $4 \times 4$ - Instanz:\\
233

234
    \vspace{1cm}
235
    \begin{tikzpicture}
236
        \newcommand{\n}{4}
237
        \newcommand{\m}{4}
238
        \foreach \x in {1, ..., \n}{
239
            \foreach \y in {1, ..., \m}{
240
                \node[vertex] (n-\x-\y) at (\x,\y) {};
241
            }
242
        }
243

244
        \foreach \x in {1, ..., \n}{
245
            \foreach \y in {1, ..., \m}{
246
                \ifthenelse{\x<\n}{\draw (\x,\y) -- (\x+1,\y);}{}
247
            }
248
        }
249
        \foreach \y in {1, ..., \m}{
250
            \foreach \x in {1, ..., \n}{
251
                \ifthenelse{\y<\m}{\draw (\x,\y) -- (\x,\y+1);}{}
252
            }
253
        }
254

255
        \node[vertex,blue] (n-1-1) at (1,1) {};
256
        \node[vertex,blue] (n-2-1) at (2,1) {};
257
        \node[vertex,blue] (n-3-1) at (3,1) {};
258
        \node[vertex,red]  (n-4-1) at (4,1) {};
259

260
        \node[vertex,blue] (n-1-1) at (1,2) {};
261
        \node[vertex,red]  (n-2-1) at (2,2) {};
262
        \node[vertex,red]  (n-3-1) at (3,2) {};
263
        \node[vertex,blue] (n-4-1) at (4,2) {};
264

265
        \node[vertex,red]  (n-1-1) at (1,3) {};
266
        \node[vertex,blue] (n-2-1) at (2,3) {};
267
        \node[vertex,red]  (n-3-1) at (3,3) {};
268
        \node[vertex,blue] (n-4-1) at (4,3) {};
269

270

271
        \node[vertex,red]  (n-1-1) at (1,4) {};
272
        \node[vertex,red]  (n-2-1) at (2,4) {};
273
        \node[vertex,blue] (n-3-1) at (3,4) {};
274
        \node[vertex,blue] (n-4-1) at (4,4) {};
275
    \end{tikzpicture}
276
\end{frame}
277

278
\subsection{Bildquellen}
279
\begin{frame}{Bildquellen}
280
\begin{itemize}
281
	\item \href{http://commons.wikimedia.org/wiki/File:Hypercube.svg}{http://commons.wikimedia.org/wiki/File:Hypercube.svg}
282
    \item \href{http://commons.wikimedia.org/wiki/File:Konigsberg\_bridges.png}{http://commons.wikimedia.org/wiki/File:Konigsberg\_bridges.png}
283
    \item \href{http://commons.wikimedia.org/wiki/File:Unit\_disk\_graph.svg}{http://commons.wikimedia.org/wiki/File:Unit\_disk\_graph.svg}
284
    \item \href{http://goo.gl/maps/WnXRh}{Google Maps} (Grafiken \TCop 2013 Cnes/Spot Image, DigitalGlobe)
285
	\item \href{http://cf.drafthouse.com/\_uploads/galleries/29140/good_will\_hunting\_3.jpg}{cf.drafthouse.com/\_uploads/galleries/29140/good\_will\_hunting\_3.jpg}
286
\end{itemize}
287
\end{frame}
288

289
\subsection{Literatur}
290
\begin{frame}{Literatur}
291
\begin{itemize}
292
    \item A. Beutelspacher: \textit{Diskrete Mathematik für Einsteiger}, 4. Auflage, ISBN 978-3-8348-1248-3
293
\end{itemize}
294
\end{frame}
295

296
\subsection{Folien, \LaTeX und Material}
297
\begin{frame}{Folien, \LaTeX und Material}
298
Der Foliensatz und die \LaTeX und Ti\textit{k}Z-Quellen sind unter
299

300
\href{https://github.com/MartinThoma/LaTeX-examples/tree/master/presentations/Diskrete-Mathematik}{github.com/MartinThoma/LaTeX-examples/tree/master/presentations/Diskrete-Mathematik}
301
\\
302

303
Kurz-URL:
304
\href{http://goo.gl/uTgam}{goo.gl/uTgam}
305
\end{frame}
306

307
Product

Resources

Company
