Location Problems: Theorems

Question 1

Theorem 6.1

Hint: Triangle Inequality

Answer 1

For every connected weighted graph G satisfying the triangle inequality the following holds:

rad(G) ≤ diam(G) ≤ 2rad(G)

Question 2

Theorem 6.2

Hint: Centre

Answer 2

Every unweighted graph is the centre of some connected unweighted graph

Question 3

Theorem 6.3:

Hint: Unweighted Tree Centre

Answer 3

Let T be an unweighted tree of order p ≥ 3 and let T' be the tree formed by pruning away all the leaves of T.
Then C(T) = C(T')

Question 4

Theorem 6.4:

Hint: Isomorphic

Answer 4

The centre of every unweighted tree is isomorphic to K₁ or K₂

Question 5

Theorem 6.5:

Hint: Absolute Median

Answer 5

For any connected graph G, there is always a vertex that is an absolute median of G.

Note, any vertex in the classical median of G is also in the absolute median of G

Question 6

Theorem 6.6:

Hint: General Absolute (Interior Points)

Answer 6

No interior point of a directed arc in a connected graph G can be a general absolute centre or a general absolute median of G

Question 7

Theorem 6.7:

Hint: General Absolute (Median)

Answer 7

No interior point of an undirected edge ij in a graph G can be an absolute median of G if:

Σd(i,e) - Σd(j,e) | > [ d(i,j) + d(j,i) ] / 2