7.1 Zentrum

Das Zentrum eines Graphen G ist der Knoten, dessen am weitesten entfernter Knoten in G möglichst nahe liegt.

Das Ermitteln des Zentrums eines Graphen ist unter Anwendung des Floyd-Algorithmus zur Bestimmung aller kürzesten Wege in G sehr leicht:

Bestimme mit Floyd alle d (i,j) -Werte

Errechne max[i] : = max {d (i,j) | j $\in$ G}

Suche das i mit minimalem max [i] , dieses i ist das Zentrum von G .