Ungerichteter Graph/Wege/Numerische Invarianten/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Unter der Länge eines Weges in einem Graphen versteht man die Anzahl seiner Kanten.

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


Definition  

Zu einem Knotenpunkt eines zusammenhängenden Graphen nennt man

die Exzentrizität von .

Der Durchmesser ist also das Maximum über alle Exzentrizitäten und der Radius ist das Minimum über alle Exzentrizitäten.


Beispiel  

Metro Lisboa Route Map (only with routes in operation).png

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 .