Durchmesser eines Graphen

Ein weiteres Mass für die Struktur eines Graphen ist sein Durchmesser (engl. diameter). Der Durchmesser Delta ist ein Index, der die topologische Länge oder Ausdehnung eines Graphen misst, indem die Anzahl der Kanten des kürzesten Wegs zwischen den am weitesten entfernten Knoten bestimmt wird. Es gilt
wobei s(i, j) gleich der kleinsten Kantendistanz (Kantendistanz = Anzahl der Kanten entlang eines Pfades) zwischen dem Knoten i und j ist. Die Formel ist so zu verstehen, dass alle kürzesten Wege zwischen allen Knoten gesucht werden und dann der längste (maximale) ausgewählt wird. Somit handelt es sich bei diesem Mass um den längsten kürzesten Weg zwischen zwei beliebigen Knoten eines Graphen.

Bei den ersten beiden Darstellungen des Graphen A, sind mögliche Pfade eingezeichnet, aber nicht die kürzesten. Im dritten Graph (und auch im Graph B) ist der längste kürzeste Weg eingezeichnet.

Neben der rein topologischen Anwendung kann den Kanten ihre effektive Streckenlänge oder ein anderes Gewicht (z. B. Reisezeit) zugewiesen werden. Daraus lässt sich ein etwas komplexeres und auf der Metrik des Netzes beruhendes Mass bestimmen. Der resultierende Index ist pi = mT/md , wobei mT die metrische Gesamtlänge des Netzes ist und md der metrischen Länge des Durchmessers entspricht. Je grösser pi ist, umso dichter ist ein Netz verbunden.