diff options
Diffstat (limited to '')
-rw-r--r-- | buch/chapters/70-graphen/Makefile.inc | 1 | ||||
-rw-r--r-- | buch/chapters/70-graphen/beschreibung.tex | 2 | ||||
-rw-r--r-- | buch/chapters/70-graphen/chapter.tex | 1 | ||||
-rw-r--r-- | buch/chapters/70-graphen/images/Makefile | 53 | ||||
-rw-r--r-- | buch/chapters/70-graphen/images/fundamental.tex | 108 | ||||
-rw-r--r-- | buch/chapters/70-graphen/images/gh.pdf | bin | 0 -> 26177 bytes | |||
-rw-r--r-- | buch/chapters/70-graphen/images/gh.tex | 55 | ||||
-rw-r--r-- | buch/chapters/70-graphen/images/nine.pdf | bin | 0 -> 2136 bytes | |||
-rw-r--r-- | buch/chapters/70-graphen/images/nine.tex | 67 | ||||
-rw-r--r-- | buch/chapters/70-graphen/images/petersonchrind.pdf | bin | 0 -> 15217 bytes | |||
-rw-r--r-- | buch/chapters/70-graphen/images/petersonchrind.tex | 142 | ||||
-rw-r--r-- | buch/chapters/70-graphen/spektral.tex | 663 | ||||
-rw-r--r-- | buch/chapters/70-graphen/waerme.tex | 184 | ||||
-rw-r--r-- | buch/chapters/70-graphen/wavelets.tex | 458 |
14 files changed, 1334 insertions, 400 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 c1bc5df..5db54c8 100644 --- a/buch/chapters/70-graphen/images/Makefile +++ b/buch/chapters/70-graphen/images/Makefile @@ -1,22 +1,31 @@ -#
-# Makefile -- Bilder für Kapitel Graphen
-#
-# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
-#
-all: peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf fundamental.pdf
-
-peterson.pdf: peterson.tex
- pdflatex peterson.tex
-
-adjazenzu.pdf: adjazenzu.tex
- pdflatex adjazenzu.tex
-
-adjazenzd.pdf: adjazenzd.tex
- pdflatex adjazenzd.tex
-
-kreis.pdf: kreis.tex
- pdflatex kreis.tex
-
-fundamental.pdf: fundamental.tex
- pdflatex fundamental.tex
-
+# +# Makefile -- Bilder für Kapitel Graphen +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +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 + +adjazenzd.pdf: adjazenzd.tex + pdflatex adjazenzd.tex + +kreis.pdf: kreis.tex + pdflatex 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/fundamental.tex b/buch/chapters/70-graphen/images/fundamental.tex index 388bdf7..b7fe9c4 100644 --- a/buch/chapters/70-graphen/images/fundamental.tex +++ b/buch/chapters/70-graphen/images/fundamental.tex @@ -1,54 +1,54 @@ -%
-% fundamental.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]
-
-\begin{scope}[xshift=-4.6cm]
- \draw[color=red,line width=2pt] (1.8,0) -- (1.8,2);
- \draw[color=red,line width=2pt] (0,0) -- (4,0);
- \node at (1.8,0) [below] {$i$};
- \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}];
- \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}];
-
- \node at (2,-2.3) [below] {Standarbasis};
-\end{scope}
-
-\begin{scope}
- \draw[color=red,line width=1.4pt]
- plot[domain=0:360,samples=100] ({\x/90},{2*sin(\x)});
- \draw[color=blue,line width=1.4pt]
- plot[domain=0:360,samples=100] ({\x/90},{2*cos(\x)});
- \node[color=blue] at (1,-1) {$\Re f_i$};
- \node[color=red] at (2,1) {$\Im f_i$};
- \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}];
- \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}];
- \node at (2,-2.3) [below] {Eigenbasis};
-\end{scope}
-
-\begin{scope}[xshift=4.6cm]
- \foreach \t in {0.02,0.05,0.1,0.2,0.5}{
- \draw[color=red,line width=1.0pt]
- plot[domain=-1.8:2.2,samples=100]
- ({\x+1.8},{exp(-\x*\x/(4*\t))/(sqrt(4*3.1415*\t))});
- }
- \fill[color=red] (1.8,0) circle[radius=0.08];
- \node at (1.8,0) [below] {$\xi$};
- \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}];
- \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}];
- \node at (2,-2.3) [below] {Fundamentallösung};
-\end{scope}
-
-\end{tikzpicture}
-\end{document}
-
+% +% fundamental.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] + +\begin{scope}[xshift=-4.6cm] + \draw[color=red,line width=2pt] (1.8,0) -- (1.8,2); + \draw[color=red,line width=2pt] (0,0) -- (4,0); + \node at (1.8,0) [below] {$i$}; + \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}]; + \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}]; + + \node at (2,-2.3) [below] {Standarbasis}; +\end{scope} + +\begin{scope} + \draw[color=red,line width=1.4pt] + plot[domain=0:360,samples=100] ({\x/90},{2*sin(\x)}); + \draw[color=blue,line width=1.4pt] + plot[domain=0:360,samples=100] ({\x/90},{2*cos(\x)}); + \node[color=blue] at (1,-1) {$\Re f_i$}; + \node[color=red] at (2,1) {$\Im f_i$}; + \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}]; + \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}]; + \node at (2,-2.3) [below] {Eigenbasis}; +\end{scope} + +\begin{scope}[xshift=4.6cm] + \foreach \t in {0.02,0.05,0.1,0.2,0.5}{ + \draw[color=red,line width=1.0pt] + plot[domain=-1.8:2.2,samples=100] + ({\x+1.8},{exp(-\x*\x/(4*\t))/(sqrt(4*3.1415*\t))}); + } + \fill[color=red] (1.8,0) circle[radius=0.08]; + \node at (1.8,0) [below] {$\xi$}; + \draw[->] (-0.1,0) -- (4.3,0) coordinate[label={$x$}]; + \draw[->] (0,-2.1) -- (0,2.3) coordinate[label={right:$y$}]; + \node at (2,-2.3) [below] {Fundamentallösung}; +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/70-graphen/images/gh.pdf b/buch/chapters/70-graphen/images/gh.pdf Binary files differnew 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 Binary files differnew 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 Binary files differnew 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 72e3519..5fb3056 100644 --- a/buch/chapters/70-graphen/spektral.tex +++ b/buch/chapters/70-graphen/spektral.tex @@ -1,198 +1,465 @@ -%
-% spektral.tex
-%
-% (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
-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).
-\]
-
-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}
-\]
-
-
+% +% 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 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 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} + +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*} +V +&= +\bigcup_{\text{$f$ eine Farbe}} V_f +&&\Rightarrow& +n +&= +\sum_{\text{$f$ eine Farbe}} |V_f| +\\ +& +&&& +&\le +\sum_{\text{$f$ eine Farbe}} \operatorname{ind}G += +(\text{Anzahl Farben})\cdot \operatorname{ind}G += +\operatorname{chr}G \cdot \operatorname{ind}G. +\end{align*} +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} +\frac{\langle A(G)U,U\rangle}{\langle U,U\rangle} += +\frac{1}{\langle U,U\rangle}\sum_{v\in V}\deg(v) += +\frac{1}{n}(d_1+\dots+d_n) +\label{buch:graphen:eqn:AUdavg} +\end{equation} +der mittlere Grad, der mit $\overline{d}$ bezeichnet werden soll. + +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 +\[ +\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} +\sum_{v\in V}\sum_{u\sim v}f(v) +&= +U^tA(G)f += +(U^tA(G))f += +\begin{pmatrix}d_1&d_2&\dots&d_n\end{pmatrix} f +\\ +&= +\sum_{v\in V}\deg (v) f(v) +\le +\sum_{v\in V}df(v) += +d +\sum_{v\in V}f(v). +\end{aligned} +\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) += +U^tA(G)f += +\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, +\] +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 +\[ +g(v) += +\begin{cases} +f'(v)&\qquad v\in V'\\ + 0&\qquad\text{sonst} +\end{cases} +\] +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 +\[ +\langle A(G')f',f'\rangle +\le +\langle A(G)g,g\rangle, +\] +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. + +\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 +\[ +\operatorname{chr}G\le \alpha_{\text{max}}+1. +\] +\end{satz} + +\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 +\[ +\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 26a9e42..ef1520e 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -1,125 +1,333 @@ -%
-% wavelets.tex -- Wavelets auf Graphen
-%
-% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
-%
-\section{Wavelets auf Graphen
-\label{buch:section:wavelets-auf-graphen}}
-\rhead{Wavelets auf Graphen}
-In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis} wurde
-gezeigt dass die Standardbasis den Zusammenhang zwischen den einzelnen
-Teilen des Graphen völlig ignoriert, während die Eigenbasis Wellen
-beschreibt, die mit vergleichbarer Amplitude sich über den ganzen
-Graphen entsprechen.
-Die Eigenbasis unterdrückt also die ``Individualität'' der einzelnen
-Knoten fast vollständig.
-
-Wenn man einen Standardbasisvektor in einem Knoten $i$
-als Anfangstemperaturverteilung verwendet, erwartet man eine Lösung,
-die für kleine Zeiten $t$ die Energie immer in der Nähe des Knotens $i$
-konzentriert hat.
-Weder die Standardbasis noch die Eigenbasis haben diese Eigenschaft.
-
-\subsection{Vergleich mit der Wärmeleitung auf $\mathbb{R}$}
-Ein ähnliches Phänomen findet man bei der Wärmeausbreitung gemäss
-der partiellen Differentialgleichung
-\[
-\frac{\partial T}{\partial t} = -\kappa \frac{\partial^2 T}{\partial x^2}.
-\]
-Die von Fourier erfundene Methode, die Fourier-Theorie, verwendet die
-Funktionen $e^{ik x}$, die Eigenvektoren der zweiten Ableitung
-$\partial^2/\partial x^2$ sind.
-Diese haben das gleiche Problem, der Betrag von $e^{ikx}$ ist $1$, die
-Entfernung von einem Punkt spielt überhaupt keine Rolle.
-Die Funktion
-\[
-F(x,t)
-=
-\frac{1}{\sqrt{4\pi\kappa t}}e^{-x^2/4\kappa t}
-\]
-ist eine Lösung der Wärmeleitungsgleichung mit einem Maximum an
-der Stelle $0$.
-Sie heisst die Fundamentallösung der Wärmeleitungsgleichung.
-Durch Überlagerung von Translaten in eine Funktion
-\begin{equation}
-f(x,t)
-=
-\int_{-\infty}^\infty f(\xi) F(x-\xi,t)\,d\xi
-\label{buch:graphen:eqn:fundamentalueberlagerung}
-\end{equation}
-kann man die allgemeine Lösung aus Fundamentallösungen zusammensetzen.
-Die Fundamentallösungen $f(x-\xi,t)$ sind für kleine Zeiten immer noch
-deutlich in einer Umgebung von $\xi$ konzentriert.
-
-% XXX Ausbreitung der Fundamentallösung illustrieren
-\begin{figure}
-\centering
-\includegraphics{chapters/70-graphen/images/fundamental.pdf}
-\caption{Vergleich der verschiedenen Funktionenfamilien, mit denen
-Lösungenfunktionen durch Linearkombination erzeugt werden können.
-In der Standarbasis (links) ist es am einfachsten, die Funktionswerte
-abzulesen, in der Eigenbasis (Mitte) kann die zeitliche Entwicklung
-besonders leicht berechnet werden.
-Dazuwischen liegen die Fundamentallösungen (rechts), die eine einigermassen
-übersichtliche Zeitentwicklung haben, die Berechnung der Temperatur an
-einer Stelle $x$ zur Zeit $t$ ist aber erst durch das Integral
-\eqref{buch:graphen:eqn:fundamentalueberlagerung} gegeben.
-\label{buch:graphen:fig:fundamental}}
-\end{figure}
-
-\subsection{Fundamentallösungen auf einem Graphen}
-Die Wärmeleitungsgleichung auf einem Graphen kann für einen
-Standardbasisvektor mit Hilfe der
-Lösungsformel~\eqref{buch:graphen:eqn:eigloesung}
-gefunden werden.
-Aus physikalischen Gründen ist aber offensichtlich, dass die
-Wärmeenergie Fundamentallösungen $F_i(t)$ für kurze Zeiten $t$
-in der Nähe des Knoten $i$ konzentriert ist.
-Dies ist aber aus der expliziten Formel
-\begin{equation}
-F_i(t)
-=
-\sum_{j=1}^n \langle f_j,e_i\rangle e^{-\kappa \lambda_i t} f_j
-=
-\sum_{j=1}^n \overline{f}_{ji} e^{-\kappa \lambda_i t},
-\label{buch:graphen:eqn:fundamentalgraph}
-\end{equation}
-nicht unmittelbar erkennbar.
-
-Man kann aber aus~\eqref{buch:graphen:eqn:fundamentalgraph} ablesen,
-dass für zunehmende Zeit die hohen Frequenzen sehr schnell gedämpft
-werden.
-Die hohen Frequenzen erzeugen also den scharfen Peak für Zeiten nahe
-beim Knoten $i$, die zu kleineren $\lambda_i$ beschreiben die Ausbreitung
-über grössere Distanzen.
-Die Fundamentallösung interpoliert also in einem gewissen Sinne zwischen
-den Extremen der Standardbasis und der Eigenbasis.
-Die ``Interpolation'' geht von der Differentialgleichung aus,
-sie ist nicht einfach nur ein Filter, der die verschiedenen Frequenzen
-auf die gleiche Art bearbeitet.
-
-Gesucht ist eine Methode, eine Familie von Vektoren zu finden,
-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{Frequenzspektrum
-\label{buch:subsection:frequenzspektrum}}
-Die Fundamentallösung der Wärmeleitunsgleichung haben ein Spektrum, welches
-wie $e^{-k^2}$ gegen $0$ geht.
-
-Die Fundamentallösung entsteht dadurch, dass die hohen Frequenzen
-schneller dämpft als die tiefen Frequenzen.
-
-
-\subsection{Wavelet-Basen
-\label{buch:subsection:}}
-
-
-
-
-
+% +% wavelets.tex -- Wavelets auf Graphen +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Wavelets auf Graphen +\label{buch:section:wavelets-auf-graphen}} +\rhead{Wavelets auf Graphen} +In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis} wurde +gezeigt dass die Standardbasis den Zusammenhang zwischen den einzelnen +Teilen des Graphen völlig ignoriert, während die Eigenbasis Wellen +beschreibt, die mit vergleichbarer Amplitude sich über den ganzen +Graphen entsprechen. +Die Eigenbasis unterdrückt also die ``Individualität'' der einzelnen +Knoten fast vollständig. + +Wenn man einen Standardbasisvektor in einem Knoten $i$ +als Anfangstemperaturverteilung verwendet, erwartet man eine Lösung, +die für kleine Zeiten $t$ die Energie immer in der Nähe des Knotens $i$ +konzentriert hat. +Weder die Standardbasis noch die Eigenbasis haben diese Eigenschaft. + +\subsection{Vergleich mit der Wärmeleitung auf $\mathbb{R}$} +Ein ähnliches Phänomen findet man bei der Wärmeausbreitung gemäss +der partiellen Differentialgleichung +\[ +\frac{\partial T}{\partial t} = -\kappa \frac{\partial^2 T}{\partial x^2}. +\] +Die von Fourier erfundene Methode, die Fourier-Theorie, verwendet die +Funktionen $e^{ik x}$, die Eigenvektoren der zweiten Ableitung +$\partial^2/\partial x^2$ sind. +Diese haben das gleiche Problem, der Betrag von $e^{ikx}$ ist $1$, die +Entfernung von einem Punkt spielt überhaupt keine Rolle. +Die Funktion +\[ +F(x,t) += +\frac{1}{\sqrt{4\pi\kappa t}}e^{-x^2/4\kappa t} +\] +ist eine Lösung der Wärmeleitungsgleichung mit einem Maximum an +der Stelle $0$. +Sie heisst die Fundamentallösung der Wärmeleitungsgleichung. +Durch Überlagerung von Translaten in eine Funktion +\begin{equation} +f(x,t) += +\int_{-\infty}^\infty f(\xi) F(x-\xi,t)\,d\xi +\label{buch:graphen:eqn:fundamentalueberlagerung} +\end{equation} +kann man die allgemeine Lösung aus Fundamentallösungen zusammensetzen. +Die Fundamentallösungen $f(x-\xi,t)$ sind für kleine Zeiten immer noch +deutlich in einer Umgebung von $\xi$ konzentriert. + +% XXX Ausbreitung der Fundamentallösung illustrieren +\begin{figure} +\centering +\includegraphics{chapters/70-graphen/images/fundamental.pdf} +\caption{Vergleich der verschiedenen Funktionenfamilien, mit denen +Lösungenfunktionen durch Linearkombination erzeugt werden können. +In der Standarbasis (links) ist es am einfachsten, die Funktionswerte +abzulesen, in der Eigenbasis (Mitte) kann die zeitliche Entwicklung +besonders leicht berechnet werden. +Dazuwischen liegen die Fundamentallösungen (rechts), die eine einigermassen +übersichtliche Zeitentwicklung haben, die Berechnung der Temperatur an +einer Stelle $x$ zur Zeit $t$ ist aber erst durch das Integral +\eqref{buch:graphen:eqn:fundamentalueberlagerung} gegeben. +\label{buch:graphen:fig:fundamental}} +\end{figure} + +\subsection{Fundamentallösungen auf einem Graphen} +Die Wärmeleitungsgleichung auf einem Graphen kann für einen +Standardbasisvektor mit Hilfe der +Lösungsformel~\eqref{buch:graphen:eqn:eigloesung} +gefunden werden. +Aus physikalischen Gründen ist aber offensichtlich, dass die +Wärmeenergie Fundamentallösungen $F_i(t)$ für kurze Zeiten $t$ +in der Nähe des Knoten $i$ konzentriert ist. +Dies ist aber aus der expliziten Formel +\begin{equation} +F_i(t) += +\sum_{j=1}^n \langle f_j,e_i\rangle e^{-\kappa \lambda_i t} f_j += +\sum_{j=1}^n \overline{f}_{ji} e^{-\kappa \lambda_i t}, +\label{buch:graphen:eqn:fundamentalgraph} +\end{equation} +nicht unmittelbar erkennbar. + +Man kann aber aus~\eqref{buch:graphen:eqn:fundamentalgraph} ablesen, +dass für zunehmende Zeit die hohen Frequenzen sehr schnell gedämpft +werden. +Die hohen Frequenzen erzeugen also den scharfen Peak für Zeiten nahe +beim Knoten $i$, die zu kleineren $\lambda_i$ beschreiben die Ausbreitung +über grössere Distanzen. +Die Fundamentallösung interpoliert also in einem gewissen Sinne zwischen +den Extremen der Standardbasis und der Eigenbasis. +Die ``Interpolation'' geht von der Differentialgleichung aus, +sie ist nicht einfach nur ein Filter, der die verschiedenen Frequenzen +auf die gleiche Art bearbeitet. + +Gesucht ist eine Methode, eine Familie von Vektoren zu finden, +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 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. + +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 $L$ 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 Matrix $g(L)$ 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(L)$ 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(L)$ die Matrix +\begin{equation} +g(L) += +\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} + +\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(L)$ +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(L) += +g_i(L) += +\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(L)$ 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(L)$ 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(L)$ bildet daher den konstanten Vektor nicht auf $0$ ab, +sondern lokalisiert ihn im Ortsraum. +Wir erhalten daher in den Spalten von $h(L)$ Vektoren, die um die +einzelnen Knoten lokalisiert sind. + +\subsubsection{Rekonstruktion} +Die Operatoren $h(L)$ und $g_i(L)$ 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(L) + \sum_{i}g_i(L)=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(L)$ und $g_i(L)$ +bilden daher ein Frame. +Die Frame-Konstanten kann man unmittelbar ausrechnen. +Der mittlere Term von \eqref{buch:graphen:eqn:frame} ist +\[ +\|h(L) v\|^2 ++ +\sum_{i} \|g_i(L)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. + + + + |