Elements of optimization theory on graphs and networks

2.3.1 Synthesis of the minimal cost network

The situation, where some set of points is necessary to connect so, that each pair of points to be connected (directly or via other points), and the total weight characteristic of connections was minimal, generates a problem of synthesis of the minimum cost network.

For example, there is a sequence of points, where points of telecommunication network can be placed. Distances between pairs of points and cost of the foundation for communication line of one kilometer are known. It is necessary to define the set of communication lines that provides connectivity of all network points and its minimal cost.

From graph and networks theory it is known, that solution of the given task is the network with topology of «tree»type.

D e f i n i t i o n. The connected graph (connecting network) is called a tree if there are no cycles in it.

They say that the graph contains cycles if it is possible to find the closed contours in it. Cycles absence defines the feature of the tree type graph which consists in that between any pair of its vertices there is only one path connecting them, i.e. connectivity parameter h =1. The quantity of edges in a tree is always one unit less than the quantity of its vertices.

D e f i n i t i o n. The tree which includes all vertices is called covering.

Mathematically the problem of network synthesis of the minimum cost is formulated this way.

Let non-directional graph G (N, V) be given, where the set of N vertices corresponds to the set of network points, general number of which is equal to n, and set of V edges - { l_ij } distances between pairs of points. The organizations cost c_ij for communication line of 1 kilometer between points i and j is known.

It is necessary to find some covering G' (N, V')tree for which the criterion function minimum is attained:

For this task solving there is a sequence of effective algorithms. We will bring one of them, which is known as Prim. The algorithm is implemented by assignment of marks to vertices, which are input into graph G' (N, V'),and consequential introduction in it, the shortest edges, total quantity of which should not exceed (n- 1) and provide connectivity between all n vertices of a covering tree.

The step-by-step form of Prim algorithm has the following form:

Step 0. The initial network G' (N, V ') in a stowed position contains n vertices and does not contain edges. One random vertex i is chosen and marked as «selected». The other (n-1) vertices are marked as «non-selected».

Step 1. The edge (i, j) belonging to G (N, V) with the minimal weight, which vertex i belongs to a subset of «selected» vertices, and vertex j - to a subset of «non-selected» vertices is found.

Step 2. The edge (i, j) is included into the initial network G' (N, V '),and the vertex j is excluded from a subset of «non-selected» vertices and is included into a subset of «selected» vertices. If the subset of «non-selected» vertices is empty it means the end of algorithm operation. Otherwise – going back to the step 1.

Let's illustrate the Prim algorithm operation on the instance. Let there be seven network points, the distances between which are implemented into matrix L = [ l_ij ],namely:

On a step 0 the initial graph G' (N, V ') contains 6 vertices and does not contain edges. Let’s choose vertex 3 and mark it as «selected» (see figure 2.2).

On a step 1 let’s choose the edge (l₃₅) as an edge with a minimal weight, which vertex i =3 belongs to a subset of t «selected» vertices (still it contains only one vertex 3), and the vertex j =5- to a subset of«non-selected» vertices (now these are all other vertices). On a step 2 edge l₃₅ is input into the initial graph G',and the vertex 5 is included into a subset of«selected» vertices (figure 2.3).

As a subset of«non-selected» vertices is not empty, we repeat step 1. For this purpose we find the edge of the minimum weight, overhauling combinations of each pair of «selected» and «non-selected» vertices. Thus there was an edge l₃₄ (figure 2.4). It is input into the graph G ', and the vertex 4 becomes «selected».

The following edges to be chosen are: l₂₆ (figure 2.6); l₃₁ (figure 2.7); l₂₇ (figure 2.8). Here the algorithm operation comes to an end, because all vertices are marked as «selected» (i.e. the subset of «non-selected» vertices are an empty subset).

The graph G' (N, V'),representing covering tree, as it includes all vertices, contains the number of edges one unit lower than the numbers of vertices (n =7, v =6) and provides connectivity of each pair of vertices is obtained.