Grundidee

Der Grundgedanke von Theta-Graphen basiert auf einem trivialen Ansatz zur Wegfindung. Wenn sich jemand, z. B. im Autobahnnetz von Deutschland, von einem Startpunkt zu einem Zielpunkt bewegen möchte, ohne den Weg zu kennen, wird er vermutlich folgendermaßen vorgehen:

  • Ausgehend von seinem aktuellen Aufenthaltsort wird er ermitteln, welche Autobahn in Richtung seines Zieles führt.
  • Diese wird er soweit fahren, bis er die Möglichkeit hat, die Autobahn zu wechseln.


Er wird sein Vorgehen solange wiederholen, bis er an seinem Ziel angekommen ist. Im Rahmen des Informatik-Proseminars Graphen und Netzwerke an der Technischen Universität Dortmund sind eine Seminarausarbeitung und ein Java-Programm zum Thema entstanden, die im Folgenden zum Download bereitstehen.


Aufsatz

In diesem Aufsatz werden die theoretischen Grundlagen und die Algorithmen zur Konstruktion von Theta-Graphen vorgestellt. Die theoretischen Überlegungen in diesem Aufsatz basieren zu großen Teilen auf dem vierten Kapitel von "Giri Narasimhan und Michiel Smid: Geometric Spanner Networks. Cambridge University Press, 2007".

Download: Seminarausarbeitung - Konstruktion von t-Spannern mithilfe von Theta-Graphen


Java-Programm - "TGT - Theta-Graph Toolkit"

Um die theoretischen Überlegungen zu veranschaulichen und die Laufzeitbetrachtungen zu verifizieren, ist das "Theta-Graph Toolkit" entstanden. Dabei handelt es sich um ein Java-Programm, mit dem es möglich ist, Graphen visuell darzustellen, mit der Maus zu bearbeiten und als Bild zu exportieren. Darüber hinaus fasst das Programm statistische Informationen des Graphen zusammen. Die Hauptfunktion des Programms liegt jedoch in der Konstruktion von Theta-Graphen. Es ist möglich, die in der Seminarausarbeitung beschriebenen Algorithmen MinAbove und BuildGraph auf beliebige Graphen anzuwenden. Dabei besteht unter anderem die Möglichkeit, die Algorithmen schrittweise ablaufen zu lassen, um so die einzelnen Schritte besser nachvollziehen zu können. Des Weiteren können die Laufzeit von BuildGraph automatisiert gemessen und die Ergebnisse exportiert werden. Das "Theta-Graph Toolkit" darf nach den Bedingungen der "GNU General Public License" verwendet werden.

Download: TGT - Theta-Graph Toolkit 1.0 Jar-Datei

Download: TGT - Theta-Graph Toolkit 1.0 Sourcecode