Graphtheoretische Dilation eines Graphen


 

Einführung und Definitionen

Die Dilation eines Graphen gibt an um wieviel größer die Distanz des kürzesten Weges zweier Punkt des Graphen im Vergleich ihrer euklidischen Distanz ist. Sei C(p, q) die Distanz des kürzesten der Punkte Weges p und q des Graphen G = (V, E) und sei |pq| ihre euklidische Distanz, dann ist der Umweg (detour) von p und q definiert als

detour(p, q) = C(p, q) / |pq|.
Betrachten wir nur die Ecken von G, so erhalten wir die graphtherotische Dilation
S(G) = max {detour(p, q); (p, q in V) & (p != q)}

Applet

[Applet cannot be started]
Das Applet GraphDilation (sollte automatisch starten) berechnet die graphtheoretische Dilation für einen Graphen G=(V,E). Da es den Algorithmus von Floyd zur Bestimmung der Längen der kürzesten Wege zwischen allen Paaren von Knoten verwendet, hat es eine Laufzeit von O(|V|3).

Der aktuelle Wert der Dilation wird im unter dem Editierbereich angezeigt. Jedes Paar von Knoten mit einem maximalen Wert der Dilation ist verbunden durch eine güne Linie.

Referenzen

[1] David Eppstein. Spanning trees and spanners. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 425-461, Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.

[2] Tim Komorowski. Berechnung der graphentheoretischen Dilation. Diplomarbeit, Universität Bonn. 2004.