From d2fecb0eeb3854c999108aa224cdcd260bed7ef0 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 22 Feb 2021 20:41:15 +0100 Subject: =?UTF-8?q?Beispiele=20von=20Basen=20f=C3=BCr=20Wavelets=20auf=20G?= =?UTF-8?q?raphen?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/70-graphen/beschreibung.tex | 16 +++- buch/chapters/70-graphen/images/Makefile | 5 +- buch/chapters/70-graphen/images/kreis.pdf | Bin 0 -> 23540 bytes buch/chapters/70-graphen/images/kreis.tex | 47 +++++++++++ buch/chapters/70-graphen/wavelets.tex | 125 ++++++++++++++++++++++++++++++ 5 files changed, 190 insertions(+), 3 deletions(-) create mode 100644 buch/chapters/70-graphen/images/kreis.pdf create mode 100644 buch/chapters/70-graphen/images/kreis.tex (limited to 'buch/chapters/70-graphen') 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 Binary files /dev/null and b/buch/chapters/70-graphen/images/kreis.pdf differ 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}} + + + + + + -- cgit v1.2.1