aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/70-graphen
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@ost.ch>2021-09-25 16:43:39 +0200
committerAndreas Müller <andreas.mueller@ost.ch>2021-09-25 16:43:39 +0200
commitf88b8071a623096f9004007ced8ec97195aaa218 (patch)
tree9fad214708204690b2f724459234d66ffde8d12b /buch/chapters/70-graphen
parentmore missing periods (diff)
downloadSeminarMatrizen-f88b8071a623096f9004007ced8ec97195aaa218.tar.gz
SeminarMatrizen-f88b8071a623096f9004007ced8ec97195aaa218.zip
zweite Lesung
Diffstat (limited to '')
-rw-r--r--buch/chapters/70-graphen/beschreibung.tex42
-rw-r--r--buch/chapters/70-graphen/chapter.tex5
-rw-r--r--buch/chapters/70-graphen/spektral.tex14
-rw-r--r--buch/chapters/70-graphen/waerme.tex15
-rw-r--r--buch/chapters/70-graphen/wavelets.tex24
5 files changed, 55 insertions, 45 deletions
diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex
index 845e640..5bae074 100644
--- a/buch/chapters/70-graphen/beschreibung.tex
+++ b/buch/chapters/70-graphen/beschreibung.tex
@@ -12,7 +12,7 @@ Zum Beispiel zeigt Kapitel~\ref{chapter:munkres}, wie man
ein Zuordnungsproblem als Graphenproblem formulieren kann.
Die Lösung erfolgt dann allerdings zweckmässigerweise unter
Verwendung einer Matrix.
-Ziel dieses Abschnitts ist, Graphen und ihre zugehörige Matrizen
+Ziel dieses Abschnitts ist, Graphen und ihre zugehörigen Matrizen
zu definieren und erste Eigenschaften des Graphen mit algebraischen
Mitteln abzuleiten.
Die Präsentation ist allerdings nur ein erster Einstieg, tiefer
@@ -37,7 +37,7 @@ Die Unterschiede zeigen sich in der Art und Weise, wie die Knoten
mit sogenannten Kanten
\index{Kante}%
verbunden werden.
-Bei einen ungerichteten Graphen sind die beiden Endpunkte einer Kante
+Bei einem ungerichteten Graphen sind die beiden Endpunkte einer Kante
gleichwertig, es gibt keine bevorzugte Reihenfolge oder Richtung der
Kante.
Eine Kante ist daher vollständig spezifiziert, wenn wir die
@@ -110,8 +110,8 @@ Ausderdem ist eine Kante $(a,a)$ wohldefiniert, also eine Kante, die vom
Knoten $a$ wieder zu $a$ zurück führt.
Man kann einen ungerichteten Graphen in einen gerichteten Graphen
-verwandeln, indem jede Kante $\{a,b\}$ durch zwei Kanten
-$(a,b)$ und $(b,a)$ ersetzt wird.
+verwandeln, indem jede Kante $\{u,v\}$ durch zwei Kanten
+$(u,v)$ und $(v,u)$ ersetzt wird.
Aus dem ungerichteten Graphen $(V,E)$ mit Knotenmenge $V$ und Kantenmenge
$E$ wird so der gerichtete Graph
$(V,E')$ mit der Kantenmenge
@@ -119,13 +119,13 @@ $(V,E')$ mit der Kantenmenge
E'
=
\{
-(a,e)
+(u,v)
\,|\,
-\{a,e\}\in E
+\{u,v\}\in E
\}.
\end{equation*}
Eine umgekehrte Zuordnung eines gerichteten zu einem ungerichteten
-Graphen ist nicht möglich, da eine ``Schleife'' $(a,a)$ nicht in eine Kante
+Graphen ist nicht möglich, da eine ``Schleife'' $(v,v)$ nicht in eine Kante
des ungerichteten Graphen abgebildet werden kann.
In einem gerichteten Graphen kann man sinnvoll von gerichteten Pfaden
@@ -224,8 +224,8 @@ enhält.
Die zugehörigen Matrixelemente schreiben wir $a_{ji}^{n}$ bzw.~$a_{ji}^{(n)}$.
Wir haben also zu zeigen, dass $A^n = A^{(n)}$.
-Wir beweisen, dass $A^n$ Pfade der Länge $n$ zählt, mit Hilfe von
-vollständiger Induktion.
+Wir beweisen mit Hilfe von vollständiger Induktion,
+dass $A^n$ Pfade der Länge $n$ zählt.
Es ist klar, dass $A^1$ die genannte Eigenschaft hat.
Der Fall $A^1$ dient daher als Induktionsverankerung.
@@ -233,7 +233,7 @@ Wir nehmen daher im Sinne einer Induktionsannahme an, dass bereits
bewiesen ist, dass das Element in Zeile
$j$ und Spalte $i$ von $A^{n-1}$ die Anzahl der Pfade der Länge $n-1$
zählt, dass also $A^{n-1}=A^{(n-1)}$.
-Dies ist die Induktionsannahme.
+%Dies ist die Induktionsannahme.
Wir bilden jetzt alle Pfade der Länge $n$ von $i$ nach $k$.
Ein Pfad der Länge besteht aus einem Pfad der Länge $n-1$, der von $i$ zu
@@ -294,7 +294,8 @@ sind.
\caption{Peterson-Graph mit zehn Knoten.
\label{buch:figure:peterson}}
\end{figure}
-Der Peterson-Graph hat die Adjazenzmatrix
+Der Peterson-Graph von Abbildung~\ref{buch:figure:peterson}
+hat die Adjazenzmatrix
\[
G
=
@@ -376,7 +377,7 @@ ist eine Abbildung $l\colon E\to L$.
\index{Beschriftung}%
\end{definition}
-Einen gerichteten, beschrifteten Graphen können wir gleichwertig
+Einen gerichteten, beschrifteten Graphen können wir
statt mit einer Beschriftungsabbildung $l$ auch dadurch erhalten,
dass wir Kanten als Tripel betrachten, die ausser den Knoten auch
noch den Wert der Beschriftung enthalten.
@@ -386,12 +387,12 @@ noch den Wert der Beschriftung enthalten.
Ein gerichteter Graph mit beschrifteten Kanten ist eine Menge $V$ von
Knoten und eine Menge von beschrifteten Kanten der Form
\[
-E \{ (a,b,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt von $a$ nach $b$}\}.
+E \{ (u,v,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt von $u$ nach $v$}\}.
\]
Die Menge $L$ enthält die möglichen Beschriftungen der Kanten.
\end{definition}
-Diese Definition gestattet, dass zwischen zwei Knoten $a$ und $e$
+Diese Definition gestattet, dass zwischen zwei Knoten $u$ und $v$
mehrere Kanten vorhanden sind, die sich durch die Beschriftung
unterscheiden.
@@ -492,13 +493,13 @@ negativ.
\subsubsection{Anwendung: Netlist}
Eine natürliche Anwendung eines gerichteten und beschrifteten Graphen
-ist eine eletronische Schaltung.
+ist eine elektronische Schaltung.
Die Knoten des Graphen sind untereinander verbundene Leiter, sie werden
auch {\em nets} genannt.
Die beschrifteten Kanten sind die elektronischen Bauteile, die solche
-Nets miteinander verbinden.
+nets miteinander verbinden.
Die Inzidenzmatrix beschreibt, welche Anschlüsse eines Bauteils mit
-welchen Nets verbunden werden müssen.
+welchen nets verbunden werden müssen.
Die Informationen in der Inzidenzmatrix werden also in einer
Applikation zum Schaltungsentwurf in ganz natürlicher Weise erhoben.
@@ -547,9 +548,10 @@ $L(G)=B(G')B(G')^t$ nach \eqref{buch:graphen:eqn:gradmatrix} genau
die Elemente der Gradmatrix $D(G)$.
Die ausserdiagonalen Elemente sind nach
\eqref{buch:graphen:eqn:ausserdiagonal}
-genau dann, wenn es in $G$ eine Verbindung zwischen den beiden Knoten
-gibt.
-Dies sind die Elemente von $-A(G)$.
+genau dann von $0$ verschieden, wenn es in $G$ eine Verbindung zwischen
+den beiden Knoten gibt.
+Im Produkt $B(G')B(G')^t$ summieren sie sich zu den ausserdiagonalen
+Elementen von $-A(G)$.
Damit ist die Formel
\eqref{buch:graphen:eqn:laplace-definition}
nachgewiesen.
diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex
index 1fb61b6..14240f4 100644
--- a/buch/chapters/70-graphen/chapter.tex
+++ b/buch/chapters/70-graphen/chapter.tex
@@ -22,8 +22,7 @@ Die Bedeutung des Graphenkozeptes wird unterstrichen von der Vielzahl
von Fragestellungen, die über Graphen gestellt worden sind, und der
zugehörigen Lösungsalgorithmen, die zu ihrer Beantwortung gefunden
worden sind.
-Die Komplexitätstheorie hat sogar gezeigt, dass sich jedes diskrete
-\index{Komplexitätstheorie}%
+Die Komplexitätstheorie hat sogar gezeigt, dass sich jedes NP-vollständige
Problem in ein Graphenproblem umformulieren lässt.
\index{Komplexitätstheorie}%
@@ -46,7 +45,7 @@ ins gleiche Zeitintervall geplant werden.
Das zugehörige abstrakte Graphenproblem heisst das Färbeproblem:
\index{Färbeproblem}%
ist es möglich, mit einer beschränkten Anzahl von Farben, oder im
-vorliegenden Fall Zeitintervalle, die Knoten
+vorliegenden Fall Zeitintervallen, die Knoten
des Graphen so einzufärben, dass benachbarte Knoten niemals die gleiche
Farbe haben.
diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex
index b718b65..9767c71 100644
--- a/buch/chapters/70-graphen/spektral.tex
+++ b/buch/chapters/70-graphen/spektral.tex
@@ -26,7 +26,7 @@ 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
+die minimale Anzahl von Farben, die zum Einfärben der Knoten eines Graphen
nötig sind, sodass benachbarte Knoten verschiedene Farben haben.
\index{chromatische Zahl}
\end{definition}
@@ -158,7 +158,7 @@ $\operatorname{chr}G \le d+1$.
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
+daher $d=0$ und $d+1=1$ Farbe reicht auch tatsächlich zur Einfärbung des
einen Knotens.
Wir nehmen jetzt an, die Behauptung sei für Graphen mit $n-1$ Knoten bereits
@@ -220,7 +220,7 @@ Somit ist
\end{equation}
der {\em mittlere Grad}, der mit $\overline{d}$ bezeichnet werden soll.
Da die Kanten eines Graphen zusammen $2\cdot|E|$ Enden haben, kann
-er kann auch als
+er auch als
\[
\overline{d}=\frac{2\cdot|E|}{|V|}
\]
@@ -257,7 +257,9 @@ ist der grösste Eigenwert, also genau die Grösse, auf die die
Sätze~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius}
und \ref{buch:wahrscheinlichkeit:satz:perron-frobenius2}
anwendbar sind.
-Dazu muss die Matrix allerdings primitiv sein, was gleichbedeutend
+Dazu muss die Matrix allerdings primitiv sein
+(Definition~\ref{buch:positiv:def:primitiv} in Kapitel~\ref{buch:chapter:wahrscheinlichkeit}),
+was gleichbedeutend
\index{primitive Matrix}%
ist damit, dass der Graph zusammenhängend ist.
Im folgenden soll dies daher jeweils angenommen werden.
@@ -292,8 +294,8 @@ Schreiben wir $u\sim v$ für die Nachbarschaftsrelation, dann ist
=
\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
+Die Summe der Komponenten $A(G)f$ kann man durch Multiplikation
+von $A(G)f$ mit einem Zeilenvektor $U^t$ aus lauter Einsen erhalten, also
\begin{equation}
\begin{aligned}
{\color{red}
diff --git a/buch/chapters/70-graphen/waerme.tex b/buch/chapters/70-graphen/waerme.tex
index bfeff74..ac49880 100644
--- a/buch/chapters/70-graphen/waerme.tex
+++ b/buch/chapters/70-graphen/waerme.tex
@@ -5,6 +5,7 @@
%
\section{Wärmeleitung auf einem Graphen
\label{buch:section:waermeleitung-auf-einem-graphen}}
+\rhead{Wärmeleitung auf einem Graphen}
Die Vektoren, auf denen die Laplace-Matrix operiert, können
als Funktionen betrachtet werden, die jedem Knoten einen Wert zuordnen.
Eine mögliche physikalische Interpretation davon ist die Temperaturverteilung
@@ -44,8 +45,6 @@ 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}}
@@ -165,13 +164,13 @@ s_k(l)
&=
\sin\frac{2\pi kl}{n}
=
-\Im \chi_k(l)
+\Im \chi_k(l),
\\
c_k(l)
&=
\cos\frac{2\pi kl}{n}
=
-\Re\chi_k(l)
+\Re\chi_k(l).
\end{aligned}
\]
Das Skalarprodukt dieser Funktionen ist
@@ -189,14 +188,16 @@ e^{\frac{2\pi i}{n}(m'-m)l}
=
\delta_{mm'}
\]
-Die Funktionen bilden daher eine Orthonormalbasis des Raums der
-Funktionen auf $G$.
+Die Funktionen bilden daher eine Orthonormalbasis des komplexen
+Vektorraums der
+komplexen Funktionen auf $G$ mit dem sesquilinearen Skalarprodut.
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.
+eine orthonormierte Basis des reellen Vektorraumes der reellen Funktionen
+auf $G$ mit dem gewöhnlichen Skalarprodukt.
\subsection{Standardbasis und Eigenbasis
\label{buch:subsection:standardbasis-und-eigenbasis}}
diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex
index 073deab..c453eb9 100644
--- a/buch/chapters/70-graphen/wavelets.tex
+++ b/buch/chapters/70-graphen/wavelets.tex
@@ -18,7 +18,11 @@ 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.
+Es werden daher mit der Zeit immer stärkere benachbarte Standardbasisvektoren
+in der Lösung auftreten.
+Auch die Eigenbasis hilft nicht, dieses Lösungsverhalten aufzuzeigen:
+sie sind im Definitionsgebiet stark delokalisiert und daher die allmählich
+abnehmende Lokalisierung der Lösung nicht wiedergeben.
\subsection{Vergleich mit der Wärmeleitung auf $\mathbb{R}$}
Ein ähnliches Phänomen findet man bei der Wärmeausbreitung gemäss
@@ -29,7 +33,7 @@ der partiellen Differentialgleichung
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
+Diese haben das gleiche Problem: Der Betrag von $e^{ikx}$ ist $1$, die
Entfernung von einem Punkt spielt überhaupt keine Rolle.
Die Funktion
\[
@@ -90,7 +94,7 @@ wenigstens 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
+beim Knoten $i$, die 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.
@@ -142,7 +146,7 @@ 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
+von Streckungsfaktoren eine Familie von Funktionen $\chi_j$ finden
derart, dass man sich die $\chi_j$ in einem gewissen Sinn als aus
$\chi_0$ durch Dilatation entstanden vorstellen kann.
@@ -174,8 +178,8 @@ die in der Umgebung eines Knotens wie die konstante Funktion aussehen.
Das Mutter-Wavelet einer Wavelet-Analyse 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.
+perfekte örtliche Lokalisierung, die 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}).
@@ -190,11 +194,13 @@ 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,
+Die Matrix $g(L)$ kann mit Hilfe der Spektraltheorie
+von Abschnitt~\ref{buch:section:spektraltheorie}
+berechnet werden,
was im vorliegenden Fall naheliegend ist, weil ja die Eigenvektoren
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,
+Eigenbasis-Vektoren ab, also in eine Zerlegung im Frequenzraum,
$\chi$ vermittelt die Umkehrabbildung.
Mit der Spektraltheorie findet man für die Abbildung $g(L)$ die Matrix
\begin{equation}
@@ -255,7 +261,7 @@ 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
+Die Operatoren $h(L)$ und $g_i(L)$ 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