Geoscience Reference
In-Depth Information
Let N
D
.T;`/ beatreenetwork,withT
D
.V;E/. For two points a;b
2
P.T/
we define the line segment LŒa;b between a and b as
LŒa;b
WDf
x
2
P.T/
W
d.a;x/
C
d.x;b/
D
d.a;b/
g
;
which contains all points on the unique path between a and b. A subset C
P.T/
is called convex, if and only if for all a;b
2
C, LŒa;b
C.
Now let C
P.T/be convex and let h
W
P.T/
!
be a real valued function.
This function h is called convex on C, if and only if for all a;b
2
C,
R
h.x
/
h.a/
C
.1
/h.b/ ;
8
2
Œ0;1 ;
where x
is uniquely defined by
d.x
;b/
D
d.a;b/ and d.x
;a/
D
.1
/d.a;b/ :
(9.5)
A function is called convex on T if it is convex on C
D
P.T/. Note that it is possible
to define convexity also on general networks. Then one can show that d.x;c/ for
c
2
P.T/ fixed is convex if and only if the underlying graph is a tree. Median and
Center objective functions are convex functions on a tree (see Dearing et al.
1976
).
Now let L.a;b/
WD
LŒa;b
nf
a;b
g
, L.a;b
WD
LŒa;b
nf
a
g
and LŒa;b/
WD
LŒa;b
nf
b
g
. We have now the following important property (a proof can be found
in Hamacher et al.
1999
).
Theorem 9.9
Let
a;b
2
P.T/
and
h
WD
.h
1
;:::;h
Q
/
be a vector of
Q
objective
functions, with
h
q
convex on
T
, for all
q
2
Q
Df
1;:::;Q
g
. Then the following
holds:
par
par
:
f
a;b
g
X
if and only if
LŒa;b
X
For T
D
.V;E/ and V
0
V let
0
1
w
1
.V
0
/
w
2
.V
0
/
:
:
:
w
Q
.V
0
/
@
A
W.V
0
/
WD
;
where
w
q
.V
0
/
WD
P
v
i
2V
0
w
i
,
8
q
2
Q
.
Proposition 9.1
Let
T
be partitioned in such a way that
T
D
T
1
[
T
2
[f
e
g
(and
T
1
\
T
2
D;
). Then
W.V.T
1
//
dominates
W.V.T
2
//
if and only if for all
x
2
P.T
1
/
there exists some
y
2
P.T
2
/
which dominates
x
.
Now we can state a multicriteria version of Goldman's dominance algorithm
(see Goldman
1971
). We start with a subtree containing only one leaf of the tree