Kapitel 8.1-8.3

8 files changed, 272 insertions, 172 deletions

diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex
index a0f46da..918594d 100644
--- a/buch/chapters/70-graphen/beschreibung.tex
+++ b/buch/chapters/70-graphen/beschreibung.tex
@@ -6,16 +6,21 @@
 \section{Beschreibung von Graphen mit Matrizen
 \label{buch:section:beschreibung-von-graphen-mit-matrizen}}
 \rhead{Beschreibung mit Matrizen}
-Ein Graph ist eine Menge von Knoten, die untereinander mit Kanten
-verbunden sind.
-Graphen können zum Beispiel verwendet werden um Netzwerke zu beschreiben,
-aber auch viele andere Datenstrukturen.
-Die Knoten können einzelne Objekte beschreiben, die Kanten beschreiben
-dann Beziehungen zwischen diesen Objekten.
+Als universelles kombinatorisches Modell sind Graphen für eine
+Vielzahl von Problemlösungen interessant.
+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
+zu definieren und erste Eigenschaften des Graphen mit algebraischen
+Mitteln abzuleiten.
+Die Präsentation ist allerdings nur ein erster Einstieg, tiefer
+gehende Information kann in \cite{skript:brualdi} gefunden werden.
 
 \subsection{Definition von Graphen
 \label{subsection:definition-von-graphen}}
-In der Einleitung zu diesem Abschnitt wurde bereits eine informelle
+In der Einleitung wurde bereits eine informelle
 Beschreibung des Konzeptes eines Graphen gegeben.
 Um zu einer Beschreibung mit Hilfe von Matrizen zu kommen,
 wird eine exakte Definition benötigt.
@@ -25,7 +30,7 @@ sind und sich in Unterschieden in der Definition der zugehörigen Matrix
 
 \subsubsection{Ungerichtete Graphen}
 Die Grundlage für alle Arten von Graphen ist eine Menge $V$ von {\em Knoten},
-auch {\em Vertices} genannt.
+auch {\em Vertizes} genannt.
 \index{Knoten}%
 \index{Vertex}%
 Die Unterschiede zeigen sich in der Art und Weise, wie die Knoten
@@ -35,7 +40,7 @@ verbunden werden.
 Bei einen ungerichteten Graphen sind die beiden Endpunkte einer Kante
 gleichwertig, es gibt keine bevorzugte Reihenfolge oder Richtung der
 Kante.
-Eine Kante wird daher vollständig spezifiziert, wenn wir die
+Eine Kante ist daher vollständig spezifiziert, wenn wir die
 Menge der Endpunkte kennen.
 Dies führt auf die folgende Definition eines ungerichteten Graphen.
 
@@ -48,14 +53,16 @@ und eine Menge $E$ von zweielementigen Teilmengen
 \[
 E \subset \{\, \{a,b\}\subset V\,|\, a\ne b\}.
 \]
-Die Elemente von $E$ heissen {\em Kanten} ({\em edges}).
+Die Elemente von $E$ heissen {\em Kanten} (edges).
 \end{definition}
 
 Man beachte, dass es keine Kante gibt, die einen Knoten $a\in V$
 mit sich selbst verbindet, da die zugehörige Menge $\{a,a\}=\{a\}$
 nicht aus zwei verschiedenen Elementen besteht, wie die
 Definition~\ref{buch:def:ungerichteter-graph} dies verlangt.
+Es gibt also keine Schleifen an einem Knoten.
 
+\begin{beispiel}
 Ein elektrisches Netzwerk von ohmschen Widerständen kann mit Hilfe
 eines ungerichteten Graphen beschrieben werden.
 Ohmsche Widerstände hängen nicht von der Richtung des Stromflusses
@@ -67,6 +74,7 @@ Die Endpunkte solcher Widerstände wären immer auf dem gleichen Potential.
 Folglich würde kein Strom fliessen und sie hätten keinen Einfluss auf
 das Verhalten des Netzwerkes.
 Sie können einfach weggelassen werden.
+\end{beispiel}
 
 \subsubsection{Gerichtete Graphen}
 In vielen Anwendungen sind die Endpunkte einer Kante nicht austauschbar.
@@ -95,15 +103,15 @@ Der Knoten $a(k)$ heisst der {\em Anfangspunkt} der Kante $k\in E$,
 $e(k)$ heisst der {\em Endpunkt}.
 \end{definition}
 
-In einem gerichteten Graphen gehört also zu jeder Kante auch eine Richtung
-und die Unterscheidung von Anfangs- und Endpunkt einer Kante ist sinnvoll
+In einem gerichteten Graphen gehört also zu jeder Kante auch eine Richtung.
+Die Unterscheidung von Anfangs- und Endpunkt einer Kante ist sinnvoll
 geworden.
 Ausderdem ist eine Kante $(a,a)$ wohldefiniert, also eine Kante, die vom
-Knoten $a$ wieder zu $a$ zurückführt.
+Knoten $a$ wieder zu $a$ zurück führt.
 
 Man kann einen ungerichteten Graphen in einen gerichteten Graphen
-verwandeln, indem wir jede Kante $\{a,b\}$ durch zwei Kanten 
-$(a,b)$ und $(b,a)$ ersetzen.
+verwandeln, indem jede Kante $\{a,b\}$ durch zwei Kanten 
+$(a,b)$ und $(b,a)$ ersetzt wird.
 Aus dem ungerichteten Graphen $(V,E)$ mit Knotenmenge $V$ und Kantenmenge
 $E$ wird so der gerichtete Graph
 $(V,E')$ mit der Kantenmenge
@@ -130,12 +138,12 @@ Dies bedeutet, dass der Endpunkt jeder Kante mit dem Anfangspunkt der
 nachfolgenden Kante übereinstimmt.
 Die {\em Länge} des Pfades $\gamma=(k_1,\dots,k_r)$ ist $|\gamma|=r$.
 
-\subsubsection{Adjazenzmatrix}
+\subsection{Adjazenzmatrix}
 \begin{figure}
 \centering
 \includegraphics{chapters/70-graphen/images/adjazenzu.pdf}
 \caption{Adjazenz-, Inzidenz- und Gradmatrix eines ungerichteten
-Graphen mit $5$ Knoten und $7$ Kanten.
+Graphen mit fünf Knoten und sieben Kanten.
 \label{buch:graphen:fig:adjazenzu}}
 \end{figure}
 Eine naheliegende Beschreibung eines Graphen mit Hilfe einer
@@ -146,13 +154,13 @@ Diese Zahlen werden dann als Zeilen- uns Spaltenindizes interpretiert.
 Die zum Graphen gehörige sogenannte {\em Adjazenzmatrix} $A(G)$
 enthält die Einträge
 \begin{equation}
-a_{ij}
+a_{i\!j}
 =
 \begin{cases}
 1&\qquad  \{j,i\} \in E\\
 0&\qquad  \text{sonst.}
 \end{cases}
-\label{buch:graphen:eqn:linkmatrix}
+\label{buch:graphen:eqn:adjazenzmatrix}
 \end{equation}
 Die Matrix hat also genau dann einen von Null verschiedenen Eintrag
 in Zeile $i$ und Spalte $j$, wenn die beiden Knoten $i$ und $j$
@@ -165,24 +173,27 @@ dargestellt.
 \centering
 \includegraphics{chapters/70-graphen/images/adjazenzd.pdf}
 \caption{Adjazenz-, Inzidenz- und Gradmatrix eines gerichteten
-Graphen mit $5$ Knoten und $7$ Kanten.
+Graphen mit fünf Knoten und sieben Kanten.
+Die roten Einträge in der Adjazenzmatrix $A(G)$ heben die
+Unterschiede zur Adjazenzmatrix des gerichteten Graphen
+von Abbildung~\ref{buch:graphen:fig:adjazenzu} hervor.
 \label{buch:graphen:fig:adjazenzd}}
 \end{figure}
 Die Adjazenzmatrix kann auch für einen gerichteten Graphen definiert
-werden wie dies in in Abbildung~\ref{buch:graphen:fig:adjazenzu}
+werden wie dies in in Abbildung~\ref{buch:graphen:fig:adjazenzd}
 illustriert ist.
 Ihre Einträge sind in diesem Fall definiert mit Hilfe der 
 gerichteten Kanten als
 \begin{equation}
-A(G)_{ij}
+A(G)_{i\!j}
 =
-a_{ij}
+a_{i\!j}
 =
 \begin{cases}
 1&\qquad  (j,i) \in E\\
 0&\qquad  \text{sonst.}
 \end{cases}
-\label{buch:graphen:eqn:linkmatrix}
+\label{buch:graphen:eqn:adjazenzmatrix}
 \end{equation}
 Die Matrix $A(G)$ hat also genau dann einen nicht verschwindenden
 Matrixeintrag in Zeile $i$ und Spalte $j$, wenn es eine Verbindung
@@ -192,31 +203,36 @@ von Knoten $j$ zu Knoten $i$ gibt.
 
 \subsubsection{Adjazenzmatrix und die Anzahl der Pfade}
 Die Beschreibung des Graphen mit der Adjazenzmatrix $A=A(G)$ nach
-\eqref{buch:graphen:eqn:linkmatrix} ermöglicht bereits, eine interessante
-Aufgabe zu lösen.
+\eqref{buch:graphen:eqn:adjazenzmatrix} ermöglicht bereits, eine
+interessante Aufgabe zu lösen.
 
 \begin{satz}
 \label{buch:graphen:pfade-der-laenge-n}
 Der gerichtete Graph $G=([n],E)$ werde beschrieben durch die Adjazenzmatrix
 $A=A(G)$.
-Dann gibt das Element in Zeile $j$ und Spalte $i$ von $A^n$ die Anzahl
-der Wege der Länge $n$ an, die von Knoten $i$ zu Knoten $j$ führen.
-Insbesondere kann man die Definition~\eqref{buch:graphen:eqn:linkmatrix}
+Dann gibt das Element $(A^n)_{ji}$ in Zeile $j$ und Spalte $i$ von $A^n$
+die Anzahl der Wege der Länge $n$ an, die von Knoten $i$ zu Knoten $j$ führen.
+Insbesondere kann man die Definition~\eqref{buch:graphen:eqn:adjazenzmatrix}
 formulieren als: In Zeile $j$ und Spalte $i$ der Matrix steht die Anzahl
 der Pfade der Länge $1$, die $i$ mit $j$ verbinden.
 \end{satz}
+\index{Anzahl der Pfade}%
 
 \begin{proof}[Beweis]
-Es ist klar, dass $A^1$ die genannte Eigenschaft hat.
-Wir beweisen, dass $A^n$ Pfade der Länge $n$ zählt, mit Hilfe von
-vollständiger Induktion.
-Zur Unterscheidung schreiben wir $A^{(n)}$ für die Matrix, die in Zeile
+Zur Unterscheidung der Matrix der Wegzahlen von $A^n$ schreiben wir
+$A^{(n)}$ für die Matrix, die in Zeile
 $j$ und Spalte $i$ die Anzahl der Pfade der Länge $n$ von $i$ nach $j$
 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 nehmen daher an, dass bereits bewiesen ist, dass das Element in Zeile
+Wir beweisen, dass $A^n$ Pfade der Länge $n$ zählt, mit Hilfe von
+vollständiger Induktion.
+Es ist klar, dass $A^1$ die genannte Eigenschaft hat.
+Der Fall $A^1$ dient daher als Induktionsverankerung.
+
+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.
@@ -225,16 +241,16 @@ 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
 einem beliebigen Knoten $j$ führt, gefolgt von einer einzelnen Kante,
 die von $j$ nach $k$ führt.
-Ob es eine solche Kante gibt, zeigt das Matrixelement $a_{kj}$ an.
+Ob es eine solche Kante gibt, zeigt das Matrixelement $a_{k\!j}$ an.
 Das Element in Zeile $j$ und Spalte $i$ der Matrix $A^{(n-1)}$ gibt
 die Anzahl der Wege von $i$ nach $j$ an.
-Es gibt also $a_{kj}\cdot a_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$
+Es gibt also $a_{k\!j}\cdot a_{ji}^{(n-1)}$ Wege der Länge $n$, die von $i$
 nach $k$ führen, aber als zweitletzten Knoten über den Knoten $j$ führen.
 Die Gesamtzahl der Wege der Länge $n$ von $i$ nach $k$ ist daher
 \[
 a_{ki}^{(n)}
 =
-\sum_{j=1}^n a_{kj} a_{ji}^{(n-1)}.
+\sum_{j=1}^n a_{k\!j} a_{ji}^{(n-1)}.
 \]
 In Matrixschreibweise bedeutet dies
 \[
@@ -248,8 +264,13 @@ A^n.
 \]
 Beim zweiten Gleichheitszeichen haben wir die Induktionsannahme
 verwendet.
+Damit ist der Induktionsschritt vollzogen und der Satz bewiesen.
 \end{proof}
 
+Speziell geben die Diagonalelemente von $A^n$ die Zahl der geschlossenen
+Pfade an.
+$(A^n)_{ii}$ ist die Anzahl der geschlossenen Pfade, die $i$ enthalten.
+
 Der Satz~\ref{buch:graphen:pfade-der-laenge-n} ermöglicht auch, einen 
 Algorithmus für den sogenannten Durchmesser eines Graphen zu formulieren.
 
@@ -291,7 +312,7 @@ G
  0& 0& 1& 0& 0& 0& 1& 0& 1& 0\\ %  8
  0& 0& 0& 1& 0& 0& 0& 1& 0& 1\\ %  9
  0& 0& 0& 0& 1& 1& 0& 0& 1& 0   % 10
-\end{pmatrix}
+\end{pmatrix}.
 \]
 Durch Nachrechnen kann man bestätigen, dass $G^3$ keine
 Ausserdiagonalelemente $0$ enthält:
@@ -310,13 +331,15 @@ G^3
  2& 2& 2& 5& 2& 2& 2& 5& 0& 5\\
  2& 2& 2& 2& 5& 5& 2& 2& 5& 0
 \end{pmatrix}
+=
+2(U-I) + 3G.
 \]
 Daraus kann man jetzt ablesen, dass der Durchmesser des Petersongraphen
-$d=5$ ist.
-Man kann aber auch mehr ablesen:
+$d=3$ ist.
+Man kann aber noch mehr ablesen:
 \begin{itemize}
 \item
-Es gibt keine geschlossenen Pfade der Länge $\le 3$.
+Es gibt keine geschlossenen Pfade der Länge $3$.
 \item
 Zwischen benachbarten Knoten gibt es jeweils $5$ Pfade der Länge $3$,
 zwischen nicht benachbarten Knoten gibt es genau $2$ Pfade der Länge $3$.
@@ -332,18 +355,6 @@ Für den Peterson-Graphen können die gefundenen Aussagen über die Anzahl
 von Pfaden durch Ausnützung der Symmetrien des Graphen leichter direkt
 gefunden werden.
 
-\subsubsection{Beschriftete Graphen}
-Bei der Beschreibung eines elektrischen Netzwerkes mit Hilfe eines
-ungerichteten Graphen muss jeder Kante zusätzlich ein Widerstandswert
-zugeordnet werden.
-Dies ist, was eine Beschriftung einer Kante bewerkstelligt.
-
-\begin{definition}
-Eine Beschriftung mit Elementen der Menge $L$
-eines gerichteten oder ungerichteten Graphen $G=(V,E)$ 
-ist eine Abbildung $l\colon E\to L$.
-\index{Beschriftung}%
-\end{definition}
 
 \subsection{Inzidenzmatrix}
 Die Adjazenzmatrix kann zusätzliche Information, die möglicherweise
@@ -352,27 +363,27 @@ Dies tritt zum Beispiel in der Informatik bei der Beschreibung
 endlicher Automaten auf, wo zu jeder gerichteten Kante auch noch
 Buchstaben gehören, für die der Übergang entlang dieser Kante
 möglich ist.
-
-Die {\em Inzidenzmatrix} löst dieses Problem.
-\index{Inzidenzmatrix}%
-Dazu werden zunächst die Kanten numeriert $1,\dots,m$
-numeriert.
-Die Matrixeinträge
-\[
-a_{ij} = \begin{cases}
-1\qquad&\text{Knoten $i$ ist ein Endpunkt von Kante $j$}
-\\
-0\qquad&\text{sonst}
-\end{cases}
-\]
-stellen die Beziehung zwischen Kanten und Knoten her.
+Oder in der Elektrotechnik, wo jedes Bauteil in einem elektrischen
+Netzwerk eine Impedanz hat.
 
 \subsubsection{Beschriftete Graphen}
-Die Inzidenzmatrix kann auch einen erweiterten Graphenbegriff abbilden,
-in dem zwischen zwei Kanten mehrere Verbindungen möglich sind.
-Graphen mit beschrifteten Kanten gehören dazu.
+Ein beschrifteter Graph löst dieses Problem.
 
 \begin{definition}
+Eine {\em Beschriftung}
+eines gerichteten oder ungerichteten Graphen $G=(V,E)$ 
+mit Elementen der Menge $L$, den Labels,
+ist eine Abbildung $l\colon E\to L$.
+\index{Beschriftung}%
+\end{definition}
+
+Einen gerichteten, beschrifteten Graphen können wir gleichwertig
+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.
+
+\begin{definition}
+\label{buch:graphen:def:beschriftetergraphgerichtet}
 Ein gerichteter Graph mit beschrifteten Kanten ist eine Menge $V$ von 
 Knoten und eine Menge von beschrifteten Kanten der Form
 \[
@@ -381,63 +392,104 @@ E \{ (a,b,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt vo
 Die Menge $L$ enthält die möglichen Beschriftungen der Kanten.
 \end{definition}
 
+Diese Definition gestattet, dass zwischen zwei Knoten $a$ und $e$
+mehrere Kanten vorhanden sind, die sich durch die Beschriftung
+unterscheiden.
+
+\subsubsection{Inzidenzmatrix}
+Die Adjazenzmatrix bildet nur die Nachbarschaftsbeziehung ab,
+sie sagt nichts aus über die ``Qualität'' der Verbindung, die durch
+die Beschriftung einer Kante angezeigt wird.
+Nach Definition~\ref{buch:graphen:def:beschriftetergraphgerichtet}
+ist es auch möglich, dass mehrere Kanten von $a$ nach $e$ führen,
+die Adjazenzmatrix kann diese ebenfalls nicht unterscheiden.
+Die {\em Inzidenzmatrix}
+löst dieses Problem.
+\index{Inzidenzmatrix}%
+Dazu werden zunächst zusätzlich die Kanten $1,\dots,m$
+numeriert, wobei Kanten mit verschiedenen Beschriftungen separat
+gezählt werden.
+Die Matrixeinträge
+\[
+b_{i\!j} = \begin{cases}
+1\qquad&\text{Knoten $i$ ist ein Endpunkt von Kante $j$}
+\\
+0\qquad&\text{sonst}
+\end{cases}
+\]
+der Inzidenzmatrix $B(G)$
+stellen die Beziehung zwischen Kanten und Knoten her.
 Für einen gerichteten Graphen wird in der Inzidenzmatrix für
 den Anfangspunkt einer Kante $-1$ eingetragen und für den
 Endpunkt $+1$.
-% XXX Beispiel
+Die Inzidenzmatrizen $B(G)$ für die Graphen der beiden Beispiele
+in den Abbildungen~\ref{buch:graphen:fig:adjazenzu} und
+\ref{buch:graphen:fig:adjazenzd} ist ebendort angegeben.
 
 \subsubsection{Inzidenzmatrix und Adjazenzmatrix}
-Sei $B(G)$ die Inzidenzmatrix eines Graphen $G$. 
+Sei $B(G)$ die Inzidenzmatrix eines ungerichteten Graphen $G$. 
 Die Spalten von $B(G)$ sind mit den Kanten des Graphen indiziert.
 Die Matrix $B(G)B(G)^t$ ist eine quadratische Matrix, deren
 Zeilen und Spalten mit den Knoten des Graphen indiziert sind.
-In dieser Matrix geht die Informatione über die individuellen
+In dieser Matrix geht die Information über die individuellen
 Kanten wieder verloren.
 Sie hat für $i\ne j$ die Einträge
 \begin{align*}
-(B(G)B(G)^t)_{ij}
+(B(G)B(G)^t)_{i\!j}
 &=
 \sum_{\text{$k$ Kante}} b_{ik}b_{jk}
 \\
 &=\text{Anzahl der Kanten, die $i$ mit $j$ verbinden}
 \\
-&=a_{ij}.
+&=a_{i\!j}.
 \end{align*}
 Die Adjazenzmatrix eines Graphen lässt sich also aus der
 Inzidenzmatrix berechnen.
 
 \subsubsection{Gradmatrix}
 \index{Gradmatrix}%
-Die Diagonale von $B(G)B(G)^t$ enthält die Werte
-\begin{align*}
+Die Diagonale von $B(G)B(G)^t$ eines ungerichteten Graphen $G$
+enthält die Werte
+\begin{align}
 (B(G)B(G)^t)_{ii}
 &=
 \sum_{\text{$k$ Kante}} b_{ik}^2
 =
 \text{Anzahl Kanten, die im Knoten $i$ enden}
-\end{align*}
+\label{buch:graphen:eqn:gradmatrix}
+\end{align}
 Der {\em Grad} eines Knoten eines Graphen ist die Anzahl der
 \index{Grad eines Knotens}%
 Kanten, die in diesem Knoten enden.
-Die Diagonalmatrix die aus den Graden der Knoten besteht, heisst die
+Die Diagonalmatrix, die aus den Graden der Knoten besteht, heisst die
 Gradmatrix $D(G)$ des Graphen.
 Es gilt daher $B(G)B(G)^t = A(G) + D(G)$.
+Für Beispiele siehe die Abbildungen~\ref{buch:graphen:fig:adjazenzu} und
+\ref{buch:graphen:fig:adjazenzd}.
 
 \subsubsection{Gerichtete Graphen}
 Für einen gerichteten Graphen ändert sich an der Diagonalen
 der Matrix $B(G)B(G)^t$ nichts.
-Da es in einem gerichteten Graphen nur eine einzige Kante $k$ gibt, die zwei
-Knoten $i$ und $j$ verbinden kann, muss das zugehörige 
-Ausserdiagonalelement
-\[
-a_{ij}
-=b_{ik}b_{jk}
+Sei $k$ die Kante, die vom Knoten $j$ zum Knoten $i$ führt.
+Die Einträge in der Inzidenzmatrix sind daher $b_{ik}=1$ und $b_{jk}=-1$.
+Da es nur eine solche Kante gibt (der Graph ist nicht beschriftet),
+ist $b_{ik}b_{jk}$ der einzige Term in der Summe, mit der das
+Matrixelement
+\begin{equation}
+a_{i\!j}
+=
+(B(G)B(G)^t)_{i\!j}
+=
+\sum_{\kappa} b_{i\kappa}b_{j\kappa}
+=
+b_{ik}b_{jk}
 =
 -1
-\]
-sein.
+\label{buch:graphen:eqn:ausserdiagonal}
+\end{equation}
+berechnet wird.
 Für einen gerichteten Graphen sind daher alle Ausserdiagonalelemente
-negativ und es gilt $B(G)B(G)^t = D(G)-A(G)$.
+negativ.
 
 \subsubsection{Anwendung: Netlist}
 Eine natürliche Anwendung eines gerichteten und beschrifteten Graphen
@@ -451,52 +503,61 @@ welchen Nets verbunden werden müssen.
 Die Informationen in der Inzidenzmatrix werden also in einer
 Applikation zum Schaltungsentwurf in ganz natürlicher Weise erhoben.
 
-\subsection{Die Adjazenzmatrix und Laplace-Matrix
-\label{subsection:adjazenz-und-laplace-matrix}}
-Die Beschreibung mit der Matrix~\eqref{buch:graphen:eqn:linkmatrix}
-``vergisst'' den ``Namen'' der Kante, die eine Verbindung zwischen zwei
-Knoten herstellt.
-Damit ist sie keine geeignete Grundlage, um beschriftete Graphen einer
-Matrixbeschreibung zuzuführen.
-Eine solche muss eine Matrix verwenden, die nicht nur das Vorhandensein einer
-Verbindung wiedergibt, sondern ausdrückt, welche Kante welche beiden
-Knoten miteinander verbindet.
-Dies führt zur sogenannten Adjazenzmatrix.
+\subsection{Die Laplace-Matrix
+\label{subsection:laplace-matrix}}
+Will man ein elektrisches Netzwerk modellieren oder den Transport
+von Wärme durch eine Gitterstruktur berechnen, dann muss man zwar den
+Kanten des Netzwerks eine ``Stromrichtung'' geben um ausdrücken zu können,
+in welche Richtung der Strom oder die Wärmeenergie fliesst.
+Trotzdem gestattet man natürlich auch den Stromfluss in Gegenrichtung.
+
+Wir gehen also aus von einem ungerichteten Graphen $G$, aus dem
+wir einen gerichteten Graphen $G'$ machen.
+Zu jeder Kante $\{a,b\}$ von $G$ wählen wir genau eine der möglichen
+Orientierungen $(a,b)$ oder $(b,a)$ im Graphen $G'$.
+Aus der Inzidenzmatrix $B(G')$ lässt sich jetzt ein Operator konstruieren,
+der für die Anwendungen besonders gut geeignet ist.
 
 \begin{definition}
-\label{buch:def:adjazenz-matrix}
-Ist $G=(V,E)$ ein gerichteter Graph mit $n=|G|$ Vertizes und $m=|E|$ Kanten,
-dann ist die zugehörige {\em Adjazenzmatrix} $A=A(G)$ eine $n\times m$-Matrix.
-In der Spalte $k$ wird der Anfangspunkt der Kante $k$ mit $-1$, der Endpunkt
-mit $+1$ angezeigt, die übrigen Einträge sind $0$.
-$A$ hat also die Matrixelemente
+\label{buch:graphen:def:laplace-matrix}
+Die {\em Laplace-Matrix} des Graphen $G$ ist
+\[
+L(G) = B(G')B(G')^t,
+\]
+wobei $G'$ ein wie oben konstruierter gerichteter Graph ist.
+\end{definition}
+
+Wir müssen uns davon überzeugen, dass diese Definition sinnvoll ist
+und nicht etwa von der Wahl von $G'$ abhängt.
+Diese klärt der folgende Satz.
+
+\begin{satz}
+Die Laplace-Matrix eines ungerichteten Graphen $G$ ist
 \begin{equation}
-a_{ik}
-=
-\begin{cases}
--1&\qquad i=a(k)\\
-+1&\qquad i=e(k)\\
-\phantom{+}0&\qquad\text{sonst}
-\end{cases}
-\label{buch:eqn:ajazenz-matrix}
+L(G) = D(G) - A(G)
+\label{buch:graphen:eqn:laplace-definition}
 \end{equation}
-\end{definition}
+und somit insbesondere unabhängig von der Wahl des Graphen $G'$,
+der für die Definition von $L(G)$ verwendet wurde.
+\end{satz}
 
-Der wesentliche Unterschied dieser Definition von der Matrix $G$
-liegt in der Bedeutung der Einträge.
-Für $G$ drückt ein nicht verschwindendes Matrixelement das Vorhandensein
-einer Kante aus, in $A$ ist es die Tatsache, dass in diesem Knoten
-eine Kante beginnt oder endet.
-
-Es ist natürlich möglich, aus der Adjazenzmatrix auch die Link-Matrix
-zu rekonstruieren.
-Dazu muss für jedes Paar $(j,i)$ von Knoten festgestellt werden,
-ob die Adjazenzmatrix eine entsprechende Verbindung enthält, also ob der
-Vektor 
-\[
-k_{ji} = e_i - e_j
-\]
-als Spaltenvektor vorkommt, wobei die $e_i$ die $n$-dimensionalen
-Standardbasisvektoren sind.
+\begin{proof}[Beweis]
+Aufgrund der Konstruktion des Graphen $G'$ sind die Diagonalelemente
+der Laplace-Matrix
+$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)$.
+Damit ist die Formel
+\eqref{buch:graphen:eqn:laplace-definition}
+nachgewiesen.
+\end{proof}
 
+Die Laplace-Matrix tritt zum Beispiel als Diskretisation des Laplace-Operators
+in partiellen Differentialgleichungen auf.
+Sie ist die Basis für die Untersuchungen der spektralen Graphentheorie
+in Abschnitt~\ref{buch:section:spektrale-graphentheorie}.
 
diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex
index 530d96c..1fb61b6 100644
--- a/buch/chapters/70-graphen/chapter.tex
+++ b/buch/chapters/70-graphen/chapter.tex
@@ -9,41 +9,44 @@
 \rhead{}
 Ein Graph ist eine Menge von Knoten, die untereinander mit Kanten
 verbunden sind.
-Graphen können zum Beispiel verwendet werden um Netzwerke zu beschreiben,
+\index{Graph}%
+Graphen können zum Beispiel verwendet werden, um Netzwerke zu beschreiben,
 aber auch viele andere Datenstrukturen.
 \index{Graph}%
-Die Knoten können einzelne Objekte beschreiben, die Kanten beschreiben
+Die Knoten können einzelne Objekte darstellen, die Kanten entsprechen
 dann Beziehungen zwischen diesen Objekten.
 Graphen haben zwar nur eine eindimensionale Geometrie, sie können aber auch als
-erste Approximation dreidimensionaler Objekte dienen.
+erste Approximation höherdimensionaler geometrischer Strukturen dienen.
 
 Die Bedeutung des Graphenkozeptes wird unterstrichen von der Vielzahl
-von Fragestellungen, die über Graphen gestellt, und der
+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}%
 Problem in ein Graphenproblem umformulieren lässt.
 \index{Komplexitätstheorie}%
 
 Das Problem, einen Stundenplan zu finden, der sicherstellt, dass
+\index{Stundenplan}%
 alle Studierenden jedes Fach besuchen können, für die sie sich
 angemeldet haben, lässt sich zum Beispiel wie folgt als ein
 Graphenproblem formulieren.
 Die Fächer betrachten wir als Knoten des Graphen.
-Für jedes Paar von Fächern ziehen wir eine Kante des Graphen, wenn 
+Für jedes Paar von Fächern ziehen wir eine Kante, wenn 
 sich mindestens ein Studierender für beide Fächer angemeldet hat.
 Die Kante drückt aus, dass die beiden Fächer nicht zur gleichen Zeit
 geplant werden dürfen.
 Das Problem, einen Stundenplan zu finden, besteht jetzt darin, für
-jedes Fach ein Zeitintervall zu finden, während dem es durchgeführt
+jedes Fach ein Zeit\-intervall zu finden, während dem es durchgeführt
 werden soll.
-\index{Stundenplan}%
-Natürlich steht nur eine beschränkte Anzahl Zeitintervalle zur Verfügung
-und benachbarte Knoten dürfen nicht ins gleiche Zeitintervall geplant
-werden.
+Natürlich steht nur eine beschränkte Anzahl Zeitintervalle zur Verfügung.
+Benachbarte, also mit einer Kante verbundene Knoten dürfen nicht
+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 die Knoten
+ist es möglich, mit einer beschränkten Anzahl von Farben, oder im
+vorliegenden Fall Zeitintervalle, die Knoten
 des Graphen so einzufärben, dass benachbarte Knoten niemals die gleiche
 Farbe haben.
 
diff --git a/buch/chapters/70-graphen/images/adjazenzd.pdf b/buch/chapters/70-graphen/images/adjazenzd.pdf
index dc3dd8f..146856c 100644
--- a/buch/chapters/70-graphen/images/adjazenzd.pdf
+++ b/buch/chapters/70-graphen/images/adjazenzd.pdf
diff --git a/buch/chapters/70-graphen/images/adjazenzd.tex b/buch/chapters/70-graphen/images/adjazenzd.tex
index 5cef18e..81801d3 100644
--- a/buch/chapters/70-graphen/images/adjazenzd.tex
+++ b/buch/chapters/70-graphen/images/adjazenzd.tex
@@ -10,12 +10,14 @@
 \usepackage{txfonts}
 \usepackage{pgfplots}
 \usepackage{csvsimple}
+\usepackage{color}
 \usetikzlibrary{arrows,intersections,math,calc}
 \begin{document}
 \def\skala{1}
 \begin{tikzpicture}[>=latex,thick,scale=\skala]
 
 \def\r{1.8}
+\def\R{\bgroup\color{red}0\egroup}
 
 \begin{scope}
 \coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)});
@@ -71,15 +73,16 @@ B(G)
 \end{pmatrix*}$};
 \end{scope}
 
+
 \begin{scope}[xshift=3cm,yshift=1.1cm]
 \node at (0,0) [right] {$\displaystyle
 A(G)
 =
 \begin{pmatrix*}[r]
- 0& 1& 1& 0& 1\\
- 1& 0& 1& 1& 0\\
- 1& 1& 0& 1& 0\\
- 0& 1& 1& 0& 1\\
+ 0&\R&\R& 0&\R\\
+ 1& 0&\R&\R& 0\\
+ 1& 1& 0&\R& 0\\
+ 0& 1& 1& 0&\R\\
  1& 0& 0& 1& 0
 \end{pmatrix*},
 \quad
@@ -90,7 +93,7 @@ D(G)
 0&3&0&0&0\\
 0&0&3&0&0\\
 0&0&0&3&0\\
-0&0&0&0&1
+0&0&0&0&2
 \end{pmatrix*}
 $};
 \end{scope}
diff --git a/buch/chapters/70-graphen/images/adjazenzu.pdf b/buch/chapters/70-graphen/images/adjazenzu.pdf
index d3f255e..6002cbf 100644
--- a/buch/chapters/70-graphen/images/adjazenzu.pdf
+++ b/buch/chapters/70-graphen/images/adjazenzu.pdf
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$.
diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex
index 8baa88c..2b9f29b 100644
--- a/buch/chapters/70-graphen/wavelets.tex
+++ b/buch/chapters/70-graphen/wavelets.tex
@@ -270,7 +270,7 @@ $\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,
+Für beliebige Funktionen $g$ und $h$ kann man nicht davon ausgehen,
 aber man kann erwarten.
 Man muss daher zusätzlich verlangen, dass
 \[
diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib
index 977bf81..fb88d09 100644
--- a/buch/chapters/references.bib
+++ b/buch/chapters/references.bib
@@ -152,3 +152,13 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc
         language = {german},
 }
 
+@buch{skript:brualdi,
+	title = {The mutually beneficial relationships of graphs and matrices},
+	author = {Richard A. Brualdi},
+	series = {CBMS Regionals conference series in mathematics},
+	number = {115},
+	publisher = {American Mathematical Society},
+	isbn = {978-0-8218-5315-3},
+	year = 2011,
+	language = {english}
+}