add new slides

6 files changed, 359 insertions, 1 deletions

diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc
index d46dc7f..b2823ca 100644
--- a/vorlesungen/slides/8/Makefile.inc
+++ b/vorlesungen/slides/8/Makefile.inc
@@ -28,5 +28,8 @@ chapter8 =								\
 	../slides/8/tokyo/bahn0.tex					\
 	../slides/8/tokyo/bahn1.tex					\
 	../slides/8/tokyo/bahn2.tex					\
+	../slides/8/chrind.tex						\
+	../slides/8/chrindprop.tex					\
+	../slides/8/chroma1.tex						\
 	../slides/8/chapter.tex
 
diff --git a/vorlesungen/slides/8/chapter.tex b/vorlesungen/slides/8/chapter.tex
index 6a0b13f..2110bb2 100644
--- a/vorlesungen/slides/8/chapter.tex
+++ b/vorlesungen/slides/8/chapter.tex
@@ -30,3 +30,7 @@
 \folie{8/tokyo/bahn1.tex}
 \folie{8/tokyo/bahn2.tex}
 
+\folie{8/chrind.tex}
+\folie{8/chrindprop.tex}
+\folie{8/chroma1.tex}
+
diff --git a/vorlesungen/slides/8/chrind.tex b/vorlesungen/slides/8/chrind.tex
new file mode 100644
index 0000000..bd406ab
--- /dev/null
+++ b/vorlesungen/slides/8/chrind.tex
@@ -0,0 +1,231 @@
+%
+% chrind.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Chromatische Zahl und Unabhängigkeitszahl}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Chromatische Zahl}
+$\operatorname{chr}(G)=\mathstrut$
+minimale Anzahl Farben, die zum Einfärben eines Graphen $G$ nötig sind derart,
+dass benachbarte Knoten verschiedene Farben haben.
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+
+\def\Ra{2}
+\def\Ri{1}
+\def\e{1.0}
+\def\r{0.2}
+
+\definecolor{rot}{rgb}{0.8,0,0.8}
+\definecolor{gruen}{rgb}{0.2,0.6,0.2}
+\definecolor{blau}{rgb}{1,0.6,0.2}
+
+\coordinate (PA) at ({\Ri*sin(0*72)},{\e*\Ri*cos(0*72)});
+\coordinate (PB) at ({\Ri*sin(1*72)},{\e*\Ri*cos(1*72)});
+\coordinate (PC) at ({\Ri*sin(2*72)},{\e*\Ri*cos(2*72)});
+\coordinate (PD) at ({\Ri*sin(3*72)},{\e*\Ri*cos(3*72)});
+\coordinate (PE) at ({\Ri*sin(4*72)},{\e*\Ri*cos(4*72)});
+
+\coordinate (QA) at ({\Ra*sin(0*72)},{\e*\Ra*cos(0*72)});
+\coordinate (QB) at ({\Ra*sin(1*72)},{\e*\Ra*cos(1*72)});
+\coordinate (QC) at ({\Ra*sin(2*72)},{\e*\Ra*cos(2*72)});
+\coordinate (QD) at ({\Ra*sin(3*72)},{\e*\Ra*cos(3*72)});
+\coordinate (QE) at ({\Ra*sin(4*72)},{\e*\Ra*cos(4*72)});
+
+\draw (PA)--(PC)--(PE)--(PB)--(PD)--cycle;
+\draw (QA)--(QB)--(QC)--(QD)--(QE)--cycle;
+\draw (PA)--(QA);
+\draw (PB)--(QB);
+\draw (PC)--(QC);
+\draw (PD)--(QD);
+\draw (PE)--(QE);
+
+\only<1>{
+        \fill[color=white] (PA) circle[radius=\r];
+        \fill[color=white] (PB) circle[radius=\r];
+        \fill[color=white] (PC) circle[radius=\r];
+        \fill[color=white] (PD) circle[radius=\r];
+        \fill[color=white] (PE) circle[radius=\r];
+        \fill[color=white] (QA) circle[radius=\r];
+        \fill[color=white] (QB) circle[radius=\r];
+        \fill[color=white] (QC) circle[radius=\r];
+        \fill[color=white] (QD) circle[radius=\r];
+        \fill[color=white] (QE) circle[radius=\r];
+}
+
+\only<2->{
+        \fill[color=blau] (PA) circle[radius=\r];
+        \fill[color=rot] (PB) circle[radius=\r];
+        \fill[color=rot] (PC) circle[radius=\r];
+        \fill[color=gruen] (PD) circle[radius=\r];
+        \fill[color=gruen] (PE) circle[radius=\r];
+
+        \fill[color=rot] (QA) circle[radius=\r];
+        \fill[color=blau] (QB) circle[radius=\r];
+        \fill[color=gruen] (QC) circle[radius=\r];
+        \fill[color=rot] (QD) circle[radius=\r];
+        \fill[color=blau] (QE) circle[radius=\r];
+}
+
+\draw (PA) circle[radius=\r];
+\draw (PB) circle[radius=\r];
+\draw (PC) circle[radius=\r];
+\draw (PD) circle[radius=\r];
+\draw (PE) circle[radius=\r];
+
+\draw (QA) circle[radius=\r];
+\draw (QB) circle[radius=\r];
+\draw (QC) circle[radius=\r];
+\draw (QD) circle[radius=\r];
+\draw (QE) circle[radius=\r];
+
+\node at ($0.5*(QC)+0.5*(QD)+(0,-0.2)$) [below] {$\operatorname{chr} G = 3$};
+
+\end{tikzpicture}
+\end{center}
+\end{block}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<3->{%
+\begin{block}{Unabhängigkeitszahl}
+$\operatorname{ind}(G)=\mathstrut$
+maximale Anzahl nicht benachbarter Knoten
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+
+\def\Ra{2}
+\def\Ri{1}
+\def\e{1.0}
+\def\r{0.2}
+
+\definecolor{rot}{rgb}{0.8,0,0.8}
+\definecolor{gruen}{rgb}{0.2,0.6,0.2}
+\definecolor{blau}{rgb}{1,0.6,0.2}
+\definecolor{gelb}{rgb}{0,0,1}
+
+\coordinate (PA) at ({\Ri*sin(0*72)},{\e*\Ri*cos(0*72)});
+\coordinate (PB) at ({\Ri*sin(1*72)},{\e*\Ri*cos(1*72)});
+\coordinate (PC) at ({\Ri*sin(2*72)},{\e*\Ri*cos(2*72)});
+\coordinate (PD) at ({\Ri*sin(3*72)},{\e*\Ri*cos(3*72)});
+\coordinate (PE) at ({\Ri*sin(4*72)},{\e*\Ri*cos(4*72)});
+
+\coordinate (QA) at ({\Ra*sin(0*72)},{\e*\Ra*cos(0*72)});
+\coordinate (QB) at ({\Ra*sin(1*72)},{\e*\Ra*cos(1*72)});
+\coordinate (QC) at ({\Ra*sin(2*72)},{\e*\Ra*cos(2*72)});
+\coordinate (QD) at ({\Ra*sin(3*72)},{\e*\Ra*cos(3*72)});
+\coordinate (QE) at ({\Ra*sin(4*72)},{\e*\Ra*cos(4*72)});
+
+\draw (PA)--(PC)--(PE)--(PB)--(PD)--cycle;
+\draw (QA)--(QB)--(QC)--(QD)--(QE)--cycle;
+\draw (PA)--(QA);
+\draw (PB)--(QB);
+\draw (PC)--(QC);
+\draw (PD)--(QD);
+\draw (PE)--(QE);
+
+\foreach \n in {1,...,7}{
+	\only<\n>{\node[color=white] at (1,2.9) {$\n$};}
+}
+
+\fill[color=white] (PA) circle[radius=\r];
+\fill[color=white] (PB) circle[radius=\r];
+\fill[color=white] (PC) circle[radius=\r];
+\fill[color=white] (PD) circle[radius=\r];
+\fill[color=white] (PE) circle[radius=\r];
+\fill[color=white] (QA) circle[radius=\r];
+\fill[color=white] (QB) circle[radius=\r];
+\fill[color=white] (QC) circle[radius=\r];
+\fill[color=white] (QD) circle[radius=\r];
+\fill[color=white] (QE) circle[radius=\r];
+
+\only<4->{
+        \fill[color=rot] (QA) circle[radius={1.5*\r}];
+        \fill[color=rot!40] (QB) circle[radius=\r];
+        \fill[color=rot!40] (QE) circle[radius=\r];
+        \fill[color=rot!40] (PA) circle[radius=\r];
+}
+
+\only<5->{
+        \fill[color=blau] (PB) circle[radius={1.5*\r}];
+        \fill[color=blau!40] (PD) circle[radius=\r];
+        \fill[color=blau!40] (PE) circle[radius=\r];
+        \fill[color=blau!80,opacity=0.5] (QB) circle[radius=\r];
+}
+
+\only<6->{
+        \fill[color=gruen] (PC) circle[radius={1.5*\r}];
+        \fill[color=gruen!40] (QC) circle[radius=\r];
+        \fill[color=gruen!80,opacity=0.5] (PA) circle[radius=\r];
+        \fill[color=gruen!80,opacity=0.5] (PE) circle[radius=\r];
+}
+
+\only<7->{
+        \fill[color=gelb] (QD) circle[radius={1.5*\r}];
+        \fill[color=gelb!80,opacity=0.5] (QC) circle[radius=\r];
+        \fill[color=gelb!80,opacity=0.5] (QE) circle[radius=\r];
+        \fill[color=gelb!80,opacity=0.5] (PD) circle[radius=\r];
+}
+
+\only<-3|handout:0>{
+	\draw (QA) circle[radius=\r];
+}
+\only<4->{
+	\draw (QA) circle[radius={1.5*\r}];
+}
+
+\only<-4|handout:0>{
+	\draw (PB) circle[radius=\r];
+}
+\only<5->{
+	\draw (PB) circle[radius={1.5*\r}];
+}
+
+\only<-5|handout:0>{
+	\draw (PC) circle[radius=\r];
+}
+\only<6->{
+	\draw (PC) circle[radius={1.5*\r}];
+}
+
+\only<-6|handout:0>{
+	\draw (QD) circle[radius=\r];
+}
+\only<7->{
+	\draw (QD) circle[radius={1.5*\r}];
+}
+
+\draw (PA) circle[radius=\r];
+\draw (PD) circle[radius=\r];
+\draw (PE) circle[radius=\r];
+
+\draw (QB) circle[radius=\r];
+\draw (QC) circle[radius=\r];
+\draw (QE) circle[radius=\r];
+
+\only<4|handout:0>{
+\node at ($0.5*(QC)+0.5*(QD)+(0,-0.2)$) [below] {$\operatorname{ind} G = 1$};
+}
+\only<5|handout:0>{
+\node at ($0.5*(QC)+0.5*(QD)+(0,-0.2)$) [below] {$\operatorname{ind} G = 2$};
+}
+\only<6|handout:0>{
+\node at ($0.5*(QC)+0.5*(QD)+(0,-0.2)$) [below] {$\operatorname{ind} G = 3$};
+}
+\only<7->{
+\node at ($0.5*(QC)+0.5*(QD)+(0,-0.2)$) [below] {$\operatorname{ind} G = 4$};
+}
+
+\end{tikzpicture}
+\end{center}
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
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
diff --git a/vorlesungen/slides/8/chroma1.tex b/vorlesungen/slides/8/chroma1.tex
new file mode 100644
index 0000000..6a55704
--- /dev/null
+++ b/vorlesungen/slides/8/chroma1.tex
@@ -0,0 +1,56 @@
+%
+% chroma1.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Schranke für $\operatorname{chr}(G)$}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.40\textwidth}
+\begin{block}{Proposition}
+Ist $G$ ein Graph mit maximalem Grad $d$, dann gilt
+\[
+\operatorname{chr}(G) \le d + 1
+\]
+\end{block}
+\uncover<2->{%
+\begin{block}{Beispiel}
+\begin{itemize}
+\item<3->
+Peterson-Graph $G$: maximaler Grad ist $d=3$, aber
+\[
+\operatorname{chr}(G)
+=
+3
+< d+1=4
+\]
+\item<4->
+Voller Graph $V$: maximaler Grad ist $d=n-1$,
+\[
+\operatorname{chr}(V) = n = d+1
+\]
+\end{itemize}
+\end{block}}
+\end{column}
+\begin{column}{0.58\textwidth}
+\uncover<4->{%
+\begin{proof}[Beweis]
+Mit vollständiger Induktion, d.~h.~Annahme: Graphen mit $<n$ Knoten und
+maximalem Grad $d$ lassen sich mit höchstens $d+1$ Farben färben.
+\begin{itemize}
+\item<5-> $X$ ein Graph mit $n$ Knoten
+\item<6-> entferne den Knoten $v\in X$, $X'=X\setminus\{v\}$
+\item<7-> $X'$ lässt sich mit höchstens $d+1$ Farben einfärben
+\item<8-> $v$ hat höchstens $d$ Nachbarn, die höchsten $d$ verschiedene
+Farben haben
+\item<9-> Es bleibt eine Farbe für $v$
+\end{itemize}
+\end{proof}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/8/spanningtree.tex b/vorlesungen/slides/8/spanningtree.tex
index 425fe1c..62180d9 100644
--- a/vorlesungen/slides/8/spanningtree.tex
+++ b/vorlesungen/slides/8/spanningtree.tex
@@ -3,6 +3,7 @@
 %
 % (c) 2019 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
+\bgroup
 \begin{frame}
 \frametitle{Spannbäume}
 
@@ -121,7 +122,7 @@ Wieviele Spannbäume gibt es?
 \begin{column}{0.56\hsize}
 \uncover<5->{%
 \begin{block}{Laplace-Matrix}
-\vspace{-15pt}
+%\vspace{-15pt}
 \[
 L=
 \tiny
@@ -162,3 +163,4 @@ L\text{ ohne }\left\{\begin{array}{c}\text{Zeile $i$}\\\text{Spalte $j$}\end{arr
 \end{columns}
 
 \end{frame}
+\egroup