Beispiele von Basen für Wavelets auf Graphen

5 files changed, 190 insertions, 3 deletions

diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex
index 70dc296..25cfcc0 100644
--- a/buch/chapters/70-graphen/beschreibung.tex
+++ b/buch/chapters/70-graphen/beschreibung.tex
@@ -134,7 +134,7 @@ Die {\em Länge} des Pfades $\gamma=(k_1,\dots,k_r)$ ist $|\gamma|=r$.
 \begin{figure}
 \centering
 \includegraphics{chapters/70-graphen/images/adjazenzu.pdf}
-\caption{Adjazenz- und Inzidenzmatrix eines ungerichteten
+\caption{Adjazenz-, Inzidenz- und Gradmatrix eines ungerichteten
 Graphen mit $5$ Knoten und $7$ Kanten.
 \label{buch:graphen:fig:adjazenzu}}
 \end{figure}
@@ -161,8 +161,16 @@ Die Adjazenzmatrix eines ungerichteten Graphen ist immer symmetrisch.
 Ein Beispiel ist in Abbildung~\ref{buch:graphen:fig:adjazenzu}
 dargestellt.
 
+\begin{figure}
+\centering
+\includegraphics{chapters/70-graphen/images/adjazenzd.pdf}
+\caption{Adjazenz-, Inzidenz- und Gradmatrix eines gerichteten
+Graphen mit $5$ Knoten und $7$ Kanten.
+\label{buch:graphen:fig:adjazenzd}}
+\end{figure}
 Die Adjazenzmatrix kann auch für einen gerichteten Graphen definiert
-werden.
+werden wie dies in in Abbildung~\ref{buch:graphen:fig:adjazenzu}
+illustriert ist.
 Ihre Einträge sind in diesem Fall definiert mit Hilfe der 
 gerichteten Kanten als
 \begin{equation}
@@ -334,6 +342,7 @@ Dies ist, was eine Beschriftung einer Kante bewerkstelligt.
 Eine Beschriftung mit Elementen der Menge $L$
 eines gerichteten oder ungerichteten Graphen $G=(V,E)$ 
 ist eine Abbildung $l\colon E\to L$.
+\index{Beschriftung}%
 \end{definition}
 
 \subsection{Inzidenzmatrix}
@@ -345,6 +354,7 @@ Buchstaben gehören, für die der Übergang entlang dieser Kante
 möglich ist.
 
 Die {\em Inzidenzmatrix} löst dieses Problem.
+\index{Inzidenzmatrix}%
 Dazu werden zunächst die Kanten numeriert $1,\dots,m$
 numeriert.
 Die Matrixeinträge
@@ -368,6 +378,7 @@ Knoten und eine Menge von beschrifteten Kanten der Form
 \[
 E \{ (a,b,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt von $a$ nach $b$}\}.
 \]
+Die Menge $L$ enthält die möglichen Beschriftungen der Kanten.
 \end{definition}
 
 Für einen gerichteten Graphen wird in der Inzidenzmatrix für
@@ -396,6 +407,7 @@ Die Adjazenzmatrix eines Graphen lässt sich also aus der
 Inzidenzmatrix berechnen.
 
 \subsubsection{Gradmatrix}
+\index{Gradmatrix}%
 Die Diagonale von $B(G)B(G)^t$ enthält die Werte
 \begin{align*}
 (B(G)B(G)^t)_{ii}
diff --git a/buch/chapters/70-graphen/images/Makefile b/buch/chapters/70-graphen/images/Makefile
index 529f314..b42cbae 100644
--- a/buch/chapters/70-graphen/images/Makefile
+++ b/buch/chapters/70-graphen/images/Makefile
@@ -3,7 +3,7 @@
 #
 # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
 #
-all:	peterson.pdf adjazenzu.pdf adjazenzd.pdf
+all:	peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf
 
 peterson.pdf:	peterson.tex
 	pdflatex peterson.tex
@@ -14,3 +14,6 @@ adjazenzu.pdf:	adjazenzu.tex
 adjazenzd.pdf:	adjazenzd.tex
 	pdflatex adjazenzd.tex
 
+kreis.pdf:	kreis.tex
+	pdflatex kreis.tex
+
diff --git a/buch/chapters/70-graphen/images/kreis.pdf b/buch/chapters/70-graphen/images/kreis.pdf
new file mode 100644
index 0000000..f7ed37a
--- /dev/null
+++ b/buch/chapters/70-graphen/images/kreis.pdf
diff --git a/buch/chapters/70-graphen/images/kreis.tex b/buch/chapters/70-graphen/images/kreis.tex
new file mode 100644
index 0000000..a926839
--- /dev/null
+++ b/buch/chapters/70-graphen/images/kreis.tex
@@ -0,0 +1,47 @@
+%
+% tikztemplate.tex -- template for standalon tikz images
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{mathtools}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\r{3}
+
+\foreach \w in {0,20,...,340}{
+	\draw (\w:\r) circle[radius=0.2];
+	\draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (\w:\r) -- ({\w+20}:\r);
+}
+
+\foreach \x in {1,...,15}{
+	\node at ({20*(\x-1)}:\r) {$\scriptstyle \x$};
+}
+\node at (340:\r) {$\scriptstyle n$};
+\node at (320:\r) {$\scriptstyle \dots$};
+\node at (300:\r) {$\scriptstyle \dots$};
+
+\begin{scope}[xshift=4cm]
+\node at (0,0) [right] {$\displaystyle
+L=\begin{pmatrix*}[r]
+ 2&-1& 0& 0&\dots& 0&-1\\
+-1& 2&-1& 0&\dots& 0& 0\\
+ 0&-1& 2&-1&\dots& 0& 0\\
+ 0& 0&-1& 2&\dots& 0& 0\\
+\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\
+ 0& 0& 0& 0&\dots& 2&-1\\
+-1& 0& 0& 0&\dots&-1& 2
+\end{pmatrix*}$};
+\end{scope}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex
index 6a4876a..0739f14 100644
--- a/buch/chapters/70-graphen/wavelets.tex
+++ b/buch/chapters/70-graphen/wavelets.tex
@@ -6,3 +6,128 @@
 \section{Wavelets auf Graphen
 \label{buch:section:wavelets-auf-graphen}}
 \rhead{Wavelets auf Graphen}
+Graphen werden oft verwendet um geometrische Objekte zu approximieren.
+Funktionen auf einem Graphen können dann Approximationen von physikalischen
+Grössen wie zum Beispiel der Temperatur auf dem geometrischen Objekt
+interpretiert werden.
+Verschiedene Basen für die Beschreibung solcher Funktionen sind im Laufe
+der Zeit verwendet worden, doch Wavelets auf einem Graphen sind eine
+neuere Idee, mit der man aus der Laplace-Matrix Basen gewinnen kann,
+die die Idee von langsam sich ausbreitenden Störungen besonders gut
+wiederzugeben in der Lage sind.
+
+In diesem Abschnitt werden erst Funktionen auf einem Graphen genauer
+definiert.
+In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis}
+wird die Eigenbasis mit dem Laplace-Operator konstruiert und mit
+der Standarbasis verglichen.
+Schliesslich werden in Abschnitt~\ref{buch:subsection:wavelet-basen}
+verschiedene Wavelet-Basen konstruiert.
+
+\subsection{Funktionen auf einem Graphen und die Laplace-Matrix}
+Sei $G$ ein Graph mit der Knotenmenge $V$.
+Eine Funktion $f$ auf einem Graphen ist eine Funktion $f\colon V\to\mathbb{R}$.
+Funktionen auf $G$ sind also Vektoren, die mit den Knoten $V$ indiziert
+sind.
+
+Es gibt auch ein Skalarprodukt für Funktionen auf dem Graphen.
+Sind $f$ und $g$ zwei Funktionen auf $G$, dann ist das Skalarprodukt
+definiert durch
+\[
+\langle f,g\rangle
+=
+\frac{1}{|V|}\sum_{v\in V} \overline{f}(v) g(v)
+\]
+Dies ist das bekannte Skalarprodukt der Vektoren mit Komponenten $f(v)$.
+
+\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}
+\begin{beispiel}
+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.
+\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').
+\]
+
+\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{Wavelet-Basen
+\label{buch:subsection:wavelet-basen}}
+
+
+
+
+
+