7 files changed, 334 insertions, 0 deletions
diff --git a/vorlesungen/slides/8/Makefile.inc b/vorlesungen/slides/8/Makefile.inc
index b2823ca..81f91d0 100644
--- a/vorlesungen/slides/8/Makefile.inc
+++ b/vorlesungen/slides/8/Makefile.inc
@@ -31,5 +31,9 @@ chapter8 =								\
 	../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 2110bb2..7511e3e 100644
--- a/vorlesungen/slides/8/chapter.tex
+++ b/vorlesungen/slides/8/chapter.tex
@@ -33,4 +33,8 @@
 \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/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/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)