Dilatation (Graphentheorie)

Die Dilatation eines euklidischen Graphen G = (V, E) ist ein Maß dafür, wie viel Umweg beim Durchlaufen des Graphen in Kauf genommen werden muss, im Vergleich zur direkten euklidischen Strecke. Sie ist definiert als das Verhältnis der Entfernung im Graphen zur Distanz im ${\displaystyle \mathbb {R} ^{d}}$.

Definition

Die Dilatation zweier Punkte ${\displaystyle a}$ und ${\displaystyle b}$ in einem euklidischen Graphen errechnet sich aus den Kosten des kürzesten Pfades d_min(a,b) von a nach b, geteilt durch die Euklidische Distanz ${\displaystyle |ab|}$:

${\displaystyle \Delta (a,b)={\frac {d_{\mathrm {min} }(a,b)}{|ab|}}\,.}$

Die Dilatation d​es Graphen G i​st die maximale Dilatation a​ller Punktpaare i​n V:

${\displaystyle \Delta (V)=\max _{a,b\in V}\Delta (a,b)\,.}$

Literatur

• Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein: The Geometric Dilation of Finite Point Sets. In: Algorithmica. 44, Nr. 2, 2006, S. 137–149. doi:10.1007/s00453-005-1203-9.