Geoscience Reference
In-Depth Information
In this section we state the fundamental properties of Problem (
10.28
). We
will present a localization result which generalizes the well-known results by
Hakimi on finite dominating sets for the center and median problems on networks
(Hakimi
1964
) and gives some insight in the connection between median and center
problems.
For all v
i
;v
j
2
V; i
¤
j define
EQ
ij
WDf
x
2
P.G/
W
w
i
d.v
i
;x/
D
w
j
d.v
j
;x/
g
(10.29)
and let
EQ
WD
S
f
EQ
ij
W
i;j with i
¤
j
g
.
The points in
EQ
are called equilibria points of N. Two points a;b
2
EQ
are
called consecutive, if there is no other c
2
EQ
on the shortest path between a
and b. The points in
EQ
establish a partition on N with the property that for two
consecutive elements a;b
2
EQ
the permutation which gives the order of the vector
d
.x/ is the same for all x
2
Œa;b.
Now we will give a finite dominating set (FDS) for the optimal locations of
Problem (
10.28
), see Nickel and Puerto (
1999
) for further details.
Theorem 10.6
An optimal solution for Problem
(
10.28
)
can always be found in the
set
Cand
WD
EQ
[
V
.
Proof
Starting from the original graph G, build a set of new graphs G
1
;:::;G
K
by inserting all points of
EQ
as new nodes. Now every subgraph G
i
is defined by
either
I. Two consecutive elements of
EQ
on an edge or
II. An element v
i
2
V
n
EQ
and the adjacent elements of
EQ
and the corresponding edges. In this situation for every subgraph G
i
the permutation
of d
.x/ is constant (by definition of
EQ
). Therefore for all x
2
P.G
i
/ we have
n
n
X
X
i
d
.i/
.x/
D
i
w
.i/
d.v
.i/
;x/;
iD1
iD1
where
2
P.1;:::;n/,andP.1;:::;n/is defined as the set of all permutations of
f
1;:::;n
g
. Therefore we can replace the objective by a classical median-objective.
Now we can apply Hakimi's node dominance result in every G
i
and the result
follows.
Theorem
10.6
also gives rise to some geometrical subdivision of the network
N. Like indicated in the proof of Theorem
10.6
we can assign to every subgraph
G
i
;i
D
1;:::;k a n-tuple giving in the i-th position the i-th nearest vertex to all
points in G
i
. As an example we have in Fig.
10.2
a graph with three nodes and all
weights
w
i
and all lengths are 1.
This partition can be seen as a kind of higher order Voronoi diagram of N quite
related to the Voronoi partition of networks introduced in Hakimi et al. (
1992
).
