Merge remote-tracking branch 'upstream/master'

13 files changed, 1098 insertions, 164 deletions

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.