blob: 094588c0ea2f26db44de649257559c16b8191f52 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
%
% chrindprop.tex -- slide template
%
% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
%
\bgroup
\begin{frame}[t]
\setlength{\abovedisplayskip}{5pt}
\setlength{\belowdisplayskip}{5pt}
\frametitle{Zusammenhang zwischen $\operatorname{chr}G$ und $\operatorname{ind}G$}
\vspace{-20pt}
\begin{columns}[t,onlytextwidth]
\begin{column}{0.38\textwidth}
\begin{block}{Proposition}
Ist $G$ ein Graph mit $n$ Knoten, dann gilt
\[
\operatorname{chr}G
\cdot
\operatorname{ind}G
\ge n
\]
\end{block}
\uncover<2->{%
\begin{block}{Beispiel}
Peterson-Graph $K$ hat $n=10$ Knoten:
\[
\operatorname{chr}(K)
\cdot
\operatorname{ind}(K)
=
3\cdot 4
\ge
10
=
n
\]
\end{block}}
\end{column}
\begin{column}{0.58\textwidth}
\uncover<3->{%
\begin{proof}[Beweis]
\begin{itemize}
\item<4-> eine minimale Färbung hat $\operatorname{chr}(G)$ Farben
\item<5-> Sie teilt die Knoten in $\operatorname{chr}(G)$
gleichfarbige Mengen auf
\item<6-> Jede einfarbige Menge von Knoten ist unabhängig, d.~h.~sie
besteht aus Knoten, die nicht miteinander verbunden sind.
\item<7-> Jede einfarbige Menge enthält höchstens $\operatorname{ind}(G)$
\item<8-> Die Gesamtzahl der Knoten ist
\[
n\uncover<9->{=\sum_{\text{Farbe}}\underbrace{|V_{\text{Farbe}}|}_{\le \operatorname{ind}(G)}}
\uncover<10->{\le
\operatorname{chr}(G)
\cdot
\operatorname{ind}(G)}
\]
\end{itemize}
\end{proof}}
\end{column}
\end{columns}
\end{frame}
\egroup
|
