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 $\mathbb {R} ^{d}$ .

Definition

Die Dilatation zweier Punkte $a$ und $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 $|ab|$ :

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

Die Dilatation des Graphen G ist die maximale Dilatation aller Punktpaare in V:

\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. Jahrgang, Nr. 2, 2006, S. 137–149, doi:10.1007/s00453-005-1203-9 (uni-bonn.de [PDF]).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.