Location Problems

Question 1

Location of supply

Answer 1

Is the supply on a vertex only or on any point along an edge or arc

Question 2

Location of demand

Answer 2

Is the demand on a vertex only or any point along an edge or arc

Question 3

Objective

Answer 3

Do we want to minimize the distance from supply to all points of demand or minimize the maximum distance from supply to the farthest demand?

Question 4

Classical

Answer 4

Vertex supply to vertex demand

Question 5

Eccentricity

Answer 5

The eccentricity of a vertex is the maximum distance from a vertex v to the farthest vertex from v
[ e(v) ]

Question 6

Radius

Answer 6

The minimum eccentricity of the graph G

[ rad(G) ]

Question 7

Central vertex

Answer 7

The vertex/vertices with eccentricity equal to the radius

Question 8

Diameter

Answer 8

The maximum eccentricity of the graph G

[ diam(G) ]

Question 9

Peripheral vertex

Answer 9

The vertex/vertices with eccentricity equal to the diameter

Question 10

Classical Centre

Answer 10

Subgraph of all the central vertices denoted as C(G)

Question 11

Periphery

Answer 11

Subgraph of all the peripheral vertices of G

Question 12

Classical Median

Answer 12

Subgraph denoted as M(G) of a weighted connected graph G induced by all the vertices of G which achieve a minimum value for the sum total of the distances from themselves to all other vertices.

Question 13

General

Answer 13

Vertex supply to any point demand

Question 14

f-point

Answer 14

The point on the edge uv at a distance f x w(u) from u and a distance (1-f) x w(v) for v for any real number of f from 0 to 1

Question 15

0-point

Answer 15

u where f = 0

Question 16

Internal f-point

Answer 16

Where f is greater than 0 and smaller than 1

Question 17

1-point

Answer 17

v where f = 1

Question 18

Vertex to edge distance

Answer 18

The distance from a vertex u to the critical f*-point of uv where f is the maximal distance

Question 19

Vertex to arc distance

Answer 19

The distance from vertex i to the maximal distance for an arc which is always f = 1

Question 20

D(G)

Answer 20

The matrix of distance between the vertices and edges of the graph G

Question 21

General Centre

Answer 21

The subgraph of G induced by the vertex/vertices achieving a minimum value of row maxima in D(G)
[ minimum maximum of row ]

Question 22

General Median

Answer 22

The subgraph of G induced by the vertex/vertices achieving a minimum value of row sum in D(G)
[ minimum sum of row ]

Question 23

Absolute

Answer 23

Any point supply to vertex point demand

Question 24

Point (edge) to vertex distance

Answer 24

There are two possible routes for the shortest path from an f-point of uv to i. Hence:

d = min[ f w(uv) + d(u,i), (1-f) w(uv) + d(v,i) ]

In the case where there exists a critical value of f, f* such that f w(uv) + d(u,i) = (1-f) w(uv) + d(v,i) then to calculate f* we solve the aforementioned equation to get:

f* = [ w(uv) + d(v,i) - d(u,i) ] / [ 2w(uv) ]

Question 25

General Absolute

Answer 25

Any point supply to any point demand

Question 26

Point (edge) to edge distance: e ≠ v

Answer 26

For e ≠ v the shortest path from an f-point (supply) to the farthest point of e (demand) is via u or v therefore:

d(f(uv), e) = min{ f w(uv) + d(u,e), (1-f) w(uv) + d(v,e)

Question 27

Point (edge) to edge distance: e = v

Answer 27

For e = v the shortest path from an f-point to the farthest g-point described by the following equation:

d(f(uv), uv) = max{ A, B }

where A and B are:

A = min{ f w(uv), [ w(uv) + d(v,u) ] / 2 }
B = min( (1-f) w(uv),  [ w(uv) + d(u,v) ] / 2 }

Question 28

Drawing of general absolute

Answer 28

Use these equations:

Right: A’ = [ w(uv) + d(v,u) ] / 2 }
Left: B’ = [ w(uv) + d(u,v) ] / 2 }