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
Search WWH ::




Custom Search