Ungerichteter Graph/Wege/Numerische Invarianten/Textabschnitt
Dabei zählt man sich wiederholende Kanten mehrfach, d.h. der Weg hat die Länge , auch wenn in dem Weg die gleiche Kante mehrfach vorkommt.
Definition
Zu zwei Knotenpunkten und in einem zusammenhängenden Graphen versteht man unter dem Abstand die minimale Länge eines verbindenden Weges von nach .
In einem nicht zusammenhängenden Graphen setzt man manchmal den Abstand zwischen zwei Punkten, die zu verschiedenen Zusammenhangskomponenten gehören, als unendlich an.
Definition
Unter dem Durchmesser eines zusammenhängenden Graphen versteht man das Maximum über alle Abstände zu .
Definition
Unter dem Radius eines zusammenhängenden Graphen versteht man den Ausdruck
Der Durchmesser ist also das Maximum über alle Exzentrizitäten und der Radius ist das Minimum über alle Exzentrizitäten.
Beispiel
Wir betrachten das Metronetz von Lissabon. Es handelt sich um einen zusammenhängenden Graphen. Der durch die gelbe Linie beschriebene Weg hat die Länge . Der Abstand von São Sebastião zu Alameda ist , der kürzeste Weg ist über Sadanha (mit der roten Linie) gegeben. Es gibt natürlich auch deutlich längere Wege zwischen diesen beiden Stationen, beispielsweise über Marquês de Pompal mit der blauen Linie, dann nach Campo Grande mit der gelben Linie und dann mit der grünen Linie nach Alameda, der die Länge besitzt. Der Durchmesser des Netzgraphen ist , dieser wird im Abstand von Reboleira zu Aeroporto angenommen. Der Radius des Graphen ist , unz zwar haben sowohl Saldana als auch São Sebastião diese Exzentrizität. Die Exzentrizität von Cidada Universitária beträgt .