Marcus Sähn

Implementierung einer Datenstruktur für den dynamischen Zusammenhang für allgemeine und Unit Disk Graphen

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 05.04.2016

Kurzbeschreibung

Graphen werden häufig genutzt, um Beziehungen zwischen Objekten zu modellieren. Ein bekanntes Beispiel ist das von Milgram beschriebene Kleine-Welt-Phänomen. Dabei geht es unter anderem um die Frage, ob sich zwei zufällig ausgewählte Personen (über weitere Personen) kennen. Im Modell werden Personen als Knoten und Bekanntschaften als Kanten des Graphen dargestellt. Eine Bekanntschaft zwischen zwei Personen besteht, wenn sich die entsprechenden Knoten in der gleichen Zusammenhangskomponente befinden.


Mit wachsender Komplexität der Modelle und häufigeren Änderungen am Graphen rückten dynamische Datenstrukturen vermehrt in den Fokus. Wenn diese Datenstrukturen zusätzlich Zusammenhangsanfragen schnell beantworten können, unterstützen sie den so genannten dynamischen Zusammenhang (dynamic connectivity).


In dieser Arbeit werden zwei Datenstrukturen für den dynamischen Zusammenhang vorgestellt und implementiert. Eine unterstützt allgemeine Graphen, die andere Unit Disk Graphen. Die Laufzeiten beider Datenstrukturen betragen für eine Graphveränderung amortisiert O(log 2 n) und für eine Zusammenhangsanfrage amortisiert O(log n). Für die Auswertung werden beide Datenstrukturen mit simulierten Daten getestet und mit naiven Ansätzen verglichen. Zur Anschauung und zum besseren Verständnis wurden Visualisierungen für Unit Disk Graphen und für die untere Kontur (lower envelope) entwickelt und implementiert.