diff options
author | Andreas Müller <andreas.mueller@othello.ch> | 2021-01-01 11:47:44 +0100 |
---|---|---|
committer | Andreas Müller <andreas.mueller@othello.ch> | 2021-01-01 11:47:44 +0100 |
commit | a225b823fd2c8724e39597bbbf5ddb6e4de6222c (patch) | |
tree | f005ee46dd9bea8ada0f344453d2fea49bcbfb76 /buch/chapters/70-graphen/chapter.tex | |
parent | typo (diff) | |
download | SeminarMatrizen-a225b823fd2c8724e39597bbbf5ddb6e4de6222c.tar.gz SeminarMatrizen-a225b823fd2c8724e39597bbbf5ddb6e4de6222c.zip |
Graphendefinitionen
Diffstat (limited to '')
-rw-r--r-- | buch/chapters/70-graphen/chapter.tex | 54 |
1 files changed, 54 insertions, 0 deletions
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} |