19 files changed, 809 insertions, 4 deletions
diff --git a/vorlesungen/11_msegraphen/Makefile b/vorlesungen/11_msegraphen/Makefile
new file mode 100644
index 0000000..36f1877
--- /dev/null
+++ b/vorlesungen/11_msegraphen/Makefile
@@ -0,0 +1,33 @@
+#
+# Makefile -- graphen
+#
+# (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil
+#
+all:	graphen-handout.pdf MathSemMSE-11-graphen.pdf
+
+include ../slides/Makefile.inc
+
+SOURCES = common.tex slides.tex $(slides)
+
+MathSemMSE-11-graphen.pdf:	MathSemMSE-11-graphen.tex $(SOURCES)
+	pdflatex MathSemMSE-11-graphen.tex
+
+graphen-handout.pdf:	graphen-handout.tex $(SOURCES)
+	pdflatex graphen-handout.tex
+
+thumbnail:	thumbnail.jpg # fix1.jpg
+
+thumbnail.pdf:	MathSemMSE-11-graphen.pdf
+	pdfjam --outfile thumbnail.pdf --papersize '{16cm,9cm}' \
+		MathSemMSE-11-graphen.pdf 1
+thumbnail.jpg:	thumbnail.pdf
+	convert -density 300 thumbnail.pdf \
+                -resize 1920x1080 -units PixelsPerInch thumbnail.jpg
+
+fix1.pdf:	MathSemMSE-11-graphen.pdf
+	pdfjam --outfile fix1.pdf --papersize '{16cm,9cm}' \
+		MathSemMSE-11-graphen.pdf 1
+fix1.jpg:	fix1.pdf
+	convert -density 300 fix1.pdf \
+                -resize 1920x1080 -units PixelsPerInch fix1.jpg
+
diff --git a/vorlesungen/11_msegraphen/MathSemMSE-11-graphen.tex b/vorlesungen/11_msegraphen/MathSemMSE-11-graphen.tex
new file mode 100644
index 0000000..6d4ff2d
--- /dev/null
+++ b/vorlesungen/11_msegraphen/MathSemMSE-11-graphen.tex
@@ -0,0 +1,14 @@
+%
+% MathSem-11-msegraphen.tex -- Präsentation 
+%
+% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\documentclass[aspectratio=169]{beamer}
+\input{common.tex}
+\setboolean{presentation}{true}
+\begin{document}
+\begin{frame}
+\titlepage
+\end{frame}
+\input{slides.tex}
+\end{document}
diff --git a/vorlesungen/11_msegraphen/common.tex b/vorlesungen/11_msegraphen/common.tex
new file mode 100644
index 0000000..67cf5e5
--- /dev/null
+++ b/vorlesungen/11_msegraphen/common.tex
@@ -0,0 +1,16 @@
+%
+% common.tex -- gemeinsame definition
+%
+% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\input{../common/packages.tex}
+\input{../common/common.tex}
+\mode<beamer>{%
+\usetheme[hideothersubsections,hidetitle]{Hannover}
+}
+\beamertemplatenavigationsymbolsempty
+\title[Graphen]{Spektrale Graphentheorie}
+\author[A.~Müller]{Prof. Dr. Andreas Müller}
+\date[]{}
+\newboolean{presentation}
+
diff --git a/vorlesungen/11_msegraphen/graphen-handout.tex b/vorlesungen/11_msegraphen/graphen-handout.tex
new file mode 100644
index 0000000..58d0aff
--- /dev/null
+++ b/vorlesungen/11_msegraphen/graphen-handout.tex
@@ -0,0 +1,11 @@
+%
+% msegraphen-handout.tex -- Handout XXX
+%
+% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\documentclass[handout,aspectratio=169]{beamer}
+\input{common.tex}
+\setboolean{presentation}{false}
+\begin{document}
+\input{slides.tex}
+\end{document}
diff --git a/vorlesungen/11_msegraphen/slides.tex b/vorlesungen/11_msegraphen/slides.tex
new file mode 100644
index 0000000..b3d1519
--- /dev/null
+++ b/vorlesungen/11_msegraphen/slides.tex
@@ -0,0 +1,35 @@
+%
+% slides.tex -- XXX
+%
+% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+
+\folie{8/graph.tex}
+\folie{8/dgraph.tex}
+\folie{8/grad.tex}
+\folie{8/inzidenz.tex}
+\folie{8/inzidenzd.tex}
+\folie{8/diffusion.tex}
+\folie{8/laplace.tex}
+\folie{8/produkt.tex}
+\folie{8/fourier.tex}
+\folie{8/spanningtree.tex}
+
+\folie{8/pfade/adjazenz.tex}
+\folie{8/pfade/langepfade.tex}
+\folie{8/pfade/beispiel.tex}
+\folie{8/pfade/gf.tex}
+
+%\folie{8/floyd-warshall/problem.tex}
+%\folie{8/floyd-warshall/rekursion.tex}
+%\folie{8/floyd-warshall/iteration.tex}
+%\folie{8/floyd-warshall/wegiteration.tex}
+%\folie{8/floyd-warshall/wege.tex}
+
+\folie{8/chrind.tex}
+\folie{8/chrindprop.tex}
+\folie{8/chroma1.tex}
+\folie{8/amax.tex}
+\folie{8/subgraph.tex}
+\folie{8/chrwilf.tex}
+\folie{8/weitere.tex}
diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc
index d46dc7f..81f91d0 100644
--- a/vorlesungen/slides/8/Makefile.inc
+++ b/vorlesungen/slides/8/Makefile.inc
@@ -28,5 +28,12 @@ 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/amax.tex						\
+	../slides/8/subgraph.tex					\
+	../slides/8/chrwilf.tex						\
+	../slides/8/weitere.tex						\
 	../slides/8/chapter.tex
 
diff --git a/vorlesungen/slides/8/amax.tex b/vorlesungen/slides/8/amax.tex
new file mode 100644
index 0000000..951400a
--- /dev/null
+++ b/vorlesungen/slides/8/amax.tex
@@ -0,0 +1,86 @@
+%
+% amax.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{$\alpha_{\text{max}}$ und $d$}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.44\textwidth}
+\begin{block}{Definition}
+$\alpha_{\text{max}}$ ist der grösste Eigenwert der Adjazenzmatrix
+\end{block}
+\uncover<2->{
+\begin{block}{Fakten}
+\begin{itemize}
+\item<3->
+Der Eigenwert $\alpha_{\text{max}}$ ist einfach
+\item<4->
+Es gibt einen positiven Eigenvektor $f$ zum Eigenwert $\alpha_{\text{max}}$
+\item<5->
+$f$ maximiert
+\[
+\frac{\langle Af,f\rangle}{\langle f,f\rangle}
+=
+\alpha_{\text{max}}
+\]
+\end{itemize}
+Herkunft: Perron-Frobenius-Theorie positiver Matrizen (nächste Woche)
+\end{block}}
+\end{column}
+\begin{column}{0.52\textwidth}
+\uncover<6->{%
+\begin{block}{Mittlerer Grad}
+\[
+\overline{d}
+=
+\frac1{n} \sum_{v} \operatorname{deg}(v)
+\le
+\alpha_{\text{max}}
+\le
+d
+\]
+\end{block}}
+\vspace{-10pt}
+\uncover<7->{%
+\begin{proof}[Beweis]
+\begin{itemize}
+\item Konstante Funktion $1$ anstelle von $f$:
+\[
+\frac{\langle A1,1\rangle}{\langle 1,1\rangle}
+\uncover<8->{=
+\frac{\sum_v \operatorname{deg}(v)}{n}}
+\uncover<9->{=
+\overline{d}}
+\uncover<10->{\le
+\alpha_{\text{max}}}
+\]
+\item<11-> Komponenten von $Af$ summieren:
+\begin{align*}
+\uncover<12->{
+\alpha_{\text{max}}
+f(v) &= (Af)(v)}\uncover<13->{ = \sum_{u\sim v} f(u)}
+\\
+\uncover<14->{\alpha_{\text{max}}
+\sum_{v}f(v)
+&=
+\sum_v
+\operatorname{deg}(v) f(v)}
+\\
+&\uncover<15->{\le
+d\sum_v f(v)}
+\;
+\uncover<16->{\Rightarrow
+\;
+\alpha_{\text{max}} \le d}
+\end{align*}
+\end{itemize}
+\end{proof}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/8/chapter.tex b/vorlesungen/slides/8/chapter.tex
index 6a0b13f..7511e3e 100644
--- a/vorlesungen/slides/8/chapter.tex
+++ b/vorlesungen/slides/8/chapter.tex
@@ -30,3 +30,11 @@
 \folie{8/tokyo/bahn1.tex}
 \folie{8/tokyo/bahn2.tex}
 
+\folie{8/chrind.tex}
+\folie{8/chrindprop.tex}
+\folie{8/chroma1.tex}
+\folie{8/amax.tex}
+\folie{8/subgraph.tex}
+\folie{8/chrwilf.tex}
+\folie{8/weitere.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/chrwilf.tex b/vorlesungen/slides/8/chrwilf.tex
new file mode 100644
index 0000000..7edb10e
--- /dev/null
+++ b/vorlesungen/slides/8/chrwilf.tex
@@ -0,0 +1,115 @@
+%
+% chrwilf.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\def\kante#1#2{
+	\draw[shorten >= 0.2cm,shorten <= 0.2cm] (#1) -- (#2);
+}
+\def\knoten#1#2{
+	\uncover<8->{
+		\fill[color=#2!30] (#1) circle[radius=0.2];
+		\draw[color=#2] (#1) circle[radius=0.2];
+	}
+	\only<-7>{
+		\draw (#1) circle[radius=0.2];
+	}
+}
+\def\R{1.5}
+\definecolor{rot}{rgb}{1,0,0}
+\definecolor{gruen}{rgb}{0,0.6,0}
+\definecolor{blau}{rgb}{0,0,1}
+\begin{frame}[t]
+\frametitle{Schranke für die chromatische Zahl}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Satz (Wilf)}
+$\uncover<2->{\operatorname{chr}(X) \le 1+}\alpha_{\text{max}} \le\uncover<2->{ 1 + }d$
+\end{block}
+\uncover<3->{%
+\begin{block}{Beispiel}
+\begin{align*}
+\uncover<4->{d&= 4}
+&&\uncover<5->{\Rightarrow& \operatorname{chr}(G) &\le 5}\\
+\uncover<6->{\alpha_{\text{max}} &= 
+2.9565}
+&&\uncover<7->{\Rightarrow& \operatorname{chr}(G) &\le 3}\\
+\uncover<4->{\overline{d} &= \frac{24}{9}=\rlap{$2.6666$}}
+\end{align*}
+\vspace{-20pt}
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+
+\coordinate (A) at (0:\R);
+\coordinate (B) at (40:\R);
+\coordinate (C) at (80:\R);
+\coordinate (D) at (120:\R);
+\coordinate (E) at (160:\R);
+\coordinate (F) at (200:\R);
+\coordinate (G) at (240:\R);
+\coordinate (H) at (280:\R);
+\coordinate (I) at (320:\R);
+
+\knoten{A}{rot}
+\knoten{B}{blau}
+\knoten{C}{gruen}
+\knoten{D}{blau}
+\knoten{E}{rot}
+\knoten{F}{blau}
+\knoten{G}{rot}
+\knoten{H}{gruen}
+\knoten{I}{blau}
+
+\kante{A}{B}
+\kante{B}{C}
+\kante{C}{D}
+\kante{D}{E}
+\kante{E}{F}
+\kante{F}{G}
+\kante{G}{H}
+\kante{H}{I}
+\kante{I}{A}
+
+\kante{A}{C}
+\kante{A}{D}
+\kante{D}{G}
+
+\end{tikzpicture}
+\end{center}
+\end{block}}
+\end{column}
+\begin{column}{0.52\textwidth}
+\uncover<9->{%
+\begin{proof}[Beweis]
+Induktion nach der Grösse $n$ des Graphen.
+\begin{itemize}
+\item<10->
+Entferne $v\in X$ mit minimalem Grad: $X'=X\setminus \{v\}$
+\item<11->
+Induktionsannahme:
+\[
+\operatorname{chr}(X')
+\le
+1+
+\alpha_{\text{max}}' 
+\]
+\item<12->
+$X'$ kann mit höhcstens $1+\alpha_{\text{max}}'\le 1+\alpha_{\text{max}}$
+Farben eingefärbt werden.
+\item<13->
+Wegen
+\(
+\deg(v) \le \overline{d} \le \alpha_{\text{max}}
+\)
+hat $v$ höchstens $\alpha_{\text{max}}$ Nachbarn, um $v$ zu färben,
+braucht man also höchstens $1+\alpha_{\text{max}}$ Farben.
+\end{itemize}
+\end{proof}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/8/inzidenz.tex b/vorlesungen/slides/8/inzidenz.tex
index 952c85b..10f88cd 100644
--- a/vorlesungen/slides/8/inzidenz.tex
+++ b/vorlesungen/slides/8/inzidenz.tex
@@ -5,6 +5,8 @@
 %
 \bgroup
 \definecolor{darkgreen}{rgb}{0,0.6,0}
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
 \begin{frame}[t]
 \frametitle{Inzidenz- und Adjazenzmatrix}
 \vspace{-20pt}
@@ -67,7 +69,7 @@
 \vspace{-10pt}
 \uncover<5->{%
 \begin{block}{Definition}
-\vspace{-15pt}
+%\vspace{-15pt}
 \begin{align*}
 B(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante $j$ endet in Knoten $i$}\\
 A(G)_{ij}&=1&&\Leftrightarrow&&\text{Kante zwischen Knoten $i$ und $j$}
diff --git a/vorlesungen/slides/8/inzidenzd.tex b/vorlesungen/slides/8/inzidenzd.tex
index 5f2f51a..43e5330 100644
--- a/vorlesungen/slides/8/inzidenzd.tex
+++ b/vorlesungen/slides/8/inzidenzd.tex
@@ -5,6 +5,8 @@
 %
 \bgroup
 \definecolor{darkgreen}{rgb}{0,0.6,0}
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
 \begin{frame}[t]
 \frametitle{Inzidenz- und Adjazenz-Matrix}
 \vspace{-20pt}
@@ -67,7 +69,7 @@
 \vspace{-15pt}
 \uncover<5->{%
 \begin{block}{Definition}
-\vspace{-20pt}
+%\vspace{-20pt}
 \begin{align*}
 B(G)_{ij}&=-1&&\Leftrightarrow&&\text{Kante $j$ von $i$}\\
 B(G)_{kj}&=+1&&\Leftrightarrow&&\text{Kante $j$ nach $k$}\\
diff --git a/vorlesungen/slides/8/produkt.tex b/vorlesungen/slides/8/produkt.tex
index 1d8b725..93333bc 100644
--- a/vorlesungen/slides/8/produkt.tex
+++ b/vorlesungen/slides/8/produkt.tex
@@ -56,7 +56,7 @@
 \end{center}
 \vspace{-15pt}
 \begin{block}{Berechne}
-\vspace{-20pt}
+%\vspace{-20pt}
 \begin{align*}
 \uncover<4->{L(G)}&\uncover<4->{=}B(G)B(G)^t
 \end{align*}
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
diff --git a/vorlesungen/slides/8/subgraph.tex b/vorlesungen/slides/8/subgraph.tex
new file mode 100644
index 0000000..f3005f9
--- /dev/null
+++ b/vorlesungen/slides/8/subgraph.tex
@@ -0,0 +1,60 @@
+%
+% subgraph.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{$\alpha_{\text{max}}$ eines Untergraphen}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Satz}
+$X'$ ein echter Untergraph von $X$ mit Adjazenzmatrix $A'$ und grösstem
+Eigenwert $\alpha_{\text{max}}'$
+\[
+\alpha_{\text{max}}' \le \alpha_{\text{max}}
+\]
+\end{block}
+\uncover<2->{$V'$ die Knoten von $X'$}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<3->{%
+\begin{proof}[Beweis]
+\begin{itemize}
+\item<4->
+$f'$ der positive Eigenvektor von $A'$
+\item<5->
+Definiere 
+\[
+g(v)
+=
+\begin{cases}
+f'(v) &\qquad v\in V'\\
+0     &\qquad \text{sonst}
+\end{cases}
+\]
+\item<6-> Skalarprodukte:
+\begin{align*}
+\uncover<7->{\langle f',f'\rangle &= \langle g,g\rangle}
+\\
+\uncover<8->{\langle A'f',f'\rangle &\le \langle Ag,g\rangle}
+\end{align*}
+\item<9-> Vergleich
+\[
+\alpha_{\text{max}}'
+=
+\frac{\langle A'f',f'\rangle}{\langle f',f'\rangle}
+\uncover<10->{\le 
+\frac{\langle Ag,g\rangle}{\langle g,g\rangle}}
+\uncover<11->{\le
+\alpha_{\text{max}}}
+\]
+\end{itemize}
+\end{proof}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/8/weitere.tex b/vorlesungen/slides/8/weitere.tex
new file mode 100644
index 0000000..46a3da0
--- /dev/null
+++ b/vorlesungen/slides/8/weitere.tex
@@ -0,0 +1,43 @@
+%
+% weitere.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Weitere Resultate der spektralen Graphentheorie}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Satz (Hoffmann)}
+\[
+\operatorname{chr} X \ge 1 + \frac{\alpha_{\text{max}}}{-\alpha_{\text{min}}}
+\]
+\end{block}
+\uncover<2->{%
+\begin{block}{Satz (Hoffmann)}
+\[
+\operatorname{ind} X \le n \biggl(1-\frac{d_{\text{min}}}{\lambda_{\text{max}}}\biggr)
+\]
+\end{block}}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<3->{%
+\begin{block}{Korollar}
+Für einen regulären Graphen mit $n$ Knoten gilt
+\begin{align*}
+\operatorname{ind} X
+&\le
+\frac{n}{\displaystyle 1-\frac{d}{\alpha_{\text{min}}}}
+\\
+\operatorname{chr} X
+&\ge
+1-\frac{d}{\alpha_{\text{min}}}
+\end{align*}
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/8/wilf.m b/vorlesungen/slides/8/wilf.m
new file mode 100644
index 0000000..49dc161
--- /dev/null
+++ b/vorlesungen/slides/8/wilf.m
@@ -0,0 +1,22 @@
+#
+# wilf.m -- chromatische Zahl für einen Graphen
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+N = 9;
+A = zeros(N,N);
+
+for i = (1:N)
+	j = 1 + rem(i, N)
+	A(i,j) = 1;
+endfor
+for i = (1:3:N-3)
+	j = 1 + rem(i + 2, N)
+	A(i,j) = 1;
+endfor
+
+A(1,3) = 1;
+
+A = A + A'
+
+eig(A)