From a225b823fd2c8724e39597bbbf5ddb6e4de6222c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Fri, 1 Jan 2021 11:47:44 +0100 Subject: Graphendefinitionen --- buch/chapters/70-graphen/beschreibung.tex | 132 ++++++++++++++++++++++++++++++ buch/chapters/70-graphen/chapter.tex | 54 ++++++++++++ 2 files changed, 186 insertions(+) (limited to 'buch/chapters/70-graphen') 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} -- cgit v1.2.1