Network Location Problems

Question 1

Eccentricity eG(v)

Answer 1

The maximum distance of a vertex from v. That is, e(v) is the distance from v to a vertex furthest from V.

Question 2

Radius rad(G)

Answer 2

Minimum eccentricity amoung vertices of G

Question 3

Diameter diam(G)

Answer 3

Maximum eccentricity

Question 4

Central vertex

Answer 4

Vertex whose eccentricity is equal to the radius

Question 5

Peripheral vertex

Answer 5

Vertex whose eccentricity is equal to the diameter

Question 6

Theorem 6.1

Answer 6

For every connected, unweighted graph G satisfying the triangle inequality it holds that rad(G)<=diam(G) <=2rad(G)

Question 7

Theorem 6.3

Answer 7

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 8

Algorithm 6.1 (Centre of unweighted tree)

Answer 8

All leaves of 1st layer.
If no more leaves left - - done
If more leaves, repeat
Left with 1 or 2 vertices
c(G) =

Question 9

Classical median M(G)

Answer 9

The subgraph of G induced by all vertices v in V(G) which achieve a minimum value for the sum total of the distance from themselves to all other vertices.

Question 10

General Centre

Answer 10

A vertex location in the graph at which a facility may be placed to supply some service to any point on an edge/ arc of the graph if the objective is to minimise the maximal potential distance that a user of the facility will have to travel in order to make use of the facility

Question 11

General centre

Answer 11

Not done😅

Question 12

F-point

Answer 12

The point on the arc (u, v) /edge (uv) at a distance fw(u,v) from the vertex u and at a distance (1-f)w(u,v) from the vertex v, for any f from 0 to 1

Question 13

Vertex to edge distance d~(i, uv)

Answer 13

Distance from a vertex i to an f-point on the edge uv

(d(i, u) +d(i, v) +w(uv)) /2

Question 14

Vertex-to-arc distance d~(i, (u, v))

Answer 14

d~(i, (u, v)) =d(i, u) +w(u, v)

Question 15

Absolute centre

Answer 15

Arbitrary point location on any edge/ arc of the graph at which a facility may be placed to supply some service to any vertex of the graph so that the maximum distance from the supply point to a demand vertex is minimised

Question 16

Absolute median

Answer 16

Find