7.1.3 Absoluter Median

Der absolute Median eines Graphen G ist der Kantenpunkt, dessen durchschnittliche Entfernung zu allen Knoten minimal ist.

Behauptung:

Der absolute Median liegt in jedem Fall in einem Knoten.

Beweis:

Es gilt:

(i): Die Summe konkaver Funktionen ist wieder eine konkave Funktion.
(ii): Das Minimum einer konkaven Funktion wird an einem der Ränder angenommen.

Da die einzelnen Funktionen, die bei der Berechnung auftreten, auch konkav sind, liegt das gesuchte Minimum auch hier in einem Rand einer Kante, also in einem Knoten selbst.

Der Algorithmus zur Berechnung des absoluten Medians sieht also so aus:

Berechne mit dem Algorithmus von Floyd alle d (i,j) -Werte.

Bilde für alle Knoten i aus G sum[i] = $\sum\limits_{j=1}^{n}$ d (i,j)

Finde das i mit minimalem sum[i] . Dieser Knoten i ist dann der absolute Median.

Der Algorithmus ist also erstaunlich einfach, relativ zur Komplexität des Problems gesehen.