Merge remote-tracking branch 'upstream/master'

16 files changed, 1107 insertions, 167 deletions

diff --git a/buch/chapters/10-vektorenmatrizen/gruppen.tex b/buch/chapters/10-vektorenmatrizen/gruppen.tex
index 7628942..cb37d05 100644
--- a/buch/chapters/10-vektorenmatrizen/gruppen.tex
+++ b/buch/chapters/10-vektorenmatrizen/gruppen.tex
@@ -313,14 +313,14 @@ auf einem geeigneten Vektorraum.
 \begin{definition}
 \label{buch:vektorenmatrizen:def:darstellung}
 Eine Darstellung einer Gruppe $G$ ist ein Homomorphismus 
-$G\to\operatorname{GL}_(\mathbb{R})$.
+$G\to\operatorname{GL}_n(\mathbb{R})$.
 \index{Darstellung}
 \end{definition}
 
 \begin{beispiel}
 Die Gruppen $\operatorname{GL}_n(\mathbb{Z})$,
 $\operatorname{SL}_n(\mathbb{Z})$ oder $\operatorname{SO}(n)$ 
-sind alle Teilmengen von $\operatorname{GL}_n(\mathbb{R}$.
+sind alle Teilmengen von $\operatorname{GL}_n(\mathbb{R})$.
 Die Einbettungsabbildung $G\hookrightarrow \operatorname{GL}_n(\mathbb{R})$
 ist damit automatisch eine Darstellung, sie heisst auch die
 {\em reguläre Darstellung} der Gruppe $G$.
diff --git a/buch/chapters/60-gruppen/lie-gruppen.tex b/buch/chapters/60-gruppen/lie-gruppen.tex
index d6fc007..e92c254 100644
--- a/buch/chapters/60-gruppen/lie-gruppen.tex
+++ b/buch/chapters/60-gruppen/lie-gruppen.tex
@@ -29,7 +29,7 @@ wenn es gelingt, eine Karte für eine Umgebung des neutralen Elements
 zu finden.
 Dazu muss gezeigt werden, dass sich aus einer solchen Karte für jedes
 andere Gruppenelement eine Karte für eine Umgebung ableiten lässt.
-Sei also $\varphi_e\colon U_e\mathbb{R}^N$ eine Karte für die Umgebung
+Sei also $\varphi_e\colon U_e \to \mathbb{R}^N$ eine Karte für die Umgebung
 $U_e\subset G$ von $e\in G$.
 Für $g\in G$ ist dann die Abbildung
 \[
diff --git a/buch/chapters/70-graphen/Makefile.inc b/buch/chapters/70-graphen/Makefile.inc
index d8fe742..2a7d9a6 100644
--- a/buch/chapters/70-graphen/Makefile.inc
+++ b/buch/chapters/70-graphen/Makefile.inc
@@ -7,5 +7,6 @@
 CHAPTERFILES = $(CHAPTERFILES)						\
 	chapters/70-graphen/beschreibung.tex				\
 	chapters/70-graphen/spektral.tex				\
+	chapters/70-graphen/waerme.tex					\
 	chapters/70-graphen/wavelets.tex				\
 	chapters/70-graphen/chapter.tex
diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex
index 25cfcc0..a0f46da 100644
--- a/buch/chapters/70-graphen/beschreibung.tex
+++ b/buch/chapters/70-graphen/beschreibung.tex
@@ -401,7 +401,7 @@ Sie hat für $i\ne j$ die Einträge
 \\
 &=\text{Anzahl der Kanten, die $i$ mit $j$ verbinden}
 \\
-&=a_{ij}
+&=a_{ij}.
 \end{align*}
 Die Adjazenzmatrix eines Graphen lässt sich also aus der
 Inzidenzmatrix berechnen.
diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex
index b6e02c9..6def393 100644
--- a/buch/chapters/70-graphen/chapter.tex
+++ b/buch/chapters/70-graphen/chapter.tex
@@ -65,5 +65,6 @@ Basis zur Beschreibung von Funktionen auf dem Graphen.
 
 \input{chapters/70-graphen/beschreibung.tex}
 \input{chapters/70-graphen/spektral.tex}
+\input{chapters/70-graphen/waerme.tex}
 \input{chapters/70-graphen/wavelets.tex}
 
diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile
index bd77756..5db54c8 100644
--- a/buch/chapters/70-graphen/images/Makefile
+++ b/buch/chapters/70-graphen/images/Makefile
@@ -3,11 +3,14 @@
 #
 # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
 #
-all:	peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf fundamental.pdf
+all:	peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf fundamental.pdf \
+	petersonchrind.pdf nine.pdf gh.pdf
 
 peterson.pdf:	peterson.tex
 	pdflatex peterson.tex
 
+petersonchrind.pdf:	petersonchrind.tex
+	pdflatex petersonchrind.tex
 adjazenzu.pdf:	adjazenzu.tex
 	pdflatex adjazenzu.tex
 
@@ -20,3 +23,9 @@ kreis.pdf:	kreis.tex
 fundamental.pdf:	fundamental.tex
 	pdflatex fundamental.tex
 
+nine.pdf:	nine.tex
+	pdflatex nine.tex
+
+gh.pdf:	gh.tex
+	pdflatex gh.tex
+
diff --git a/buch/chapters/70-graphen/images/gh.pdf b/buch/chapters/70-graphen/images/gh.pdf
new file mode 100644
index 0000000..c6e48d7
--- /dev/null
+++ b/buch/chapters/70-graphen/images/gh.pdf
diff --git a/buch/chapters/70-graphen/images/gh.tex b/buch/chapters/70-graphen/images/gh.tex
new file mode 100644
index 0000000..fcceb5f
--- /dev/null
+++ b/buch/chapters/70-graphen/images/gh.tex
@@ -0,0 +1,55 @@
+%
+% gh.tex -- Lokalsierungsfunktionen für Wavelets auf einem Graphen
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+
+\def\kurve#1#2{
+	\draw[color=#2,line width=1.4pt]
+		plot[domain=0:6.3,samples=400]
+			({\x},{7*\x*exp(-(\x/#1)*(\x/#1))/#1});
+}
+
+\begin{scope}
+
+\draw[->] (-0.1,0) -- (6.6,0) coordinate[label={$\lambda$}];
+
+\kurve{1}{red}
+\foreach \k in {0,...,4}{
+	\pgfmathparse{0.30*exp(ln(2)*\k)}
+	\xdef\l{\pgfmathresult}
+	\kurve{\l}{blue}
+}
+
+\node[color=red] at ({0.7*1},3) [above] {$g(\lambda)$};
+\node[color=blue] at ({0.7*0.3*16},3) [above] {$g_i(\lambda)$};
+
+\draw[->] (0,-0.1) -- (0,3.3);
+\end{scope}
+
+\begin{scope}[xshift=7cm]
+
+\draw[->] (-0.1,0) -- (6.6,0) coordinate[label={$\lambda$}];
+
+\draw[color=darkgreen,line width=1.4pt]
+	plot[domain=0:6.3,samples=100] 
+		({\x},{3*exp(-(\x/0.5)*(\x/0.5)});
+
+\draw[->] (0,-0.1) -- (0,3.3) coordinate[label={right:$\color{darkgreen}h(\lambda)$}];
+
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/70-graphen/images/nine.pdf b/buch/chapters/70-graphen/images/nine.pdf
new file mode 100644
index 0000000..2ae9f68
--- /dev/null
+++ b/buch/chapters/70-graphen/images/nine.pdf
diff --git a/buch/chapters/70-graphen/images/nine.tex b/buch/chapters/70-graphen/images/nine.tex
new file mode 100644
index 0000000..f214c1e
--- /dev/null
+++ b/buch/chapters/70-graphen/images/nine.tex
@@ -0,0 +1,67 @@
+%
+% nine.tex -- Nine node graph to illustrate Wilf's theorem
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\def\kante#1#2{
+        \draw[shorten >= 0.2cm,shorten <= 0.2cm] (#1) -- (#2);
+}
+\def\knoten#1#2{
+                \fill[color=#2!30] (#1) circle[radius=0.2];
+                \draw[color=#2] (#1) circle[radius=0.2];
+                \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{tikzpicture}[>=latex,thick,scale=\skala]
+
+\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{document}
+
diff --git a/buch/chapters/70-graphen/images/petersonchrind.pdf b/buch/chapters/70-graphen/images/petersonchrind.pdf
new file mode 100644
index 0000000..23ef6e9
--- /dev/null
+++ b/buch/chapters/70-graphen/images/petersonchrind.pdf
diff --git a/buch/chapters/70-graphen/images/petersonchrind.tex b/buch/chapters/70-graphen/images/petersonchrind.tex
new file mode 100644
index 0000000..4ae9f39
--- /dev/null
+++ b/buch/chapters/70-graphen/images/petersonchrind.tex
@@ -0,0 +1,142 @@
+%
+% tikztemplate.tex -- template for standalon tikz images
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\Ra{2}
+\def\Ri{1}
+\def\e{1.0}
+\def\r{0.2}
+
+\begin{scope}[xshift=-3.5cm]
+
+\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);
+
+\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,{-\Ra}) [below] {$\operatorname{chr}P=3\mathstrut$};
+
+\end{scope}
+
+\begin{scope}[xshift=3.5cm]
+\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);
+
+\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];
+
+\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];
+
+\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];
+
+\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];
+
+\draw (PA) circle[radius=\r];
+\draw (PB) circle[radius={1.5*\r}];
+\draw (PC) circle[radius={1.5*\r}];
+\draw (PD) circle[radius=\r];
+\draw (PE) circle[radius=\r];
+
+\draw (QA) circle[radius={1.5*\r}];
+\draw (QB) circle[radius=\r];
+\draw (QC) circle[radius=\r];
+\draw (QD) circle[radius={1.5*\r}];
+\draw (QE) circle[radius=\r];
+
+\node at (0,{-\Ra}) [below] {$\operatorname{ind}P=4\mathstrut$};
+
+\end{scope}
+
+
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex
index f68c814..5fb3056 100644
--- a/buch/chapters/70-graphen/spektral.tex
+++ b/buch/chapters/70-graphen/spektral.tex
@@ -1,198 +1,465 @@
 %
-% spektral.tex
+% spektral.tex -- spektrale Graphentheorie
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
 %
 \section{Spektrale Graphentheorie
 \label{buch:section:spektrale-graphentheorie}}
 \rhead{Spektrale Graphentheorie}
-Die Laplace-Matrix codiert alle wesentliche Information eines
+Die Adjazenz-Matrix, die Grad-Matrix und damit natürlich auch
+die Laplace-Matrix codieren alle wesentliche Information eines
 ungerichteten Graphen.
 Sie operiert auf Vektoren, die für jeden Knoten des Graphen eine
 Komponente haben.
 Dies eröffnet die Möglichkeit, den Graphen über die linearalgebraischen
-Eigenschaften der Laplace-Matrix zu studieren.
-
-\subsection{Grapheigenschaften und Spektrum von $L$
-\label{buch:subsection:grapheigenschaften-und-spektrum-von-l}}
-TODO XXX 
-
-\subsection{Wärmeleitung auf einem Graphen
-\label{buch:subsection:waermeleitung-auf-einem-graphen}}
-Die Vektoren, auf denen die Laplace-Matrix operiert, können betrachtet
-werden als Funktionen, die jedem Knoten einen Wert zuordnen.
-Eine mögliche physikalische Interpretation davon ist die Temperaturverteilung
-auf dem Graphen.
-Die Kanten zwischen den Knoten erlauben der Wärmeenergie, von einem Knoten
-zu einem anderen zu fliessen.
-Je grösser die Temperaturdifferenz zwischen zwei Knoten ist, desto
-grösser ist der Wärmefluss und desto schneller ändert sich die Temperatur
-der beteiligten Knoten.
-Die zeitliche Änderung der Temperatur $T_i$ im Knoten $i$ ist proportional
-\[
-\frac{dT_i}{dt}
-=
-\sum_{\text{$j$ Nachbar von $i$}} \kappa (T_j-T_i)
-=
--
-\kappa
-\biggl(
-d_iT_i
--
-\sum_{\text{$j$ Nachbar von $i$}} T_j
-\biggr)
-\]
-Der Term auf der rechten Seite ist genau die Wirkung der 
-Laplace-Matrix auf dem Vektor $T$ der Temperaturen:
-\begin{equation}
-\frac{dT}{dt}
-=
--\kappa L T.
-\label{buch:graphen:eqn:waermeleitung}
-\end{equation}
-Der Wärmefluss, der durch die
-Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} beschrieben
-wird, codiert ebenfalls wesentliche Informationen über den Graphen.
-Je mehr Kanten es zwischen verschiedenen Teilen eines Graphen gibt,
-desto schneller findet der Wärmeaustausch zwischen diesen Teilen
-statt.
-Die Lösungen der Wärmeleitungsgleichung liefern also Informationen 
-über den Graphen.
-
-\subsection{Eigenwerte und Eigenvektoren
-\label{buch:subsection:ein-zyklischer-graph}}
-Die Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} 
-ist eine lineare Differentialgleichung mit konstanten Koeffizienten,
-die mit der Matrixexponentialfunktion gelöst werden.
-Die Lösung ist
-\[
-f(t) = e^{-\kappa Lt}f(0).
-\]
+Eigenschaften dieser Matrizen zu studieren.
+Dieser Abschnitt soll diese Idee an dem ziemlich übersichtlichen Beispiel
+der chromatischen Zahl eines Graphen illustrieren.
+
+\subsection{Chromatische Zahl und Unabhängigkeitszahl
+\label{buch:subsection:chromatische-zahl}}
+Der Grad eines Knotens ist ein mass dafür, wie stark ein Graph
+``vernetzt'' ist.
+Je höher der Grad, desto mehr direkte Verbindungen zwischen Knoten gibt es.
+Noch etwas präziser können diese Idee die beiden mit Hilfe der
+chromatischen zahl und der Unabhängigkeitszahl erfasst werden.
+
+\begin{definition}
+Die {\em chromatische Zahl} $\operatorname{chr}G$ eines Graphen $G$ ist
+die minimale Anzahl von Farben, die Einfärben der Knoten eines Graphen
+nötig sind, sodass benachbarte Knoten verschiedene Farben haben.
+\index{chromatische Zahl}
+\end{definition}
+
+\begin{definition}
+Eine Menge von Knoten eines Graphen heisst {\em unabhängig}, wenn 
+keine zwei Knoten im Graphen verbunden sind.
+Die {\em Unabhängigkeitszahl} $\operatorname{ind}G$ eines Graphen $G$
+ist die maximale Anzahl Knoten einer unabhängigen Menge.
+\index{Unabhängigkeitszahl}
+\end{definition}
 
-Die Berechnung der Lösung mit der Matrixexponentialreihe ist ziemlich
-ineffizient, da grosse Matrizenprodukte berechnet werden müssen.
-Da die Matrix $L$ symmetrisch ist, gibt es eine Basis aus 
-orthonormierten Eigenvektoren und die Eigenwerte sind reell.
-Wir bezeichnen die Eigenvektoren mit $f_1,\dots,f_n$  und die
-zugehörigen Eigenwerte mit $\lambda_i$.
-Die Funktion $f_i(t)= e^{-\kappa\lambda_it}f_i$ ist dann eine Lösung
-der Wärmeleitungsgleichung, denn die beiden Seiten
+Zwischen der chromatischen Zahl und der Unabhängigkeitszahl eines Graphen
+muss es einen Zusammenhang geben.
+Je mehr Verbingungen es im Graphen gibt, desto grösser wird die chromatische
+Zahl.
+Gleichzeitig wird es schwieriger für Mengen von Knoten, unabhängig zu sein.
+
+\begin{satz}
+\label{buch:satz:chrind}
+Ist $G$ ein Graph mit $n$ Knoten, dann gilt
+$\operatorname{chr}G\cdot\operatorname{ind}G\ge n$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Eine minimale Färbung des Graphen mit $\operatorname{chr}G$ Farben
+teilt die Knoten in $\operatorname{chr}G$ Mengen $V_f$ von Knoten mit
+gleicher Farbe $f$ ein.
+Da diese Mengen einfarbig sind, sind sie unabhängig, enthalten also
+höchstens so viele Knoten, wie die Unabhängigkeitszahl erlaubt,
+also $|V_f|\le \operatorname{ind}G$.
+Da die Menge aller Knoten die Vereinigung der Mengen $V_f$ ist,
+ist die Gesamtzahl der Knoten 
 \begin{align*}
-\frac{d}{dt}f_i(t)
+V
 &=
--\kappa\lambda_ie^{-\kappa\lambda_it}f_i
-=
--\kappa\lambda_i f_i(t)
-\\
--\kappa Lf_i(t)
+\bigcup_{\text{$f$ eine Farbe}} V_f
+&&\Rightarrow&
+n
 &=
--\kappa e^{-\kappa\lambda_it} Lf_i
+\sum_{\text{$f$ eine Farbe}} |V_f| 
+\\
+&
+&&&
+&\le
+\sum_{\text{$f$ eine Farbe}} \operatorname{ind}G
 =
--\kappa e^{-\kappa\lambda_it} \lambda_i f_i
+(\text{Anzahl Farben})\cdot \operatorname{ind}G
 =
--\kappa \lambda_i f_i(t)
+\operatorname{chr}G \cdot \operatorname{ind}G.
 \end{align*}
-von \eqref{buch:graphen:eqn:waermeleitung} stimmen überein.
-
-Eine Lösung der Wärmeleitungsgleichung zu einer beliebigen
-Anfangstemperaturverteilung $f$ kann durch Linearkombination aus 
-den Lösungen $f_i(t)$ zusammengesetzt werden.
-Dazu ist nötig, $f$ aus den Vektoren $f_i$ linear zu kombinieren.
-Da aber die $f_i$ orthonormiert sind, ist dies besonders einfach,
-die Koeffizienten sind die Skalarprodukte mit den Eigenvektoren:
-\[
-f=\sum_{i=1}^n \langle f_i,f\rangle f_i.
-\]
-Daraus kann man die allgmeine Lösungsformel
+Damit ist $n\le \operatorname{chr}G\cdot\operatorname{ind}G$ gezeigt.
+\qedhere
+\end{proof}
+
+\begin{beispiel}
+In einem vollständigen Graphen ist jeder Knoten mit jedem anderen verbunden.
+Jede Menge mit zwei oder mehr Knoten kann daher nicht unabhängig sein, die
+Unabhängigkeitszahl ist daher $\operatorname{ind}G=1$.
+Andererseits ist für jeden Knoten eine eigene Farbe nötig, daher ist die
+chromatische Zahl $\operatorname{chr}G=n$.
+Die Ungleichung von Satz~\ref{buch:satz:chrind} ist erfüllt, sogar mit
+Gleichheit.
+Das Beispiel zeigt, dass die Ungleichung nicht ohne zusätzliche Annahmen
+verbessert werden kann.
+\end{beispiel}
+
+\begin{figure}
+\centering
+\includegraphics{chapters/70-graphen/images/petersonchrind.pdf}
+\caption{Chromatische Zahl und Unabhängigkeitszahl des Peterson-Graphen.
+Die chromatische Zahl ist $3$, da der Graph sich mit drei Farben einfärben
+lässt (links).
+Die Unabhängigkeitszahl ist $4$, die vier grösseren Knoten im rechten
+Graphen sind unabhängig.
+Die Farben der kleinen Knoten sind die additive Mischung der Farben
+der grossen Knoten, mit denen sie verbunden sind.
+\label{buch:graphen:fig:chrindpeterson}}
+\end{figure}
+
+\begin{beispiel}
+Der Peterson-Graph $P$ von Abbildung~\ref{buch:graphen:fig:chrindpeterson}
+hat chromatische Zahl $\operatorname{chr}P=3$ und unabhängigkeitszahl
+$\operatorname{ind}P=4$.
+Die Ungleichung von Satz~\ref{buch:satz:chrind} ist erfüllt, sogar als
+Ungleichung: $\operatorname{chr}P\cdot\operatorname{ind}P=3\cdot 4=12>10=n$.
+\end{beispiel}
+
+Nach Definition ist Unabhängigkeitszahl ein Mass für die Grösse einer
+unabhängigen Menge von Punkten.
+Der Beweis von Satz~\ref{buch:satz:chrind} zeigt, dass man sich die
+chromatische Zahl als ein Mass dafür, wieviele solche anabhängige 
+Mengen in einem Graphen untergebracht werden können.
+
+%
+% Chromatische Zahl und maximaler Grad
+%
+\subsection{Chromatische Zahl und maximaler Grad
+\label{buch:subsection:chr-und-maximaler-grad}}
+Wenn kein Knoten mehr als $d$ Nachbarn hat, dann reichen
+$d+1$ Farben immer, um diesen Knoten und seine Nachbarn einzufärben.
+Das heisst aber noch nicht, dass dann auch $d+1$ Farben zur
+Einfärbung des ganzen Graphen reichen.
+Genau dies garantiert jedoch der folgende Satz.
+
+\begin{definition}
+Der maximale Grad
+\(
+\max_{v\in V} \deg(v)
+\)
+wird mit $d$ bezeichnet.
+\end{definition}
+
+\begin{satz}
+\label{buch:graphen:satz:chrmaxgrad}
+Ist $G$ ein Graph mit maximalem Grad $d$, dann gilt 
+$\operatorname{chr}G \le d+1$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Wir führen den Beweis mit Hilfe von vollständiger Induktion nach der
+Anzahl Knoten eines Graphen.
+Ein Graph mit nur einem Knoten hat keine Kanten, der maximale Grad ist
+daher $0$ und $d+1=1$ Farbe reicht auch tatsächlich zur Einfärbung des
+einen Knotens.
+
+Wir nehmen jetzt an, die Behaupt sei für Graphen mit $n-1$ Knoten bereits
+bewiesen, ein Graph $G'$ mit $n-1$ Knoten und maximalem Grad $d'$ erfüllt
+also die Ungleichung $\operatorname{chr}G'\le d'+1$.
+
+Wir wählen jetzt einen beleibigen Knoten $v$ des Graphen $G$ und bilden
+den Graphen $G'$, der aus $G$ entsteht, indem man den Knoten $v$
+entfernt: $G'=G\setminus\{v\}$.
+Der maximale Grad $d'$ von $G'$ kann dabei nicht grösser werden, es ist
+also $d'\le d$.
+Da $G'$ genau $n-1$ Knoten hat, lässt er sich mit höchstens $d'+1\le d+1$
+Farben einfärben.
+Es muss jetzt also nur noch eine Farbe für den Knoten $v$ gefunden werden.
+Da $d$ der maximale Grad ist, hat $v$ höchstens $d$ Nachbarn, die höchstens
+$d$ verschiedene Farben haben können.
+Von den $d+1$ zur Verfügung stehenden Farben bleibt also mindestens eine
+übrig, mit der man den Knoten $v$ einfärben kann.
+Damit ist der Induktionsschritt gelungen und somit der Satz bewiesen.
+\end{proof}
+
+Das Argument im Beweis von Satz~\ref{buch:graphen:satz:chrmaxgrad}
+ist für alle Begriffe anwendbar, die sich bei der Bildung eines 
+Untergraphen auf ``monotone'' Art ändern.
+Die chromatische Zahl eines Untergraphen ist höchstens so gross wie die
+des ganzen Graphen. 
+Dann kann man eine Ungleichung für grosse Graphen schrittweise aus
+entsprechenden Ungleichungen für die kleineren Teilgraphen gewinnen.
+Ziel der folgenden Abschnitte ist zu zeigen, dass sich eine Grösse
+mit ähnlichen Eigenschaften aus dem Eigenwertspektrum der Adjazenzmatrix
+ablesen lässt.
+Daraus ergibt sich dann eine bessere Abschätzung der chromatischen Zahl
+eines Graphen.
+
+%
+% maximaler Eigenwert und maximaler Grad
+%
+\subsection{Maximaler Eigenwert von $A(G)$ und maximaler Grad
+\label{buch:subsection:maximaler-eigenwert}}
+Die Adjazenzmatrix $A(G)$ eines Graphen $G$  mit $n$ Knoten enthält unter
+anderem auch die Information über den Grad eines Knotens.
+Die Summe der Elemente einer Zeile oder einer Spalte ergibt einen Vektor,
+der die Grade der Knoten als Komponenten enthält.
+Ist $U$ ein $n$-dimensionaler Vektor aus lauter Einsen, dann ist
+ist $A(G)U$ ein Spaltenvektor bestehend aus den Zeilensummen der Matrix 
+$A(G)$ und
+$U^tA(G)$ ein Zeilenvektor bestehend aus den Spaltensummen.
+$A(G)U$ ist also der Vektor der Grade der Knoten.
+
+Das Skalarprodukt von $A(G)U$ mit $U$ ist die Summe der Grade.
+Somit ist
 \begin{equation}
-f(t)
+\frac{\langle A(G)U,U\rangle}{\langle U,U\rangle}
 =
-\sum_{i=1}^n \langle f_i,f\rangle f_i(t)
+\frac{1}{\langle U,U\rangle}\sum_{v\in V}\deg(v)
 =
-\sum_{i=1}^n \langle f_i,f\rangle e^{-\kappa\lambda_i t}f_i
-\label{buch:graphen:eqn:eigloesung}
+\frac{1}{n}(d_1+\dots+d_n)
+\label{buch:graphen:eqn:AUdavg}
 \end{equation}
-ableiten.
+der mittlere Grad, der mit $\overline{d}$ bezeichnet werden soll.
 
-\subsection{Beispiel: Ein zyklischer Graph}
-\begin{figure}
-\centering
-\includegraphics{chapters/70-graphen/images/kreis.pdf}
-\caption{Beispiel Graph zur Illustration der verschiedenen Basen auf einem
-Graphen.
-\label{buch:graphen:fig:kreis}}
-\end{figure}
-Wir illustrieren die im folgenden entwickelte Theorie an dem Beispielgraphen
-von Abbildung~\ref{buch:graphen:fig:kreis}.
-Besonders interessant sind die folgenden Funktionen:
+Da $A(G)$ eine symmetrische Matrix ist, ist $A(G)$ diagonalisierbar,
+die Eigenwerte sind also alle reell.
+Es ist ausserdem bekannt, dass der Eigenvektor $f$ zum grössten Eigenwert
+$\alpha_{\text{max}}$ von $A(G)$
+den Bruch
 \[
-\left.
+\frac{\langle A(G)f,f\rangle}{\langle f,f\rangle}
+\]
+für Vektoren $f\ne 0$ maximiert.
+Aus~\eqref{buch:graphen:eqn:AUdavg} folgt damit, dass
+\begin{equation}
+\overline{d}
+\le
+\alpha_{\text{max}}
+\label{buch:graphen:eqn:dqueramax}
+\end{equation}
+ist.
+
+In Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen}
+des nächsten Kapitels wird die Perron-Frobenius-Theorie positiver
+Matrizen vorgestellt, welche einer Reihe interessanter Aussagen
+über den betragsgrössten Eigenwert und den zugehörigen Eigenvektor
+macht.
+Die Adjazenz-Matrix ist eine nichtnegative Matrix und $\alpha_{\text{max}}$
+ist der grösste Eigenwert, also genau die Grösse, auf die die
+Sätze~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius}
+und \label{buch:wahrscheinlichkeit:satz:perron-frobenius2}
+anwendbar sind.
+Dazu muss die Matrix allerdings primitiv sein, was gleichbedeutend
+ist damit, dass der Graph zusammenhängend ist.
+Im folgenden soll dies daher jeweils angenommen werden.
+
+\begin{satz}
+Ist $G$ ein zusammenhänger Graph mit $n$ Knoten und maximalem Grad $d$,
+dann gilt
+\[
+\frac1n\sum_{v\in V} \deg(v) 
+=
+\overline{d}
+\le \alpha_{\text{max}} \le d.
+\]
+\end{satz}
+
+\begin{proof}[Beweis]
+Wir wissen aus \eqref{buch:graphen:eqn:dqueramax} bereits, dass
+$\overline{d}\le\alpha_{\text{max}}$ gilt, es bleibt also nur noch
+$\alpha_{\text{max}}\le d$ zu beweisen.
+
+Sei $f$ der Eigenvektor zum Eigenwert $\alpha_{\text{max}}$.
+Nach Satz~\label{buch:wahrscheinlichkeit:satz:perron-frobenius2}
+ist $f$ ein positiver Vektor mit der Eigenschaft $A(G)f=\alpha_{\text{max}}f$.
+Der Eigenvektor $f$ ist eine Funktion auf den Knoten des Graphen,
+die $v$-Komponente des Vektors $f$ für einen Vertex $v\in V$ ist $f(v)$.
+Die Eigenvektoreigenschaft bedeutet $(A(G)f)(v)=\alpha_{\text{max}} f(v)$.
+Die Adjazenzmatrix $A(G)$ enthält in Zeile $v$ Einsen genau für diejenigen
+Knoten $u\in V$, die zu $v$ benachbart sind.
+Schreiben wir $u\sim v$ für die Nachbarschaftsrelation, dann ist 
+\[
+(A(G)f)(v)
+=
+\sum_{u\sim v} f(u).
+\]
+Die Summe der Komponenten $A(G)f$ kann man erhalten durch Multiplikation
+von $A(G)f$ mit einem Zeilenvektor $U^t$ aus lauter Einsen, also
+\begin{equation}
 \begin{aligned}
-s_m(k)
+\sum_{v\in V}\sum_{u\sim v}f(v)
 &=
-\sin\frac{2\pi mk}{n}
+U^tA(G)f
+=
+(U^tA(G))f
+=
+\begin{pmatrix}d_1&d_2&\dots&d_n\end{pmatrix} f
 \\
-c_m(k)
 &=
-\cos\frac{2\pi mk}{n}
+\sum_{v\in V}\deg (v) f(v)
+\le
+\sum_{v\in V}df(v)
+=
+d
+\sum_{v\in V}f(v).
 \end{aligned}
-\;
-\right\}
-\quad
-\Rightarrow
-\quad
-e_m(k)
+\label{buch:graphen:eqn:sumkomp}
+\end{equation}
+Andererseits ist $A(G)f=\alpha_{\text{max}}f$, die linke Seite
+von~\eqref{buch:graphen:eqn:sumkomp} ist daher
+\begin{equation}
+\sum_{v\in V}\sum_{u\sim v}f(v)
 =
-e^{2\pi imk/n}
+U^tA(G)f
 =
-c_m(k) + is_m(k).
+\alpha_{\text{max}}
+U^tf
+=
+\alpha_{\text{max}} \sum_{v\in V}f(v).
+\label{buch:graphen:eqn:sumkomp2}
+\end{equation}
+Die Ungleichung~\eqref{buch:graphen:eqn:sumkomp}
+und die Gleichung~\eqref{buch:graphen:eqn:sumkomp2} ergeben zusammen
+die Ungleichung
+\[
+\alpha_{\text{max}} \sum_{v\in V}f(v)
+\le d\sum_{v\in V}f(v)
+\qquad\Rightarrow\qquad
+\alpha_{\text{max}} \le d,
 \]
-Das Skalarprodukt dieser Funktionen ist
+da die Summe der Komponenten des positiven Vektors $f$ nicht verschwinden
+kann.
+Damit ist die Ungleichung bewiesen.
+\end{proof}
+
+%
+% alpha_max eines Untergraphen
+%
+\subsection{$\alpha_{\text{max}}$ eines Untergraphen
+\label{buch:subsection:alphamax-eines-untergraphen}}
+Der grösste Eigenwert $\alpha_{\text{max}}$ ist ein potentieller 
+Anwärter für eine bessere Abschätzung der chromatischen Zahl.
+Bereits früher wurde bemerkt, dass dies auch bedeutet, dass man 
+das Verhalten des grössten Eigenwerts bei einem Übergang zu einem
+Untergraphen verstehen muss.
+
+\begin{satz}
+\label{buch:graphen:satz:amaxuntergraph}
+Sei $G'$ ein echter Untergraph von $G$ mit Adjazenzmatrix $A(G')$ und
+grösstem Eigenwert $\alpha_{\text{max}}'=\varrho(A(G'))$, dann ist
+$\alpha_{\text{max}}' \le \alpha_{\text{max}}$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Sei $f'$ der positive Eigenvektor zum Eigenwert $\alpha_{\text{max}}'$
+der Matrix $A(G')$.
+$f'$ ist definiert auf der Menge $V'$ der Knoten von $G'$.
+Aus $f'$ lässt sich ein Vektor $g$ mit den Werten
 \[
-\langle e_m, e_{m'}\rangle
+g(v)
 =
-\frac1n
-\sum_{k=1}^n
-\overline{e^{2\pi i km/n}}
-e^{2\pi ikm'/n}
-=
-\frac1n
-\sum_{k=1}^n
-e^{\frac{2\pi i}{n}(m'-m)k}
-=
-\delta_{mm'}
+\begin{cases}
+f'(v)&\qquad v\in V'\\
+    0&\qquad\text{sonst}
+\end{cases}
 \]
-Die Funktionen bilden daher eine Orthonormalbasis des Raums der
-Funktionen auf $G$.
-Wegen $\overline{e_m} = e_{-m}$ folgt, dass für gerade $n$
-die Funktionen
+konstruieren, der auf ganz $V$ definiert ist.
+
+Die Vektoren $f'$ und $g$ haben die gleichen Komponenten, also ist auch
+$\langle f',f'\rangle = \langle g,g\rangle$.
+Die Matrixelemente von $A(G')$ und $A(G)$ auf gemeinsamen Knoten $u,v\in V'$ 
+erfüllen $A(G')_{uv}\le A(G)_{uv}$, da jede Kante von $G'$ auch in $G$ ist.
+Daher gilt
 \[
-c_0, c_1,s_1,c_2,s_2,\dots c_{\frac{n}2-1},c_{\frac{n}2-1},c_{\frac{n}2}
+\langle A(G')f',f'\rangle
+\le
+\langle A(G)g,g\rangle,
 \]
-eine orthonormierte Basis.
+woraus sich die Ungleichung
+\[
+\alpha_{\text{max}}'
+=
+\frac{\langle A(G')f',f'\rangle}{\langle f',f'\rangle}
+=
+\frac{\langle A(G)g,g\rangle}{\langle g,g\rangle}
+\le
+\alpha_{\text{max}}
+\]
+ergibt, da $\alpha_{\text{max}}$ das Maximum von
+$\langle A(G)h,h\rangle/\langle h,h\rangle$ für alle Vektoren $h\ne 0$ ist.
+\end{proof}
 
+%
+% Der Satz von Wilf
+%
+\subsection{Chromatische Zahl und $\alpha_{\text{max}}$: Der Satz von Wilf
+\label{buch:subsection:chr-und-alpha-max}}
+Die in Satz~\ref{buch:graphen:satz:amaxuntergraph} beschriebene
+Eigenschaft von $\alpha_{\text{max}}$ beim Übergang zu einem Untergraphen
+ermöglich jetzt, eine besser Abschätzung für die chromatische Zahl
+zu finden.
 
-Die Laplace-Matrix kann mit der folgenden Definition zu einer linearen
-Abbildung auf Funktionen auf dem Graphen gemacht werden.
-Sei $f\colon V\to \mathbb{R}$ und $L$ die Laplace-Matrix mit
-Matrixelementen $l_{vv'}$ wobei $v,v'\in V$ ist.
-Dann definieren wir die Funktion $Lf$ durch
+\begin{satz}[Wilf]
+\label{buch:graphen:satz:wilf}
+Sie $G$ ein zusammenhängder Graph und $\alpha_{\text{max}}$ der grösste
+Eigenwert seiner Adjazenzmatrix. Dann gilt
 \[
-(Lf)(v)
-=
-\sum_{v'\in V} l_{vv'}f(v').
+\operatorname{chr}G\le \alpha_{\text{max}}+1.
 \]
+\end{satz}
 
-\subsection{Standardbasis und Eigenbasis
-\label{buch:subsection:standardbasis-und-eigenbasis}}
-Die einfachste Basis, aus der siche Funktionen auf dem Graphen linear
-kombinieren lassen, ist die Standardbasis.
-Sie hat für jeden Knoten $v$ des Graphen eine Basisfunktion mit den Werten
+\begin{proof}[Beweis]
+Wie der Satz~\ref{buch:graphen:satz:chrmaxgrad} kann auch der Satz von Wilf
+mit Hilfe von vollständiger Induktion über die Anzahl $n$ der Knoten
+bewiesen werden.
+
+Ein Graph mit nur einem Knoten hat die $0$-Matrix als Adjazenzmatrix,
+der maximale Eigenwert ist $\alpha_{\text{max}}=0$, und tatsächlich reicht
+$\alpha_{\text{max}}+1=1$ Farbe, um den einen Knoten einzufärben.
+
+Wir nehmen jetzt an, der Satz sei für Graphen mit $n-1$ Knoten bereits
+beweisen.
+Wir müssen dann zeigen, dass der Satz dann auch für Graphen mit $n$ Knoten
+gilt.
+
+Sei $v\in V$ ein Knoten minimalen Grades und $G'=G\setminus{v}$ der
+Untergraph, der entsteht, wenn der Knoten $v$ entfernt wird.
+Da $G'$ genau $n-1$ Knoten hat, gilt der Satz von Wilf für $G'$
+und daher kann $G'$ mit höchstens
 \[
-e_v\colon V\to\mathbb R:v'\mapsto \begin{cases}
-1\qquad&v=v'\\
-0\qquad&\text{sonst.}
-\end{cases}
+\operatorname{chr}G' \le 1 + \alpha_{\text{max}}'
 \]
+Farben eingefärbt werden.
+Nach Satz~\ref{buch:graphen:satz:amaxuntergraph} ist
+$\alpha_{\text{max}}'\le \alpha_{\text{max}}$,
+Also kann $G'$ mit höchstens $\alpha_{\text{max}}+1$ Farben eingefärbt werden.
+
+Da $v$ ein Knoten minimalen Grades ist, ist sein Grad
+$d(v)\le \overline{d}\le \alpha_{\text{max}}$.
+Die Nachbarn von $v$ haben also hächstens $\alpha_{\text{max}}$ verschiedene
+Farben, mit einer weiteren Farbe lässt sich also auch $G$ einfärben.
+Daraus folgt $\operatorname{chr}G\le \alpha_{\text{max}}+1$.
+\end{proof}
+
+\begin{figure}
+\centering
+\includegraphics{chapters/70-graphen/images/nine.pdf}
+\caption{Beispiel für einen Graphen, für den der
+Satz~\ref{buch:graphen:satz:wilf} von Wilf die bessere
+Abschätzung für die chromatische Zahl eines Graphen gibt als der
+maximale Grad.
+\label{buch:graphen:fig:wilfexample}}
+\end{figure}
+
+\begin{beispiel}
+Der Graph in Abbildung~\ref{buch:graphen:fig:wilfexample} 12 Kanten und 9
+Knoten, daher ist $\overline{d}\le \frac{24}{9}$.
+Der maximale Grad ist $4$ und durch explizite Rechnung mit Hilfe zum Beispiel
+von Octave ergibt, dass $\alpha_{\text{max}}\approx 2.9565$.
+Aus dem Satz von Wilf folgt, dass
+$\operatorname{chr}G\le \alpha_{\text{max}}+1$, und daraus ergibt sich
+$\operatorname{chr}G\le 3$.
+Tatsächlich ist die chromatische Zahl $\operatorname{chr}G=3$, da 
+der Graph mindestens ein Dreieck enthält.
+Der maximale Grad ist 4, somit gibt der
+Satz~\ref{buch:graphen:satz:chrmaxgrad}
+die Schranke 
+$\operatorname{chr}G\le 4+1=5$
+für die chromatische Zahl.
+Der Satz von Wilf ist also eine wesentliche Verbesserung, er liefert in
+diesem Fall den exakten Wert der chromatischen Zahl.
+\end{beispiel}
+
 
 
diff --git a/buch/chapters/70-graphen/waerme.tex b/buch/chapters/70-graphen/waerme.tex
new file mode 100644
index 0000000..e7fc023
--- /dev/null
+++ b/buch/chapters/70-graphen/waerme.tex
@@ -0,0 +1,184 @@
+%
+% waerme.tex
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Wärmeleitung auf einem Graphen
+\label{buch:section:waermeleitung-auf-einem-graphen}}
+Die Vektoren, auf denen die Laplace-Matrix operiert, können betrachtet
+werden als Funktionen, die jedem Knoten einen Wert zuordnen.
+Eine mögliche physikalische Interpretation davon ist die Temperaturverteilung
+auf dem Graphen.
+Die Kanten zwischen den Knoten erlauben der Wärmeenergie, von einem Knoten
+zu einem anderen zu fliessen.
+Je grösser die Temperaturdifferenz zwischen zwei Knoten ist, desto
+grösser ist der Wärmefluss und desto schneller ändert sich die Temperatur
+der beteiligten Knoten.
+Die zeitliche Änderung der Temperatur $T_i$ im Knoten $i$ ist proportional
+\[
+\frac{dT_i}{dt}
+=
+\sum_{\text{$j$ Nachbar von $i$}} \kappa (T_j-T_i)
+=
+-
+\kappa
+\biggl(
+d_iT_i
+-
+\sum_{\text{$j$ Nachbar von $i$}} T_j
+\biggr)
+\]
+Der Term auf der rechten Seite ist genau die Wirkung der 
+Laplace-Matrix auf dem Vektor $T$ der Temperaturen:
+\begin{equation}
+\frac{dT}{dt}
+=
+-\kappa L T.
+\label{buch:graphen:eqn:waermeleitung}
+\end{equation}
+Der Wärmefluss, der durch die
+Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} beschrieben
+wird, codiert ebenfalls wesentliche Informationen über den Graphen.
+Je mehr Kanten es zwischen verschiedenen Teilen eines Graphen gibt,
+desto schneller findet der Wärmeaustausch zwischen diesen Teilen
+statt.
+Die Lösungen der Wärmeleitungsgleichung liefern also Informationen 
+über den Graphen.
+
+\subsection{Eigenwerte und Eigenvektoren
+\label{buch:subsection:ein-zyklischer-graph}}
+Die Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} 
+ist eine lineare Differentialgleichung mit konstanten Koeffizienten,
+die mit der Matrixexponentialfunktion gelöst werden.
+Die Lösung ist
+\[
+f(t) = e^{-\kappa Lt}f(0).
+\]
+
+Die Berechnung der Lösung mit der Matrixexponentialreihe ist ziemlich
+ineffizient, da grosse Matrizenprodukte berechnet werden müssen.
+Da die Matrix $L$ symmetrisch ist, gibt es eine Basis aus 
+orthonormierten Eigenvektoren und die Eigenwerte sind reell.
+Wir bezeichnen die Eigenvektoren mit $f_1,\dots,f_n$  und die
+zugehörigen Eigenwerte mit $\lambda_i$.
+Die Funktion $f_i(t)= e^{-\kappa\lambda_it}f_i$ ist dann eine Lösung
+der Wärmeleitungsgleichung, denn die beiden Seiten
+\begin{align*}
+\frac{d}{dt}f_i(t)
+&=
+-\kappa\lambda_ie^{-\kappa\lambda_it}f_i
+=
+-\kappa\lambda_i f_i(t)
+\\
+-\kappa Lf_i(t)
+&=
+-\kappa e^{-\kappa\lambda_it} Lf_i
+=
+-\kappa e^{-\kappa\lambda_it} \lambda_i f_i
+=
+-\kappa \lambda_i f_i(t)
+\end{align*}
+von \eqref{buch:graphen:eqn:waermeleitung} stimmen überein.
+
+Eine Lösung der Wärmeleitungsgleichung zu einer beliebigen
+Anfangstemperaturverteilung $f$ kann durch Linearkombination aus 
+den Lösungen $f_i(t)$ zusammengesetzt werden.
+Dazu ist nötig, $f$ aus den Vektoren $f_i$ linear zu kombinieren.
+Da aber die $f_i$ orthonormiert sind, ist dies besonders einfach,
+die Koeffizienten sind die Skalarprodukte mit den Eigenvektoren:
+\[
+f=\sum_{i=1}^n \langle f_i,f\rangle f_i.
+\]
+Daraus kann man die allgmeine Lösungsformel
+\begin{equation}
+f(t)
+=
+\sum_{i=1}^n \langle f_i,f\rangle f_i(t)
+=
+\sum_{i=1}^n \langle f_i,f\rangle e^{-\kappa\lambda_i t}f_i
+\label{buch:graphen:eqn:eigloesung}
+\end{equation}
+ableiten.
+
+\subsection{Beispiel: Ein zyklischer Graph}
+\begin{figure}
+\centering
+\includegraphics{chapters/70-graphen/images/kreis.pdf}
+\caption{Beispiel Graph zur Illustration der verschiedenen Basen auf einem
+Graphen.
+\label{buch:graphen:fig:kreis}}
+\end{figure}
+Wir illustrieren die im folgenden entwickelte Theorie an dem Beispielgraphen
+von Abbildung~\ref{buch:graphen:fig:kreis}.
+Besonders interessant sind die folgenden Funktionen:
+\[
+\left.
+\begin{aligned}
+s_m(k)
+&=
+\sin\frac{2\pi mk}{n}
+\\
+c_m(k)
+&=
+\cos\frac{2\pi mk}{n}
+\end{aligned}
+\;
+\right\}
+\quad
+\Rightarrow
+\quad
+e_m(k)
+=
+e^{2\pi imk/n}
+=
+c_m(k) + is_m(k).
+\]
+Das Skalarprodukt dieser Funktionen ist
+\[
+\langle e_m, e_{m'}\rangle
+=
+\frac1n
+\sum_{k=1}^n
+\overline{e^{2\pi i km/n}}
+e^{2\pi ikm'/n}
+=
+\frac1n
+\sum_{k=1}^n
+e^{\frac{2\pi i}{n}(m'-m)k}
+=
+\delta_{mm'}
+\]
+Die Funktionen bilden daher eine Orthonormalbasis des Raums der
+Funktionen auf $G$.
+Wegen $\overline{e_m} = e_{-m}$ folgt, dass für gerade $n$
+die Funktionen
+\[
+c_0, c_1,s_1,c_2,s_2,\dots c_{\frac{n}2-1},c_{\frac{n}2-1},c_{\frac{n}2}
+\]
+eine orthonormierte Basis.
+
+
+Die Laplace-Matrix kann mit der folgenden Definition zu einer linearen
+Abbildung auf Funktionen auf dem Graphen gemacht werden.
+Sei $f\colon V\to \mathbb{R}$ und $L$ die Laplace-Matrix mit
+Matrixelementen $l_{vv'}$ wobei $v,v'\in V$ ist.
+Dann definieren wir die Funktion $Lf$ durch
+\[
+(Lf)(v)
+=
+\sum_{v'\in V} l_{vv'}f(v').
+\]
+
+\subsection{Standardbasis und Eigenbasis
+\label{buch:subsection:standardbasis-und-eigenbasis}}
+Die einfachste Basis, aus der siche Funktionen auf dem Graphen linear
+kombinieren lassen, ist die Standardbasis.
+Sie hat für jeden Knoten $v$ des Graphen eine Basisfunktion mit den Werten
+\[
+e_v\colon V\to\mathbb R:v'\mapsto \begin{cases}
+1\qquad&v=v'\\
+0\qquad&\text{sonst.}
+\end{cases}
+\]
+
+
diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex
index 9c88c08..ae065bc 100644
--- a/buch/chapters/70-graphen/wavelets.tex
+++ b/buch/chapters/70-graphen/wavelets.tex
@@ -103,22 +103,230 @@ aus der sich alle Vektoren linear kombinieren lassen, in der aber
 auch auf die für die Anwendung interessante Längenskala angepasste
 Funktionen gefunden werden können.
 
-\subsection{Wavelets und Frequenzspektrum}
-Eine Wavelet-Basis der Funktionen auf $\mathbb{R}$ zerlegt
+\subsection{Wavelets auf einem Graphen}
+Die Fourier-Theorie analysiert Funktionen nach Frequenzen, wobei die 
+zeitliche Position von interessanten Stellen der Funktion in der Phase
+der einzelnen Komponenten verschwindet.
+Die Lokalisierung geht also für viele praktische Zwecke verloren.
+Umgekehrt haben einzelne Ereignisse wie eine $\delta$-Funktion keine
+charakteristische Frequenz, sie sind daher im Frequenzraum überhaupt 
+nicht lokalisierbar.
+Die Darstellung im Frequenzraum und in der Zeit sind also extreme
+Darstellungen, entweder Frequenzlokalisierung oder zeitliche Lokalisierung
+ermöglichen, sich aber gegenseitig ausschliessen.
 
+\subsubsection{Dilatation}
+Eine Wavelet-Basis für die $L^2$-Funktionen auf $\mathbb{R}$ erlaubt
+eine Funktion auf $\mathbb{R}$ auf eine Art zu analysieren, die eine
+ungenaue zeitliche Lokalisierung bei entsprechend ungenauer
+Frequenzbestimmung ermöglicht.
+Ausserdem entstehen die Wavelet-Funktionen aus einer einzigen Funktion
+$\psi(t)$ durch Translation um $b$ und Dilatation mit dem Faktor $a$:
+\[
+\psi_{a,b}(t)
+=
+\frac{1}{\sqrt{|a|}} \psi\biggl(\frac{t-b}a\biggr)
+=
+T_bD_a\psi(t)
+\]
+in der Notation von \cite{buch:mathsem-wavelets}.
+Auf einem Graphen ist so eine Konstruktion grundsätzlich nicht möglich,
+da es darauf weder eine Translations- noch eine Streckungsoperation gibt.
+
+In der Theorie der diskreten Wavelet-Transformation ist es üblich, sich
+auf Zweierpotenzen als Streckungsfaktoren zu beschränken.
+Ein Gitter wird dadurch auf sich selbst abgebildet, aber auf einem
+Graphen gibt es keine Rechtfertigung für diese spezielle Wahl von
+Streckungsfaktoren mehr.
+Es stellt sich daher die Frage, ob man für eine beliebige Menge
+\(
+T= \{ t_1,t_2,\dots\} \}
+\)
+von Streckungsfaktoren eine Familie von Funktionen $\chi_j$ zu finden
+derart, dass man sich die $\chi_j$ in einem gewissen Sinn als aus
+$\chi_0$ durch Dilatation entstanden vorstellen kann.
 
-\subsection{Frequenzspektrum
-\label{buch:subsection:frequenzspektrum}}
-Die Fundamentallösung der Wärmeleitunsgleichung haben ein Spektrum, welches
-wie $e^{-k^2}$ gegen $0$ geht.
+Die Dilatation kann natürlich nicht von einer echten
+Dilatation im Ortsraum herstammen, aber man kann wenigstens versuchen, die
+Dilatation im Frequenzraum nachzubilden.
+Für Funktionen in $L^2(\mathbb{R})$ entspricht die Dilatation mit dem
+Faktor $a$ im Ortsraum der Dilatation mit dem Faktor $1/a$ im Frequenzraum:
+\[
+\widehat{D_af}(\omega) = D_{1/a}\hat{f}(\omega).
+\]
+\cite[Satz~3.14]{buch:mathsem-wavelets}.
+Es bleibt aber das Problem, dass sich auch die Skalierung im Frequenzraum
+nicht durchführen lässt, da auch das Frequenzspektrum des Graphen nur eine
+Menge von reellen Zahlen ohne innere algebraische Struktur ist.
+
+\subsubsection{Mutterwavelets}
+\begin{figure}
+\centering
+\includegraphics{chapters/70-graphen/images/gh.pdf}
+\caption{Lokalisierungsfunktion $g(\lambda)$ für die Dilatation (links).
+Die Dilatierten Funktionen $g_i=\tilde{D}_{1/a_i}g$ lokalisieren
+die Frequenzen jeweils um die Frequenzen $a_i$ im Frequenzraum.
+Der Konstante Vektor ist vollständig delokalisiert, die Funktion $h$
+in der rechten Abbildung entfernt die hohen Frequenzen und liefert Funktionen,
+die in der Umgebung eines Knotens wie die Konstante Funktion aussehen.
+\label{buch:graphs:fig:lokalisierung}}
+\end{figure}
+Das Mutter-Wavelet einer Wavelet-Analyse zeichnet definiert, in welchem Mass
+sich Funktionen im Orts- und im Frequenzraum lokalisieren lassen.
+Die Standardbasis der Funktionen auf einem Graphen repräsentieren die
+perfekte örtliche Lokalisierung, Eigenbasis der Laplace-Matrix repräsentiert
+die perfekte Lokalisierung im Frequenzraum.
+Sei $g(\lambda)\ge 0$ eine Funktion im Frequenzraum, die für  $\lambda\to0$ und
+$\lambda\to\infty$ rasch abfällt mit einem Maximum irgendwo dazwischen
+(Abbildung~\ref{buch:graphs:fig:lokalisierung}).
+Sie kann als eine Lokalisierungsfunktion im Frequenzraum betrachtet werden.
 
-Die Fundamentallösung entsteht dadurch, dass die hohen Frequenzen
-schneller dämpft als die tiefen Frequenzen.
+Die Matrix $g(I)$ bildet entfernt aus einer Funktion die ganz hohen und 
+die ganz tiefen Frequenz, lokalisiert also die Funktionen im Frequenzraum.
+Die Standardbasisvektoren werden dabei zu Funktionen, die nicht mehr nur
+auf einem Knoten von $0$ verschieden sind, aber immer noch einigermassen
+auf dem Graphen lokalisiert sind.
+Natürlich sind vor allem die Werte auf den Eigenwerten
+$\lambda_0 < \lambda_1\le \dots\le \lambda_n$ der Laplace-Matrix
+von Interesse.
 
+Die Matrix $g(I)$ kann mit Hilfe der Spektraltheorie berechnet werden,
+was im vorliegenden Fall naheliegend ist, weil ja die Eigenvektoren von
+der Laplace-Matrix bereits bekannt sind.
+Die Matrix $\chi^t$ bildet die Standardbasisvektoren in die
+Eigenbasis-Vektoren ab, also in eine Zerlegung im Frequenzraum ab,
+$\chi$ vermittelt die Umkehrabbildung.
+Mit der Spektraltheorie findet man für die Abbildung $g(I)$ die Matrix
+\begin{equation}
+g(I)
+=
+\chi
+\begin{pmatrix}
+g(\lambda_0)&0&\dots&0\\
+0&g(\lambda_1)&\dots&0\\
+\vdots&\vdots&\ddots&\vdots\\
+0&0&\dots&g(\lambda_n)
+\end{pmatrix}
+\chi^t.
+\label{buch:graphen:eqn:mutterwavelet}
+\end{equation}
 
-\subsection{Wavelet-Basen
-\label{buch:subsection:}}
+\subsubsection{Dilatation}
+Die Dilatation um $a$ im Ortsraum wird zu einer Dilatation um $1/a$ im
+Frequenzraum.
+Statt also nach einer echten Dilatation der Spaltenvektoren in $g(I)$
+zu suchen, kann man sich darauf verlegen, Funktionen zu finden, deren
+Spektrum von einer Funktionen lokalisiert worden ist, die eine Dilatation
+von $g$ ist.
+Man wählt daher eine ansteigende Folge $A=(a_1,\dots)$ von Streckungsfaktoren
+und betrachtet anstelle von $g$ die dilatierten Funktionen
+$g_i=\tilde{D}_{1/a_i}g$.
+Die zugehörigen Wavelet-Funktionen auf dem Graphen können wieder mit
+der Formel~\eqref{buch:graphen:eqn:mutterwavelet} berechnet werden,
+man erhält
+\begin{equation}
+\tilde{D}_{1/a_i}g(I)
+=
+g_i(I)
+=
+\chi
+\begin{pmatrix}
+g(a_i\lambda_0)&0&\dots&0\\
+0&g(a_i\lambda_1)&\dots&0\\
+\vdots&\vdots&\ddots&\vdots\\
+0&0&\dots&g(a_i\lambda_n)
+\end{pmatrix}
+\chi^t .
+\end{equation}
+Die Spalten von $g_i(I)$ bilden wieder eine Menge von Funktionen, die
+eine gemäss $g_i$ lokalisiertes Spektrum haben.
 
+\subsubsection{Vater-Wavelet}
+Wegen $g(0)=0$ wird die konstante Funktion, die Eigenvektor zum Eigenwert
+$\lambda_0=0$ ist, von den Abbildungen $g_i(I)$ auf $0$ abgebildet.
+Andererseits ist diese Funktion nicht lokalisiert, man möchte Sie also
+für die Analyse nicht unbedingt verwenden.
+Man wählt daher eine Funktion $h(\lambda)$ mit $h(0)=1$ so, dass
+für $\lambda\to \infty$ der Wert $h(\lambda)$ genügend rasch gegen $0$
+geht.
+Die Matrix $h(I)$ bildet daher den konstanten Vektor nicht auf $0$ ab,
+sondern lokalisiert ihn im Ortsraum.
+Wir erhalten daher in den Spalten von $h(I)$ Vektoren, die um die
+einzelnen Knoten lokalisiert sind.
+
+\subsubsection{Rekonstruktion}
+Die Operatoren $h(I)$ und $g_i(I)$ erzeugen analysieren eine Funktion
+nach den verschiedenen Frequenzen mit den Skalierungsfaktoren $a_i$,
+aber die Rekonstruktion ist noch nicht klar.
+Diese wäre einfacher, wenn die Operatoren zusammen die identische
+Abbildung ergäben, wenn also
+\[
+h(I) + \sum_{i}g_i(I)=I
+\]
+gelten würde.
+Nach der Spektraltheorie gilt das nur, wenn für alle Eigenwerte
+$\lambda_k$, $k=1,\dots,n$
+\[
+h(\lambda_k) + \sum_ig(a_i\lambda_k)=1
+\]
+gilt.
+Für beleibige Funktionen $g$ und $h$ kann man nicht davon ausgehen,
+aber man kann erwarten.
+Man muss daher zusätzlich verlangen, dass
+\[
+h(\lambda_k) + \sum_{i} g(a_i\lambda_k) > 0
+\]
+ist für alle Eigenwerte $\lambda_k$.
+
+\subsubsection{Frame}
+Die Menge von Vektoren, die in der vorangegangenen Konstruktion gefunden
+wurden, ist zu gross, um eine Basis zu sein.
+Vektoren lassen sich darin auf verschiedene Art darstellen.
+Wir verlangen aber auch keine eindeutige Darstellung, nur eine 
+Darstellung, in der wir die ``dominierenden'' Komponenten in jeder
+Frequenzskala identifizieren können.
+
+\begin{definition}
+\label{buch:graphen:def:frame}
+Ein Frame des Vektorraumes $\mathbb{R}^n$ ist eine Menge
+$F=\{e_k\;|\; k=1,\dots,N\}$ von Vektoren mit der Eigenschaft
+\begin{equation}
+A\|v\|^2
+\le
+\sum_{k=1}^N  |\langle v,e_k\rangle|^2
+\le
+B\|v\|^2
+\label{buch:graphen:eqn:frame}
+\end{equation}
+Die Zahlen $A$  und $B$ heissen die {\em Frame-Konstanten} des Frames.
+\end{definition}
+
+Die oben gefundenen Vektoren, die Spalten Vektoren von $h(I)$ und $g_i(I)$
+bilden daher ein Frame.
+Die Frame-Konstanten kann man unmittelbar ausrechnen.
+Der mittlere Term von \eqref{buch:graphen:eqn:frame} ist 
+\[
+\|h(I) v\|^2
++
+\sum_{i} \|g_i(I)v\|^2,
+\]
+die durch die Funktion
+\[
+f(\lambda)
+=
+h(\lambda)^2 + \sum_i g_i(\lambda)^2
+\]
+abgeschätzt werden kann.
+Die Frame-Konstanten sind daher
+\begin{align*}
+A&=\min_{k} f(\lambda_k)
+&
+&\text{und}&
+B&=\max_{k} f(\lambda_k).
+\end{align*}
+Die Konstruktion hat also ein Frame für die Funktionen auf dem Graphen
+etabliert, die viele Eigenschaften einer Multiskalenanalyse in diese
+wesentlich weniger symmetrische Situation rettet.
 
 
 
diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib
index a4579e7..a5d0201 100644
--- a/buch/chapters/references.bib
+++ b/buch/chapters/references.bib
@@ -21,6 +21,12 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc
 }
 
 
+@book{buch:mathsem-wavelets,
+	title = {Mathematisches Seminar Wavelets},
+	author = { Andreas M"uller and others },
+	year = {2019},
+}
+
 @book{buch:mathsem-dgl,
 	title = {Mathematisches Seminar Differentialgleichungen},
 	author = { Andreas M"uller and others },