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 .

Definition

Die Dilatation zweier Punkte und in einem euklidischen Graphen errechnet sich aus den Kosten des kürzesten Pfades dmin(a,b) von a nach b, geteilt durch die Euklidische Distanz :

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

Literatur