abschnitt spektrale Graphentheorie

7 files changed, 434 insertions, 168 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/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..8f98134 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
 
 peterson.pdf:	peterson.tex
 	pdflatex peterson.tex
 
+petersonchrind.pdf:	petersonchrind.tex
+	pdflatex petersonchrind.tex
 adjazenzu.pdf:	adjazenzu.tex
 	pdflatex adjazenzu.tex
 
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..bc5c425 100644
--- a/buch/chapters/70-graphen/spektral.tex
+++ b/buch/chapters/70-graphen/spektral.tex
@@ -1,198 +1,133 @@
 %
-% 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.
+Eigenschaften dieser Matrizen zu studieren.
+Dieser Abschnitt soll diese Idee an dem ziemlich übersichtlichen Beispiel
+der chromatischen Zahl eines Graphen illustrieren.
 
-\subsection{Grapheigenschaften und Spektrum von $L$
-\label{buch:subsection:grapheigenschaften-und-spektrum-von-l}}
-TODO XXX 
+\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.
 
-\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.
+\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}
 
-\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).
-\]
+\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.
+Die Gesamtzahl der Knoten ist also
 \begin{align*}
-\frac{d}{dt}f_i(t)
+V
+&=
+\bigcup_{\text{$f$ eine Farbe}} V_f
+&&\Rightarrow&
+n
 &=
--\kappa\lambda_ie^{-\kappa\lambda_it}f_i
+\sum_{\text{$f$ eine Farbe}} |V_f| 
+\le
+\sum_{\text{$f$ eine Farbe}} \operatorname{ind}G
 =
--\kappa\lambda_i f_i(t)
+(\text{Anzahl Farben})\cdot \operatorname{ind}G
 \\
--\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)
+\operatorname{chr}G \cdot \operatorname{ind}G
 \end{align*}
-von \eqref{buch:graphen:eqn:waermeleitung} stimmen überein.
+Damit ist $n\le \operatorname{chr}G\cdot\operatorname{ind}G$ gezeigt.
+\qedhere
+\end{proof}
 
-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.
+\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}
 
-\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}}
+\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}
-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.
 
+\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}
 
-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').
-\]
+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 Grapehn untergebracht werden können.
+
+\subsection{Chromatische Zahl und maximaler Grad
+\label{buch:subsection:chr-und-maximaler-grad}}
+
+\subsection{Maximaler Eigenwert von $A(G)$ maximaler Grad
+\label{buch:subsection:maximaler-eigenwert}}
 
-\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}
-\]
+\subsection{$\alpha_{\text{max}}$ eines Untegraphen
+\label{buch:subsection:alphamax-eines-untergraphen}}
 
+\subsection{Chromatische Zahl und $\alpha_{\text{max}}$
+\label{buch:subsection:chr-und-alpha-max}}
 
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}
+\]
+
+