Graphendefinitionen

2 files changed, 186 insertions, 0 deletions

diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex
index 50a63a5..8d7d430 100644
--- a/buch/chapters/70-graphen/beschreibung.tex
+++ b/buch/chapters/70-graphen/beschreibung.tex
@@ -6,4 +6,136 @@
 \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.
+
+\subsection{Definition von Graphen
+\label{subsection:definition-von-graphen}}
+In der Einleitung zu diesem Abschnitt wurde bereits eine informelle
+Beschreibung des Konzeptes eines Graphen gegeben.
+Um zu einer Beschreibung mit Hilfe von Matrizen kommen können,
+wird eine exakte Definition benötigt.
+Dabei werden sich einige Feinheiten zeigen, die für Anwendungen wichtig
+sind und sich in Unterschieden in der Definition der zugehörigen Matrix 
+äussern.
+
+\subsubsection{Ungerichtete Graphen}
+Die Grundlage für alle Arten von Graphen ist eine Menge $V$ von {\em Knoten},
+auch {\em Vertices} genannt.
+\index{Knoten}%
+\index{Vertex}%
+Die Unterschiede zeigen sich in der Art und Weise, wie die Knoten
+mit sogenannten die Kanten 
+\index{Kante}%
+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
+Menge der Endpunkte kennen.
+Dies führt auf die folgende Definition eines ungerichteten Graphen.
+
+\begin{definition}
+\label{buch:def:ungerichteter-graph}
+\index{Graph!ungerichteter}%
+\index{ungerichteter Graph}%
+Ein {\em ungerichteter Graph} ist eine endliche Menge $V$ von {\em Knoten}
+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}).
+\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.
+
+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
+durch die Widerstände ab.
+Will man Spannungen und Ströme in einem solchen Netzwerk berechnen,
+ist auch das Fehlen von Schleifen, die von $a$ zu $a$ führen, kein
+Verlust.
+Die Endpunkte solcher Widerstände wären immer auf gleichem Potential,
+es würde daher kein Strom fliessen, sie haben daher keinen Einfluss auf
+das Verhalten des Netzwerkes und können weggelassen werden.
+
+\subsubsection{Gerichtete Graphen}
+In vielen Anwendungen sind die Endpunkte einer Kante nicht austauschbar.
+In einem Strassennetz sind Einbahnstrassen nicht in beiden Richtungen
+befahrbar.
+Anfangs- und Endpunkt einer Kante müssen in einem solche Graphen
+unterschieden werden.
+Eine zweielementige Menge ist daher nicht mehr eine geeignete Abstraktion
+für die Kante, ein (geordnetes) Paar von Vertizes passt besser.
+
+\begin{definition}
+\label{buch:def:gerichteter-graph}
+\index{Graph!gerichteter}%
+\index{gerichteter Graph}%
+Ein {\em gerichteter Graph} ist eine endliche Menge $V$ von Knoten
+und eine Menge $E \subset V\times V$ von gerichteten Kanten.
+Ausserdem gibt es zwei Abbildungen
+\[
+\begin{aligned}
+a&\colon E\to V: (p,q) \mapsto a((p,q)) = p
+\\
+e&\colon E\to V: (p,q) \mapsto e((p,q)) = q.
+\end{aligned}
+\]
+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
+geworden.
+Ausderdem ist eine Kante $(a,a)$ wohldefiniert, also eine Kante, die vom
+Knoten $a$ wieder zu $a$ zurückführen.
+
+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.
+Aus dem ungerichteten Graphen $(V,E)$ mit Knotenmenge $V$ und Kantenmenge
+$E$ wird so der gerichtete Graph
+$(V,E')$ mit der Kantenmenge
+\[
+E' 
+=
+\{
+(a,e)
+\,|\,
+\{a,e\}\in E
+\}.
+\]
+Eine umgekehrte Zuordnung eines ungerichteten Graphen zu einem gerichteten
+Graphen ist nicht möglich, da eine ``Schleife'' $(a,a)$ nicht in Kante
+des ungerichteten Graphen abgebildet werden kann.
+
+\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$.
+\end{definition}
+
+\subsection{Die Adjazenz-Matrix
+\label{subsection:adjazenz-matrix}}
+
+\subsection{Die Laplace-Matrix
+\label{subsection:laplace-matrix}}
+
+
 
diff --git a/buch/chapters/70-graphen/chapter.tex b/buch/chapters/70-graphen/chapter.tex
index db1f8a9..ae1bb9c 100644
--- a/buch/chapters/70-graphen/chapter.tex
+++ b/buch/chapters/70-graphen/chapter.tex
@@ -7,6 +7,60 @@
 \label{buch:chapter:graphen}}
 \lhead{Graphen}
 \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,
+aber auch viele andere Datenstrukturen.
+\index{Graph}%
+Die Knoten können einzelne Objekte beschreiben, die Kanten beschreiben
+dann Beziehungen zwischen diesen Objekten.
+Graphen haben zwar nur eine eindimensionale Geometrie, sie können aber als
+erste Approximation auch dreidimensionaler Objekte dienen.
+
+Die Bedeutung des Graphenkozeptes wird unterstrichen von der Vielzahl
+von Fragestellungen, die über Graphen gestellt worden sind und der
+zugehöriten Lösungsalgorithmen, die zu ihrer Beantwortung gefunden
+worden sind.
+Die Komplexitätstheorie hat sogar gezeigt, dass sich jedes diskrete
+Problem in ein Graphenproblem umformulieren lässt.
+\index{Komplexitätstheorie}%
+Das Problem, einen Stundenplan zu finden, der sicherstellt, dass
+alle Studierenden an 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 
+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
+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.
+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
+des Graphen so einzufärben, dass benachbarte Knoten niemals die gleiche
+Farbe haben.
+
+In diesem Kapitel soll zunächst gezeigt werden, wie man Graphen mit 
+Hilfe von Matrizen beschreiben kann
+(Abschnitt~\ref{buch:section:beschreibung-von-graphen-mit-matrizen}).
+Das Ziel dabei ist natürlich, die Hilfsmittel der Matrixalgebra
+zur Lösung von Graphenprobleme hinzuzuziehen.
+Die spektrale Graphentheorie in
+Abschnitt~\ref{buch:section:spektrale-graphentheorie} verwendet
+die Eigenwerte und Eigenvektoren der zugehörigen Matrix, um Aussagen
+über den Graphen zu machen.
+\index{Graphentheorie!spektrale}%
+In Abschnitt~\ref{buch:section:wavelets-auf-graphen} wird gezeigt,
+wie spektralen Eigenschaften verwendet werden können, um eine
+Art von Wavelets auf einem Graphen zu definieren.
+Damit ensteht eine für gewisse Anwendungen besonders leistungsfähige
+Basis zur Beschreibung von Funktionen auf dem Graphen.
 
 \input{chapters/70-graphen/beschreibung.tex}
 \input{chapters/70-graphen/spektral.tex}