1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
%
% chapter.tex -- Graphenbeschreibung mit Matrizen
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\chapter{Graphen
\label{buch:chapter:graphen}}
\lhead{Graphen}
\rhead{}
Ein Graph ist eine Menge von Knoten, die untereinander mit Kanten
verbunden sind.
\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 darstellen, die Kanten entsprechen
dann Beziehungen zwischen diesen Objekten.
Graphen haben zwar nur eine eindimensionale Geometrie, sie können aber auch als
erste Approximation höherdimensionaler geometrischer Strukturen dienen.
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 NP-vollständige
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, 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 Zeit\-intervall zu finden, während dem es durchgeführt
werden soll.
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, oder im
vorliegenden Fall Zeitintervallen, 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}
\input{chapters/70-graphen/waerme.tex}
\input{chapters/70-graphen/wavelets.tex}
|
