Problems about flow

The problems about streams in networks draw special attention thanks to specificity of its structure. Let’s introduce some definitions.

D e f i n i t i o n 1. The number х_ijis called a stream on an arch (to a rib

(i, j), if х_ij_ b_ij, where b_ij - bandwidth of this arch.

D e f i n i t i o n 2. Stream P_st from some vertex s named a source to some vertex t named a flow in a network is a set of non-negative numbers х_ij (arches streams) if these numbers satisfy the following restrictions:

(1)

P_st³ 0;0 £ х_ij £ b_ij forall (i, j) V. (2)

Here the first sum is taken on the arches leading to the vertex j, and the second sum – on the arches leading from j.

Restriction (1) characterizes that fact that to each apex (except a source and a flow) comes so much stream, as from it gets out of it and is called a condition of conservation of a stream. Restriction (2) means that the stream on an arch is restricted by its bandwidth.

D e f i n i t i o n 3. Cross-section (cut) of a network is called irredundant set of arches (ribs) while excluding it from a network its connectivity is broken.

D e f i n i t i o n 4. Bandwidth of cross-section is called the sum of arches bandwidth oriented in a direction from a source to a flow or ribs making this cross-section.

D e f i n i t i o n 5. The cross-section dividing s and t and possessing the least bandwidth is called the minimum cross-section.

The minimum cross-section dividing a source s and a flow t is analogue of «bottle neck» in any network and, hence, the maximum stream magnitude cannot exceed its bandwidth. There is a theorem proved by Ford and Falkerson conferming that maximum stream magnitude is always equal to the minimum bandwidth among all cross-sections dividing s and t. The theorem of the maximum stream and the minimum cross-section is basic in the theory of streams in networks.

D e f i n i t i o n 6. The network having one source and one flow is called double-pole.

D e f i n i t i o n 7. The network where each pair of vertices can considered as a source and a flow is called multipolar.

D e f i n i t i o n 8. If there are some sources and some flows in a network and a stream can go from any source to any flow such stream is called one-component (for example networks of gas pipelines, oil pipelines, energy line etc.).

D e f i n i t i o n 9. If in networks with several sources and flows the stream must go from some selected sources to some fixed flows such stream is called multicomponent (for example, networks of the informational communication, mail conveyances post, etc.).

At any moving of some objects from one point to another there appear streams and if they are regarded taking into account restrictions on moving there is a natural task about finding the maximum magnitude of a stream which can exist in the conditions of the defined restrictions.

For an estimation of connecting network bandwidth it is enough to define the maximum stream magnitude that can pass it and besides calculation of its arc components finding, the transfer paths can appear to be not necessarily at all. According to the theorem of the maximum stream and the minimum cut,the specified problem can be shown to definition of minimum cross-section bandwidth. Most simple way of a finding such cross-section for a double-pole network is looking through all possible cross-sections dividing a set of vertices N of a network into two not correlated set: N₁,including a source and N₂,including a flow and selection among them cross-section which possesses the minimum bandwidth. Unique difficulty which appears here lies in definition of cross-sections set. The algorithm allowing to,overcome the defined difficulty and possessing high efficiency from the point of view of implementation on the computer is given below. The principal idea accepted for its basis is essentially as follows.

Vertices of subsets N₁ and N₂ where the next cross-section divides a network are appropriated to some marks, for example,: 0. N₁; 1. N₂.

Let the source s belong to N₁, and the flow t belong to N ₂. So, the vertex s will be marked with zero and t – with one. It is necessary to distribute marks between the others (n - 2) vertices for each possible cross-section of a network.

For this purpose it is necessary to be set by a rule generating various combinations of zeroes and ones which can be used to sort remained (n - 2) vertices in two subsets N ₁ and N _2. On the basis of such a rule we can use a principle of a number representation of a natural sequence in a binary aspect. Capacity of binary number in this case is defined by value (n - 2) and, hence, the maximum quantity of binary numbers will make 2 ^(n-2). The same magnitude corresponds to the greatest possible quantity of the cross-sections dividing a network into two subsets N ₁ and N ₂ of not correlated vertices. Every position of binary number should be put to the vertex number (the order makes no difference) in conformity. We will remind that vertices s and t do not participate here as they have already obtained marks and according to them are distributed in subsets: s N ₁, t N ₂.

The algorithm is formulated as follows.

Step 0. Let’s appropriate to a source (to an apex s)a mark «0», and to a flow (to an apex t) a mark «1». Let’s consider that the value of the counter of cross-sections equals 0.

Step 1. Let’s form binary representation of number C and sort vertices according to marks. Let’s define bandwidth of cross-section for the obtained alternative of vertices distribution as the sum of bandwidth of the arches (ribs) making considered cross-section.

Step 2. Let’s increase value of a variable C to one. If С =2 ^(n-2), let’s pass to a step 3, otherwise – to a step 1.

Step 3. Among the obtained values { M_i (N ₁, N ₂)} let’s choose the least one.

Let's consider an instance illustrating the algorithm operation.

Let it be required to size up bandwidth between a source s and a flow t in a non-directional network, the model and matrix of ribs bandwidth of which are shown on figure 2.11.

Figure 2.11

Let's assume s =1 and it is marked as «0», t =2 and it is marked as «1».

Combination of vertices marks for all possible cross-sections and magnitude of their bandwidth are put into the table 2.1.

Table 2.1

№	Binary combinations	М i (N 1 N 2)	So, for example, zero
Cross-sections	Apexes numbers		by order cross-section will be
						characterised in
						accordance with symbolics,
						given in table 2.1.
						by the following apexes division
						into subsets:
						N1 = (1,3,4,5,6); N2 = (2). ribs:
						this cross-section is made
						(1,2), (4,2), (5,2).
						The total bandwidth
						of these ribs is equal to 16.
						Next cross-section is characterized
						by division
						N1 = (1,3,4,5); N2 = (2,6)
						It includes the ribs: (1,2), (1,6),
						(4,2), (5,2), (5,6) they also define
						cross-section bandwidth
						accordingly equal 21.

As we see from the table 2.1 the least magnitude of the cross-section bandwidth refers to cross-section with number 0. It also defines bandwidth of the set network.

Remarks. It should be noted that the way of obtaining the set of the ribs included into some cross-section generates the ribs which can be absent in the physical count is given above. These ribs can be either expelled from consideration, or can be considered with zero bandwidth.