Input Data

Original telecommunications network consists of 10 points and 19 lines, provide a link between the points in both directions.

Table 1

I.v.	1	1	1	1	1	2	2	3	3	4	5	5	6	6	6	7	8	8	9
F.v.	2	4	5	7	8	3	4	6	7	6	6	8	7	8	9	10	9	10	10
W	70	11	90	25	80	15	3	52	30	15	93	60	20	18	45	75	13	14	8

I.v. — initial vertex;

F.v. — final vertex;

W — weight of path.

Introduction

Telecommunications - a set of tools that ensure the transfer of the information provided in the required form for a considerable distance in one of the media: copper, fiber, ether, or their combination.

Telecommunications network - a set of telecommunications and merged their sites, interoperable remote objects.

Telecommunications - equipment and systems, transmission equipment, providing signaling, synchronization, and management.

The telecommunications network is characterized by reliability and survivability:

• Reliability - is the system's ability to continue to operate and set options in the specified conditions of existence;

• vitality - the property to keep the network full or partial performance by the interaction external to the network of causes..

The transport network - telecom environment as a set of unified broadband equipment, switching centers and the access nodes to the network through which implemented a hierarchy of levels of standardized information transmission rates of data streams.

Figure 1 — Graph model of network

One of the most widespread discrete representations of the graph is the adjancent matrix. It is matrix А =[а_ij], of (пxп) size elements which can possess such values:

а_ij= 1, if there is an arc(edge) between vertices i and j in graph G;

а_ij = 0, — in the other case.

The adjancent matrix of the graph will be looks like:

1	1	0	1	1	0	1	1	0	0
1	1	1	1	0	0	0	0	0	0
0	1	1	0	0	1	1	0	0	0
1	1	0	1	0	1	0	0	0	0
1	0	0	0	1	1	0	1	0	0
0	0	1	1	1	1	1	1	1	0
1	0	1	0	0	1	1	0	0	1
1	0	0	0	1	1	0	1	1	1
0	0	0	0	0	1	0	1	1	1
0	0	0	0	0	0	1	1	1	1

А=

For storage in the computer memory of the adjacency matrix, as we see, you need n2 cells. Since we are dealing with undirected graph, the adjacency matrix is symmetric with respect to the main diagonal, and hence in the computer memory can store only one of its triangles, which will save memory, but it complicates the processing on a computer.

Telecommunications Network (weighted graph) can be in discrete form is filed by the matrix of weights, where the elements of the matrix represent the weight of an edge, if it exists in the graph. The weights of the edges is considered equal to non-existent «∞».

	1	2	3	4	5	6	7	8	9	10
1	0	70		11	90		25	80
2	70	0	15	3
3		15	0			52	30
4	11	3		0		15
5	90				0	93		60
6			52	15	93	0	20	18	45
7	25		30			20	0			75
8	80				60	18		0	13	14
9						45		13	0	8
10							75	14	8	0

В=

where an empty cell in this matrix represents ∞.

Another way to view a graph - a list of edges. This list can be implemented in two-dimensional array of dimension (2,m):

1	1	1	1	1	2	2	3	3	4	5	5	6	6	6	7	8	8	9
2	4	5	7	8	3	4	6	7	6	6	8	7	8	9	10	9	10	10

R=

In organizing the presentation of a graph in the form of a discrete array with floating boundaries, ie when it should be possible to add or remove vertices, you can use the structure of adjacency. It is a list of adjacent vertices for each vertex of the graph. The structure of the graph shown in Figure 1 has the form:

1:2,4,5,7,8

2:1,3,4

3:2,6,7

4:1,2,6

5:1,6,8

6:3,4,5,7,8,9

7:1,3,6,10

8:1,5,6,9,10

9:6,8,10

10:7,8,9

If you renumber randomly the edges and put these numbers in accordance with the numbers of rows of a matrix С=[с_ij], and the number of columns left as before, the respective numbers of a graph, in such a matrix Sij can take the values ​​{0,1}.

We renumber edges for a graph:

Н.в.	1	1	1	1	1	2	2	3	3	4	5	5	6	6	6	7	8	8	9
К.в.	2	4	5	7	8	3	4	6	7	6	6	8	7	8	9	10	9	10	10
	9	4	15	8	16	1	11	14	2	18	3	12	7	19	10	5	13	17	6

Then the incidence matrix has the form:

	1	2	3	4	5	6	7	8	9	1 0
1	0	1	1	0	0	0	0	0	0	0
2	0	0	1	0	0	0	1	0	0	0
3	0	0	0	0	1	1	0	0	0	0
4	1	0	0	1	0	0	0	0	0	0
5	0	0	0	0	0	0	1	0	0	1
6	0	0	0	0	0	0	0	0	1	1
7	0	0	0	0	0	1	1	0	0	0
8	1	0	0	0	0	0	1	0	0	0
9	1	1	0	0	0	0	0	0	0	0
10	0	0	0	0	0	1	0	0	1	0
11	0	1	0	1	0	0	0	0	0	0
12	0	0	0	0	1	0	0	1	0	0
13	0	0	0	0	0	0	0	1	1	0
14	0	0	1	0	0	1	0	0	0	0
15	1	0	0	0	1	0	0	0	0	0
16	1	0	0	0	0	0	0	1	0	0
17	0	0	0	0	0	0	0	1	0	1
18	0	0	0	1	0	1	0	0	0	0
19	0	0	0	0	0	1	0	1	0	0

С=

2. Elements of the theory of optimization on graphs and networks

2.1 Synthesis of the minimum cost network

Draw a graph representing a covering tree.

We obtain the desired graph, which is a covering tree, since it includes all the vertices, contains a number of edges is one less than the number of nodes and provides a connection for each pair of vertices.

2.2 Determination of the median graph

In the initial matrix of weights corresponding to the lengths of the edges, we find the sum of the elements for each row:

1−276

2−88

3−97

4−29

5−243

6−243

7−150

8−185

9−66

10−97

Among this set of values ​​shall find the minimum − R₄=29, and the corresponding line of the vertex 4 is the median of the graph.

2.3 Determination of the graph center

Each line of the original weight matrix we find the element with maximum value:

1−90

2−70

3−52

4−15

5−93

6−93

7−75

8−80

9−45

10−75

Among the many lines of maximum values ​​of the elements we find the smallest l_m=15. The vertex m = 4 and is the center of the graph.

3. Synthesis of inter-node communication network

3 .1 Finding the shortest way in a connecting network

1 ― 4 ― 2 ― 3 ― 7 ― 6 ― 8 ― 9 ― 10 ― 8 ― 5 ― 1 l₁=162

2 ― 4 ― 1 ― 7 ― 6 ― 8 ― 9 ― 10 ― 8 ― 5 ― 6 ― 3 ― 2 l₂=332

3 ― 2 ― 4 ― 1 ― 7 ― 6 ― 8 ― 9 ― 10 ― 8 ― 5 ― 6 ― 3 l₃=332

4 ― 2 ― 3 ― 7 ― 6 ― 8 ― 9 ― 10 ― 8 ― 5 ― 1 ― 4 l₄=282

5 ― 8 ― 9 ― 10 ― 7 ― 6 ― 4 ― 2 ― 3 ― 7 ― 1 ― 5 l₅=354

6 ― 4 ― 2 ― 3 ― 7 ― 1 ― 8 ― 9 ― 10 ― 8 ― 5 ― 6 l₆=356

7 ― 6 ― 4 ― 2 ― 3 ― 7 ― 1 ― 5 ― 8 ― 9 ― 10 ― 7 l₇=354

8 ― 9 ― 10 ― 7 ― 6 ― 4 ― 2 ― 3 ― 7 ― 1 ― 5 ― 8 l₈=354

9 ― 10 ― 8 ― 6 ― 4 ― 2 ― 3 ― 7 ― 1 ― 5 ― 8 ― 9 l₉=291

10 ― 9 ― 8 ― 6 ― 4 ― 2 ― 3 ― 7 ― 1 ― 5 ― 8 ― 10 l₁₀=291

Considering the length of the route is not difficult to find a path of minimal length, it is the 1st option.

Defining the Hamiltonian cycle of minimal length is relevant in determining the optimal ring topology segments of telecommunications networks.