Merge remote-tracking branch 'upstream/master'

1 files changed, 48 insertions, 25 deletions

diff --git a/buch/chapters/70-graphen/spektral.tex b/buch/chapters/70-graphen/spektral.tex
index 5fb3056..b718b65 100644
--- a/buch/chapters/70-graphen/spektral.tex
+++ b/buch/chapters/70-graphen/spektral.tex
@@ -6,7 +6,7 @@
 \section{Spektrale Graphentheorie
 \label{buch:section:spektrale-graphentheorie}}
 \rhead{Spektrale Graphentheorie}
-Die Adjazenz-Matrix, die Grad-Matrix und damit natürlich auch
+Die Adjazenzmatrix, die Gradmatrix 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
@@ -18,11 +18,11 @@ 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
+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.
+Noch etwas präziser kann diese Idee die mit Hilfe der 
+chromatischen Zahl und der Unabhängigkeitszahl erfasst werden.
 
 \begin{definition}
 Die {\em chromatische Zahl} $\operatorname{chr}G$ eines Graphen $G$ ist
@@ -39,9 +39,14 @@ ist die maximale Anzahl Knoten einer unabhängigen Menge.
 \index{Unabhängigkeitszahl}
 \end{definition}
 
+\begin{beispiel}
+Abbildung~\ref{buch:graphen:fig:chrindpeterson} bestimmt die chromatische
+Zahl und die Unabhängigkeitszahl im Beispiel des Peterson-Graphen.
+\end{beispiel}
+
 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
+Je mehr Verbindungen es im Graphen gibt, desto grösser wird die chromatische
 Zahl.
 Gleichzeitig wird es schwieriger für Mengen von Knoten, unabhängig zu sein.
 
@@ -53,7 +58,7 @@ $\operatorname{chr}G\cdot\operatorname{ind}G\ge n$.
 
 \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
+teilt die Knoten in $\operatorname{chr}G$ disjunkte 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,
@@ -109,16 +114,17 @@ der grossen Knoten, mit denen sie verbunden sind.
 
 \begin{beispiel}
 Der Peterson-Graph $P$ von Abbildung~\ref{buch:graphen:fig:chrindpeterson}
-hat chromatische Zahl $\operatorname{chr}P=3$ und unabhängigkeitszahl
+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
+Nach Definition ist die 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 
+chromatische Zahl als ein Mass dafür vorstellen kann,
+wieviele solche unabhängige 
 Mengen in einem Graphen untergebracht werden können.
 
 %
@@ -133,11 +139,13 @@ Einfärbung des ganzen Graphen reichen.
 Genau dies garantiert jedoch der folgende Satz.
 
 \begin{definition}
-Der maximale Grad
+Der {\em maximale Grad}
 \(
 \max_{v\in V} \deg(v)
 \)
+eines ungerichteten Graphen 
 wird mit $d$ bezeichnet.
+\index{maximaler Grad}%
 \end{definition}
 
 \begin{satz}
@@ -153,11 +161,11 @@ 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
+Wir nehmen jetzt an, die Behauptung 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
+Wir wählen jetzt einen beliebigen 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
@@ -177,7 +185,7 @@ 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
+Daher 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
@@ -210,7 +218,14 @@ Somit ist
 \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.
+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
+\[
+\overline{d}=\frac{2\cdot|E|}{|V|}
+\]
+berechnet werden.
+\index{mittlerer Grad}%
 
 Da $A(G)$ eine symmetrische Matrix ist, ist $A(G)$ diagonalisierbar,
 die Eigenwerte sind also alle reell.
@@ -232,20 +247,23 @@ ist.
 
 In Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen}
 des nächsten Kapitels wird die Perron-Frobenius-Theorie positiver
+\index{Perron-Frobenius-Theorie}%
+\index{positive Matrix}%
 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}}$
+Die Adjazenzmatrix 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}
+und \ref{buch:wahrscheinlichkeit:satz:perron-frobenius2}
 anwendbar sind.
 Dazu muss die Matrix allerdings primitiv sein, was gleichbedeutend
+\index{primitive Matrix}%
 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$,
+Ist $G$ ein zusammenhängender Graph mit $n$ Knoten und maximalem Grad $d$,
 dann gilt
 \[
 \frac1n\sum_{v\in V} \deg(v) 
@@ -266,8 +284,8 @@ 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.
+Die Adjazenzmatrix $A(G)$ enthält in Zeile $v$ genau für diejenigen
+Knoten $u\in V$ Einsen, die zu $v$ benachbart sind.
 Schreiben wir $u\sim v$ für die Nachbarschaftsrelation, dann ist 
 \[
 (A(G)f)(v)
@@ -278,9 +296,10 @@ 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)
+{\color{red}
+\sum_{v\in V}}\sum_{u\sim v}f(v)
 &=
-U^tA(G)f
+{\color{red}U^t}A(G)f
 =
 (U^tA(G))f
 =
@@ -356,7 +375,7 @@ f'(v)&\qquad v\in V'\\
 \]
 konstruieren, der auf ganz $V$ definiert ist.
 
-Die Vektoren $f'$ und $g$ haben die gleichen Komponenten, also ist auch
+Die Vektoren $f'$ und $g$ haben auf $V'$ 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.
@@ -385,6 +404,8 @@ $\langle A(G)h,h\rangle/\langle h,h\rangle$ für alle Vektoren $h\ne 0$ ist.
 %
 \subsection{Chromatische Zahl und $\alpha_{\text{max}}$: Der Satz von Wilf
 \label{buch:subsection:chr-und-alpha-max}}
+\index{Satz von Wilf}%
+\index{Wilf, Satz von}%
 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
@@ -407,13 +428,15 @@ 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.
+Dies ist die Induktionsverankerung.
 
-Wir nehmen jetzt an, der Satz sei für Graphen mit $n-1$ Knoten bereits
+Im Sinne der Induktionsannahme 
+nehmen wir 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
+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
@@ -443,7 +466,7 @@ maximale Grad.
 \end{figure}
 
 \begin{beispiel}
-Der Graph in Abbildung~\ref{buch:graphen:fig:wilfexample} 12 Kanten und 9
+Der Graph in Abbildung~\ref{buch:graphen:fig:wilfexample} hat 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$.