1 files changed, 62 insertions, 0 deletions
diff --git a/vorlesungen/slides/8/chrindprop.tex b/vorlesungen/slides/8/chrindprop.tex
new file mode 100644
index 0000000..094588c
--- /dev/null
+++ b/vorlesungen/slides/8/chrindprop.tex
@@ -0,0 +1,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