 |
|
|
|
|
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)}
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.
[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.
