Determination of the given transient path sets

Among the restrictions imposed while setting connecting sections of transfer in communication networks, restriction on number of transit points or transit sections in them can be considered.

Transit points are regarded as switching knots appearing along the messages travelling from some subscriber's point i in j where there is messages streams reallocating. Transit sections accordingly represent communication line connecting transit points.

Restriction on transience along the messages transmitting is caused by demands to a network service quality (for example, to the time of message transit in a network, to the time of message processing in switching knots etc.).

In terms of graph models the problem is formulated as follows.

Let some initial graph G be given (N, V), in accordance to a set N power n which vertices put switching knots of a communication network, and to set V - network junction circuits.

It is necessary to define a set of ways M = { _si } from the given vertex s in other vertices i N, i _ s, i = 1... n, graph G for which the transient parameter Т does not exceed some specified value T ₀, i.e.

Т _ T ₀, " _si, i _ s, i = 1... n.

One of the most convenient, easily implemented on the computer methods of paths definition meeting this demand is constructing so-called «multilevel tree» paths from some defined vertex s to other graph vertex.

There is the initial graph and corresponding to it «multilevel tree» with parameter Т ₀ = 2 on fig. 2.10. Here Т is regarded as the quantity of transit vertices.

The algorithm of «multilevel tree» constructing includes the following steps.

Step 0. To form a subset of a zero tier including a unique element-top s into it. Using a contiguity matrix to write out columns numbers in a line with number S which elements are equal to a _sj = 1. Thus, there is the first tier vertices subset, formed by an vertex s.

Figure 2.10 – Illustration work of algorithm «multilevel tree» construction

Step 1. To form a subset of the following tier vertices. For this purpose:

a) the previous tier vertices are chosen in succession for each of which the line with number with the same name is chosen in a contiguity matrix;

b) columns numbers defined by nonzero elements are written out for every line;

c) in each of the formed subsets there expelled the apexes numbers (columns numbers) concerning which apexes subsets in the previous tiers were formed. All not deleted elements (columns numbers) form the following tier subsets.

Step 2. If the tier number is equal to (Т ₀+1) – it means the end. Otherwise - to pass to a step 1.