Determination of a graph median

Let's consider the following problem. Let the graph G (N, V)represent some cable network, connecting n subscriber points. The weight of each edge (i, j) belonging to V corresponds to the length l_ij or to the cable costs connecting points i and j. It is necessary to define some vertex m belonging to N where it is expedient to place a switching node (for example, regional automatic telephone exchange) from the point of view of minimization in total length of the cable connecting subscriber points with switching node.

Solution of the given task is determination of the graph G (N, V) median.

D e f i n i t i o n. The vertex m, belonging to N, is a graph G (N, V) median
if it satisfies a condition:

Value is called median length of graph G and represents the minimal total length of the edges connecting vertex m with other graph nodes.

The algorithm of graph G median definition includesfollowing steps.

Step 1. To find the sum of elements for every line in the initial matrix of weights L = [ l_ij ], corresponding to edges lengths:

;

Step 2. To find minimal R_m. The vertex m also is a graph G median among set of values { R_i }.