Geoscience Reference
In-Depth Information
Remark 10.1 The structure of the set F is different from previous FDS which
appeared in the literature. Indeed, the set F is itself a set of candidates for optimal
solutions because it is a set of pairs of points. That means that we do not have to
choose the elements of this set by pairs to enumerate the whole set of candidates.
The candidate solutions may be either a pair of points belonging to . EQ [ V/ Y
or a pair belonging to T , but they never can be one point of Y and another point of
any pair in T .
The following examples show that the set F can not be shrunk because even in
easy cases on the real line all the points are needed. The first example shows a graph
where the optimal solution X 2 D .x 1 ;x 2 / verifies that x 1 is an equilibrium point
and x 2 is not an equilibrium point which belongs to Y.r/ n . EQ [ V/for a given r.
In the second example the optimal solution X 2 D .x 1 ;x 2 / belongs to the set T .
Example 10.4 Let N D .G;`/ be a network with underlying graph G D .V;E/
where V Df v 1 ;v 2 ;v 3 ;v 4 g and E Dff 1;2 g ; f 2;3 g ; f 3;4 gg . The length function is
given by `. f 1;2 g / D 3, `. f 2;3 g / D 20, `. f 3;4 g / D 6. The w-weights are all equal
to one and the -weights are 1 D 0:1; 2 D 0:2; 3 D 0:4; 4 D 0:3,seeFig. 10.4 .
It should be noted that this example can not have optimal solutions on the edge
f 2;3 g because any point of this edge is dominated by v 2 or v 3 . In addition, using the
symmetry of the problem we have omitted the evaluation of some of the elements
of Y .
In Fig. 10.4 we represent the nodes (dots), the equilibrium points (ticks) and
elements of Y (small ticks). Notice that in this case there are no pairs in T .
In this example the optimal solution is given by x 1 D p. f 1;2 g ;1:5/and x 2 D
p. f 3;4 g ;1:5/(see Table 10.5 ). It is easy to check that x 1 is an equilibrium point
between v 1 and v 2 ,andx 2 2 Y.1:5/. It is worth noting that the radius 1.5 is given
by the distance from the equilibrium point, p. f 1;2 g ;1:5/, generated by v 1 and v 2 to
any of these nodes.
Example 10.5 Let N D .G;`/ be a network with underlying graph G D .V;E/
where V Df v 1 ;v 2 ;v 3 ;v 4 ;v 5 g and E Dff 1;2 g ; f 2;3 g ; f 3;4 g ; f 4;5 gg . The length
function is given by `. f 1;2 g / D 5;`. f 2;3 g / D 20;`. f 3;4 g / D 5:1;`. f 4;5 g / D 1.
3
20
6
v 1
v 2
v 3
v 4
|
|
|
|
Fig. 10.4
Illustration of Example 10.4
Table 10.5 Evaluation of the candidate pairs of Example 10.4
Candidate pair X 2
Va l u e
Candidate pair X 2
Va l u e
p.f1;2g;0/;p.f3;4g;0/
3
p.f1;2g;1:5/;p.f3;4g;0/
2:7
p.f1;2g;0/;p.f3;4g;1:5/
2:85
p.f1;2g;1:5/;p.f3;4g;1:5/
2:4
p.f1;2g;0/;p.f3;4g;3/
2:7
p.f1;2g;1:5/;p.f3;4g;3/
2:55
 
Search WWH ::




Custom Search