6.12 Speeding up the search for the absolute center In our
discussion of the absolutewenter problem, it was pointed out that the quantity
provides a lower bound for the value of m(x ) on a link (p, q)
[cf. (6.26)]. This bound provides a very convenient test that facilitates
the search for the absolute center of a graph.
Another bound for m(x ) has been developed recently, as
follows. For the link (p, q), let r be the farthest node from p (r
N)
and s the farthest node from q(s N) [i.e., m(p) = d(p, r) and
m(q) = d(q, s)]. The quantities that will be used to develop the new bound
are d(p, s) and d(q, r). Clearly, the quantity Max [d(x, r), d(x, s)]
provides a lower bound on m(x ).
a. | Prove the following result: The
quantity Max{d(x, r), d(x, s)} may attain at most a single local minimum
within (q, p), i.e., excluding the nodes p and q. If such a local
minimum exists it is attained at a point x0 E (p, q) which is
a distance
away from node p along (p, q) and at which the value of Max{d(x, r),
d(x, s)} attains the value
L2(p, q) is then a lower bound for m(x ) for all
points x (p, q), excluding the nodes p and q.
| b. | Show that L2(p, q)
L1(p, q), that is, that L2(p, q) provides a better
lower bound and thus a sharper test than L1(p, q) for speeding up
the search for the absolute center of a graph.
|
|