Algorithmische Traversierung

Traversierung eines Graphen bedeutet, dass der Graph beginnend von einem Startknoten durchlaufen wird und bildet eine der wichtigsten Operationen. Es können die Knoten im Graphen gefunden werden, Nachbarknoten werden ermittelt und es können die Anzahl der unterschiedlichen Wege von einem Knoten zum anderen ermittelt werden. Unter einer algorithmischen Traversierung versteht man, dass für das Durchlaufen und das Suchen im Graph ein spezieller Algorithmus genutzt wird. Zwei der wichtigsten Algorithmen werden im Folgenden beschrieben.

Hamiltonweg (Traveling Salesman)

Das Springer-Problem
Das Springer-Problem

Häufig ist es im täglichen Leben so, dass das Zurücklegen von Wegen Kosten verursacht. Eine Reiseroute eines LKW-Fahrers soll möglichst wenig Kosten verursachen und die Strecke möglichst effizient gefahren werden. Dies wird in der Graphentheorie durch einen gewichteten Graphen abgebildet und ist unter dem Namen "Hamiltonweg" oder auch "Traveling Salesman" bekannt. Eine Definition lautet wie folgt:

"Besuche jeden Knoten des Graphen exakt einmal und versuche dabei, die Kosten zu minimieren."

Entspricht der Startknoten dem Endknoten spricht man von einem "Hamiltonkreis". Ein bekanntes Problem, was hierdurch beschrieben wird, ist das Springer-Problem. Dies beantwortet die Frage, welchen Weg ein Springer auf einem Schachfeld gehen muss, um alle Felder genau einmal zu berühren.

Eulerweg

Das Haus vom Nikolaus
Das Haus vom Nikolaus

Möchte man hingegen nicht jeden Knoten, sondern jede Kante genau einmal durchlaufen, spricht man von einem "Eulerweg" bzw. "Eulerkreis".

"Besuche jede Kante des Graphen exakt einmal und versuche dabei, die Kosten zu minimieren."

Das wohl bekannteste Problem ist das "Haus vom Nikolaus", bei dem man versucht ein Haus mit nur einem Strich zu zeichnen.

Der Unterschied zu dem Hamiltonweg/-kreis besteht darin, dass Knoten mehrmals besucht werden können, da jeder Knoten mit mehreren Kanten verbunden sein kann. Aber es wird jede Kante nur genau einmal besucht und markiert. Bei einem Hamiltonweg/-kreis ist die Vorgabe, dass jeder Knoten maximal einmal besucht wird. Es kann also sein, dass einzelne Kanten nicht durchlaufen werden, weil sie bereits markierte Knoten verbindet. Es existieren mehrere Algorithmen, und diese Art der Traversierungen durchzuführen.

Algorithmus von Dijkstra

Der Algorithmus von Dijkstra
Der Algorithmus von Dijkstra

Beispielhaft wird hier der Algorithmus von Dijkstra erklärt. Dieser Algorithmus ähnelt der Breitensuche. Anders als bei der Breitensuche werden aber die Wege im Graphen nicht verworfen, wenn dieser Knoten bereits durch einen anderen Weg gefunden wurde.

Wie in der Abbildung zu sehen ist, werden im ersten Schritt die beiden Wege vom Startknoten iteriert. Hier wird in direkt im ersten Schritt der Zielknoten gefunden und die Breitensuche würde abbrechen. Der Algorithmus von Dijkstra sucht allerdings nach einem Optimum und bricht die Suche hier nicht ab. Er speichert in dem Zielknoten die Information "15" (kann für die Länge der Strecke oder die Dauer einer Fahrtzeit stehen). In dem Knoten V1 wird gleichermaßen die Zahl "5" vermerkt. Im zweiten Schritt findet der Algorithmus ebenfalls den Zielknoten über den Knoten "V1". Er addiert nun die im Knoten V1 gespeicherte Länge zur neuen Strecke hinzu und vergleicht die beiden Ergebnisse. In diesem Beispiel ist die Strecke über den Knoten V1 kürzer (5 + 3 = 8) als der bisher gefundene Weg "15". Im Zielknoten wird nun die neue Streckenlänge 8 gespeichert und der zuerst gefundene Weg wird verworfen.

Wird bei diesem Algorithmus kein Zielknoten vorgegeben, so werden alle kürzeste Wege im Graphen berechnet. Das Ergebnis ist ein Hamiltonweg, bei dem jeder Knoten im Graph genau einmal durchlaufen, mit der Vorgabe, dass derWeg zu diesem Knoten der kürzeste ist.

Die Laufzeit des Algorithmus beträgt O(n2+m), wobei n für die Anzahl der Knoten und m für die Anzahl der Kanten steht. Die Laufzeit ist allerdings stark von Speicherstruktur für die noch nicht besuchten Knoten abhängig. Die hier angegebene Laufzeit steht für eine einfache Liste zur Verwaltung der noch offenen Knoten.

Quellen:

Weiterführende Literatur:

  • Prof. Dr. rer. nat. Peter Tittman: "Graphentheorie", Fachbuchverlag Leipzig im Carl Hanser Verlag, 2003, ISBN 3-446-22343-6
  • Prof. Dr. Volker Turas: "Algorithmische Graphentheorie", 3. Auflage, Oldenburg Wissenschaftsverlag, 2009, ISBN 978-3-486-59057-9
  • Bucher Gruppe: "Graphentheorie: Wege, Pfade, Zyklen und Kreise in Graphen, Durchlaufbarkeit Von Graphen, Vier-Farben-Satz, Zusammenhang Von Graphen", General Books LLC, 2010, ISBN 978-1-159-11215-8
  • Steffi Meier: "Graphentheoretische Modelle zur Optimierung und Simulation", 1. Auflage, GRIN Verlag, 2006, ISBN 978-3-640-32530-6

Kategorie: Neue DB-Entwicklungen, NoSQL, Graphen-DB, T, A