prev up inhalt next


7.1.1 Generelles Zentrum

Das generelle Zentrum eines Graphen G ist der Knoten, dessen entferntester Kantenpunkt möglichst nahe liegt.

Definere:

Für 0$\le$f$\le$1 sei der f -Punkt der Kante (r,s) der Punkt, der f · c(r,s) Einheiten von r bzw. (1 - f ) · c(r,s) Einheiten von s entfernt ist.


Beispiel:



Betrachte nun die kürzeste Entfernung von einem Knoten j zu allen f -Punkten der Kante (r,s) . Es ergibt sich eine Funktion (d'(j,(r,s)))(f ) , wobei f $\in$ [0,1] ist. Wir unterscheiden nun in zwei Fälle:

a) (r,s) ungerichtet:
In diesem Fall ist es möglich, daß der kürzeste Weg von j zu einem f -Punkt auf (r,s) entweder über r oder auch über s läuft. Auf jeden Fall läuft er aber bis zu diesem Punkt auf dem kürzesten j - r - bzw. j - s -Weg mit der Länge d (j,r) bzw. d (j,s) . Für d'(j,(r,s)) sind also folgende Graphenverläufe möglich:

Beispiel:



Die Frage ist nun, wie man den worst case, also die maximale Entfernung von j zu einem Kantenpunkt f , berechnet. Es leuchtet ein, daß diese maximale Entfernung max [j,(r,s)] gegeben ist durch max[j,(r,s)] = ${\frac{1}{2}}$[d (j,r) + c(r,s) + d (j,s)] .

Nun ist es leicht, das generelle Zentrum von G = (V,E) zu bestimmen, es ist der Knoten i mit minimalem max {max[i,(x,y)]|(x,y) $\in$ E} .

b) (r,s) gerichtet:
Dieser Fall ist hier der einfachere, da jeder kürzeste Weg von j zu einem Kantenpunkt von (r,s) immer über r läuft. Daraus folgt, daß der f -Punkt mit maxi maler Entfernung zu j der Punkt der Kante (r,s) ist, der beliebig nahe an s liegt. Diese r f -Punkt hat aber trivialerweise die Entfernung max [j,(r,s)] = d (j,r) + c(r,s) von j . Die Berechnung des generellen Zentrums in G läuft nun analog zu a).

prev up inhalt next