diff options
Diffstat (limited to 'buch/chapters/70-graphen')
-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 | 14 | ||||
-rw-r--r-- | buch/chapters/70-graphen/images/fundamental.pdf | bin | 0 -> 25976 bytes | |||
-rw-r--r-- | buch/chapters/70-graphen/images/fundamental.tex | 54 | ||||
-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 | 459 | ||||
-rw-r--r-- | buch/chapters/70-graphen/waerme.tex | 184 | ||||
-rw-r--r-- | buch/chapters/70-graphen/wavelets.tex | 394 |
15 files changed, 1273 insertions, 100 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 b42cbae..5db54c8 100644 --- a/buch/chapters/70-graphen/images/Makefile +++ b/buch/chapters/70-graphen/images/Makefile @@ -3,11 +3,14 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: peterson.pdf adjazenzu.pdf adjazenzd.pdf kreis.pdf +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 @@ -17,3 +20,12 @@ adjazenzd.pdf: 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.pdf b/buch/chapters/70-graphen/images/fundamental.pdf Binary files differnew file mode 100644 index 0000000..66b82ca --- /dev/null +++ b/buch/chapters/70-graphen/images/fundamental.pdf diff --git a/buch/chapters/70-graphen/images/fundamental.tex b/buch/chapters/70-graphen/images/fundamental.tex new file mode 100644 index 0000000..b7fe9c4 --- /dev/null +++ b/buch/chapters/70-graphen/images/fundamental.tex @@ -0,0 +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} + 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 9349f41..5fb3056 100644 --- a/buch/chapters/70-graphen/spektral.tex +++ b/buch/chapters/70-graphen/spektral.tex @@ -1,8 +1,465 @@ % -% spektral.tex +% spektral.tex -- spektrale Graphentheorie % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % \section{Spektrale Graphentheorie \label{buch:section:spektrale-graphentheorie}} \rhead{Spektrale Graphentheorie} +Die 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 0739f14..ef1520e 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -6,127 +6,327 @@ \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 +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 \[ -\langle f,g\rangle +\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}{|V|}\sum_{v\in V} \overline{f}(v) g(v) +\frac{1}{\sqrt{4\pi\kappa t}}e^{-x^2/4\kappa t} \] -Dies ist das bekannte Skalarprodukt der Vektoren mit Komponenten $f(v)$. +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/kreis.pdf} -\caption{Beispiel Graph zur Illustration der verschiedenen Basen auf einem -Graphen. -\label{buch:graphen:fig:kreis}} +\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} -\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) + +\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) = -e^{2\pi imk/n} +\sum_{j=1}^n \langle f_j,e_i\rangle e^{-\kappa \lambda_i t} f_j = -c_m(k) + is_m(k). -\] -Das Skalarprodukt dieser Funktionen ist +\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$: \[ -\langle e_m, e_{m'}\rangle +\psi_{a,b}(t) = -\frac1n -\sum_{k=1}^n -\overline{e^{2\pi i km/n}} -e^{2\pi ikm'/n} +\frac{1}{\sqrt{|a|}} \psi\biggl(\frac{t-b}a\biggr) = -\frac1n -\sum_{k=1}^n -e^{\frac{2\pi i}{n}(m'-m)k} -= -\delta_{mm'} +T_bD_a\psi(t) \] -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 +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: \[ -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} +\widehat{D_af}(\omega) = D_{1/a}\hat{f}(\omega). \] -eine orthonormierte Basis. -\end{beispiel} +\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 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) +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) = -\sum_{v'\in V} l_{vv'}f(v'). -\] +\chi +\begin{pmatrix} +g(\lambda_0)&0&\dots&0\\ +0&g(\lambda_1)&\dots&0\\ +\vdots&\vdots&\ddots&\vdots\\ +0&0&\dots&g(\lambda_n) +\end{pmatrix} +\chi^t. +\label{buch:graphen:eqn:mutterwavelet} +\end{equation} -\subsection{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 +\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 \[ -e_v\colon V\to\mathbb R:v'\mapsto \begin{cases} -1\qquad&v=v'\\ -0\qquad&\text{sonst.} -\end{cases} +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. -\subsection{Wavelet-Basen -\label{buch:subsection:wavelet-basen}} - +\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. |