Einführung in die Graphentheorie Teil 1/3
Einleitung
Bevor ich von Graphentheorie gehört habe, habe ich solche Rätsel mühsam mithilfe eines Excelsheet gelöst. Ich hätte alle möglichen Zustände in die Spalten und die Zustandsübergänge in den Zeilen eingetragen und nach und nach den schnellsten Weg durch Ankreuzen der jeweiligen Spalte gefunden. Heute löse ich solche Rätsel mithilfe eines Graphen, bin um ein Vielfaches schneller und muss nicht wieder von vorne beginnen, wenn ich mich versehentlich in einer Zeile geirrt habe.
In diesem Artikel erkläre ich euch die Grundbegriffe der Graphentheorie, einem Teilgebiet der Mathematik bzw. Kombinatorik und wie man diese mathematischen Erkenntnisse programmiertechnisch und praxisnah anwenden kann.
Graphentheorie ist in der Komplexitäts- sowie der Netzwerktheorie von großer Bedeutung. Die Berechenbarkeitstheorie setzt sich damit auseinander welche Probleme algorithmisch gelöst werden können, das Ziel der Komplexitätstheorie hingegen beschäftigt sich mit der Menge aller lösbaren Probleme, das bedeutet aber nicht immer, dass die aus mathematischer Sicht beste oder schnellste Lösung auch in der Praxis angewendet werden kann bzw. das auch erwünscht ist.
Vor etlichen Jahren durfte ich bei dem Diplomprojekt eines Bekannten mitwirken, wo es unter anderem um die Neuplanung des Feuerwehrgebäudes auf dem Vienna International Airport ging. Bei der Planung eines Feuerwehrgebäudes ist es primär notwendig, dass die Feuerwehrmänner im Falle eines Einsatzes innerhalb weniger Sekunden a) beim Feuerwehrwagen und b) am Unfallort sind. Dies lässt sich am besten mithilfe von Graphentheorie lösen: Es gibt Stockwerke, Räume und Wege, die nach Länge bzw. Zeit bewertet werden. Unsere Aufgabe war es den Grundriss des Feuerwehrgebäudes zu definieren, aber nachdem die Mitarbeiter dort noch nie etwas von Graphentheorie gehört hatten, wurden uns schon die diversen Anschlüsse (Strom, Wasser, etc.) vorgegeben und somit war es uns nicht mehr möglich den aus Feuerwehrsicht besten Grundriss abzugeben.
Dipl.-Ing. Franz Berger, ein ehemaliger Professor, der unter anderem auch Graphentheorie unterrichtet, hat vor etlichen Jahren im Zuge seiner Diplomarbeit das Wiener U-Bahn Netz analysiert und kam zu dem Schluss, dass man sehr viel Geld hätte einsparen können, wenn man seinerzeit bei der Planung die Graphentheorie herangezogen hätte. Seine Diplomarbeit kann man übrigens in der Österreichischen Nationalbibliothek einsehen und ist es auch wert gelesen zu werden.
Die beste Lösung kann daher nicht immer umgesetzt werden, wenn suboptimale Rahmenbedingungen gegeben sind. Wir können aber trotzdem das Beste daraus machen bzw. den unter den gegebenen Bedingungen besten Weg finden oder uns mit den unterschiedlichen Lösungen auseinandersetzen.
Definition: Graph
Ein Graph besteht aus einer Menge von Knoten und Kanten und wird zur Darstellung von Beziehungen verwendet. Knoten können mittels Kanten miteinander verbunden werden.
Definieren lässt sich ein Graph G somit als ein Paar aus einer Menge von Knoten V und eine Menge von Kanten E. Zur Visualisierung verwendet man für die Knoten häufig Kreise und für die Kanten Linien mit und ohne Richtungspfeilen.
G = (V,E) V… Menge von Knoten (engl. vertices)
E… Menge von Kanten (engl. edges)
Definition: Ungerichteter Graph
Bei ungerichteten Graphen haben die Kanten keine Richtung, weshalb sie grafisch ohne Richtungspfeil dargestellt werden. Die Bedeutung der ungerichteten Kanten kann man sich z.B. an einem Telefonnetz klarmachen, bei dem die Kanten den (bidirektionalen) Leitungen und die Knoten den Sendern entsprechen. Begrifflich wird eine nicht-leere Menge mit maximal zwei Knoten als Kante, welche die in ihr enthaltenen Knoten verbindet, verwendet, denn die Reihenfolge der Elemente innerhalb einer Menge ist belanglos.
E ⊆ {{x,y} | x,y ∈ V}
{x,y} ist Kante :⇔ Es existiert eine ungerichtete Kante zwischen x und y.
{x,y} = {y,x}
Spezialfall: {x,x} = {x} :⇔ Es existiert eine sog. Schleife am Knoten x.
Definition: Gerichteter Graph
Unter gerichteten Graphen versteht man Graphen deren Kanten eine Richtung besitzen und deshalb bei der Visualisierung mit Richtungspfeilen gezeichnet werden. Eine gerichtete Kante von x nach y wird als Paar (x,y) definiert, da die Reihenfolge in einem Paar wesentlich ist. Kanalnetze können beispielsweise mittels gerichteter Graphen abstrahiert werden, indem man die Schächte als Kanten und die Knoten als Anschlussstellen (z.B. WC, Badewanne) modelliert. Knoten stellen die Zustände und Kanten die Zustandsübergänge dar.
E ⊆ V×V = {(x,y) | x,y ∈ V}
(x,y) ∈ E :⇔ Es existiert eine gerichtete Kante von x nach y
(x,y) ≠ (y,x)
Definition: Gemischter Graph
Unter einem gemischten Graph versteht man einen Graph, der aus gerichteten und ungerichteten Kanten besteht. Am Beispiel der Straßenplanung entsprechen die Knoten den Kreuzungen und die Kanten den Straßen, wobei der Spezialfall Einbahnstraßen über gerichtete Kanten modelliert wird. In der Praxis werden gemischte Graphen jedoch kaum verwendet, sondern durch gerichtete Graphen ersetzt, da jede ungerichtete Kante {x,y} durch zwei gerichtete Kanten (x,y) und (y,x) ersetzt werden kann.
Definition: Kantengewichtung
In vielen Fällen ist es nicht ausreichend, zu wissen, welche Knoten miteinander verbunden sind, sondern auch welche Wertigkeiten sie besitzen. Um solche Wertigkeiten auszudrücken, wird den Kanten ein Gewicht zugeordnet. Hierfür gibt es eine Gewichtsfunktion w (engl. weight), die ein Element von E auf eine Zahl, wie z.B, eine natürliche Zahl, abbildet. Ein prominentes Beispiel für einen solchen Graphen sind Straßennetze, wie man sie in Routenplanern verwendet. Jeder Kante, d.h. Straße, wird dabei ein Gewicht, d.h. die Entfernung, zugeordnet. Auf einen solchen Graphen lassen sich Algorithmen zum Bestimmen des kürzesten Weges zwischen zwei Knoten anwenden, wie z.B. den A*-Algorithmus.
Definition: Nachbarschaft
Als Nachbarschaft N(v) bezeichnet man die Menge der Knoten, mit denen v durch eine Kante verbunden ist. Bei gerichteten Graphen kann außerdem zwischen der Vorgänger- und Nachfolgermenge unterschieden werden, da es für einen Knoten zwei Möglichkeiten, wie er mit einem anderen Knoten verbunden ist, geben kann.
• Ungerichtete Nachbarschaft: N(v) = { w | {v,w} ∈ E}
• Gerichtete Nachbarschaft: N(v) = N-(v) ∪ N+(v)
• Vorgängermenge (gerichtet): N-(v) = { w | (w,v) ∈ E}
• Nachfolgermenge (gerichtet): N+(v) = { w | (v,w) ∈ E}
Definition: Grad
Der Begriff Grad bezeichnet die Anzahl der Kanten, mit denen ein Knoten verbunden ist. Hierfür führen wir drei Funktionen ein, wobei eine auf ungerichteten und die anderen beiden auf gerichteten Graphen definiert sind. Durch die Kantenrichtung auf gerichteten Graphen gibt es für selbige die Funktionen indegree, welche die Anzahl der eingehenden Kanten zurückgibt, und outdegree, welche auf die Anzahl der ausgehenden Kanten abbildet. Bei ungerichteten Graphen fällt diese Unterscheidung weg, weshalb die Funktion degree jeden Knoten v auf die Anzahl der Kanten abbildet, die v mit einem anderen Knoten verbinden. Ein Knoten v mit degree(v) = 0 (bzw. indegree(v) = 0 und outdegree(v) = 0) bezeichnet man als isoliert. Auf gerichteten Graphen bezeichnet man Knoten v mit indegree(v) = 1 ∧ outdegree(v) = 0 als Endknoten und Knoten w mit indegree(w) = 0 ∧ outdegree(w) = 1 als Startknoten. Da ungerichtete Kanten keine Richtung besitzen, kann man bei Knoten v mit degree(v) = 1 nicht zwischen Start- und Endknoten entscheiden, weshalb die Bezeichnung von jeweiligen Anwendungsfall abhängt. Beispielsweise werden die Blätter in einem Baum auch als Endknoten bezeichnet, da sie die am tiefsten liegenden Knoten im Graphen darstellen. Graphen können mehrere Start- bzw. Endknoten oder keine besitzen; letztere bezeichnet man auch als geschlossene Graphen.
degree(v) = Σ{v,w} ∈ E, v ≠ w1 + Σ{v} ∈ E2
indegree(v) = Σ(w,v) ∈ E1
outdegree(v) = Σ(v,w) ∈ E1
Definition: Wege in Graphen
Einen Tupel (v1, v2, …, vn) bezeichnet man als Weg, wenn für jedes i ∈ {1,2,…,n-1} gilt, dass (vi, vi+1) ∈ E bzw. {vi, vi+1} ∈ E. D.h. jeder Knoten vi ist mit seinem Nachfolger vi+1 verbunden. Den Knoten v1 bezeichnet man als Start- und vn als Endknoten. Neben diesem allgemeinen Begriff gibt es zahlreiche spezielle Wege, welche ich nur erwähnen möchte:
Ein Pfad ist ein Weg bei dem für alle i,j mit i ≠ j gilt, dass vi ≠ vj, d.h. ein Knoten wird maximal einmal besucht.
Ein Hamiltonpfad ist ein Weg, bei dem jeder Knoten des Graphen genau einmal besucht wird (vgl. Problem des Handelsreisenden [1])
Ein Eulerweg ist ein Weg, bei dem jede Kante des Graphen genau einmal besucht wird. (vgl. Haus vom Nikolaus [2])
Interessanterweise ist das Ermitteln eines Hamiltonspfads deutlich schwieriger als das Ermitteln eines Eulerwegs.
