7.1.2 Absolutes Zentrum

Das absolute Zentrum eines Graphen G ist der Kantenpunkt, dessen entferntester Knoten möglichst nahe liegt. Zur Berechnung des absoluten Zentrums betrachten wir zunächst eine Kante (r,s) . Für jeden f -Punkt dieser Kante kann man die Entfernung zu einem Knoten x als Funktion d'((r,s),x) ausdrücken. Berechne dann d'((r,s),x) für alle Knoten x $\in$ V . Es ergeben sich folgende Funktionsverläufe:

Bilde nun das Maximum d_max(r,s) = max {d'((r,s),x)|x $\in$ V} . Diese Funktion ist im vorigen Schaubild als dicke Linie gezeichnet. Suche nun den f -Punkt f_min mit d_max(r,s)(f_min) minimal. Auch dieser Punkt ist in diesem Schaubild eingezeichnet. Sei nun d_opt(r,s) = d_max(r,s)(f_min) , also der Funktionswert von f_min . Bildet man nun das Minimum aller d_opt -Werte über alle Kanten des Graphen, so ermittelt man damit die Kante, auf der das absolute Zentrum liegen muß. Der zu dieser Kante gehörige f_min -Wert legt dann das absolute Zentrum von G exakt fest. Eine Schwierigkeit in diesem Verfahren liegt allerdings in der Berechnung der Funktionen d_max für alle Kanten des Graphen. Einen Algorithmus mit annehmbarer Laufzeitentwicklung für dieses Problem zu finden dürfte in jedem Fall schwer fallen.