zweite Lesung

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