Method for finding the maximum flow. An example of finding the maximum flow using the Ford-Fulkerson method

Hamiltonian cycles

The graph is given in the form of a matrix, where the cells specify the cost of movement between points. The symbol ∞ is placed on the main diagonal to eliminate a meaningless path into itself.

Because If the resulting matrix contains a column without zero elements, then we will find the minimum element in it and subtract it from all the elements of this column.

	A	B	C	D
A	∞
B		∞
C			∞
D				∞

Let's sum up all the subtracted elements and get the lower bound of the cycle in= 2+2+3+2+1=10

1.2. Let us evaluate all zero elements of the matrix.

It is convenient to present the estimate of zeros in a table.

	A	B	C	D
A
B
C
D

θ=max γ=γ A C =2

1.3. Let's split the set of paths into two subsets: Q A.C.– paths containing arc (AC) and Q A.C.– paths that do not contain an arc (AC). For the second subset the lower bound will be: in / = in + θ =10+2=12.

To calculate the boundary for the first subset, we move to the matrix one order of magnitude lower, crossing out the A-row and C-column. In the new matrix to eliminate the reverse path (CA), we put the sign ∞ in the corresponding cell.

Let's calculate the boundary of the resulting matrix 2+0=2

and add it to the bottom border of the loop. This amount in // =10+2=12 and will be the boundary for the first subset.

1.4. Let's compare the boundaries of all hanging vertices and select the vertex with the smallest boundary. If there are two of these vertices, choose any of them. This is the top of Q A.C., whose lower limit =12.

Let's choose the maximum of the estimates θ=max γ=γ BD =3

in / =12+3=15.

1.6. We perform all subsequent points similarly to the previous ones.

Let's choose the maximum of the estimates θ=max γ=γ C B =∞

in / =in+ θ=∞

	A
D

All rows and columns of this matrix contain zeros. Therefore, the limit remains equal to 12.

TASK. Find the value of the maximum flow on the transport network.

FORMULATION OF THE PROBLEM.

Consider the transport problem on the network ( I,D,G) with given arc capacities c(i,j).

Let us select two fixed vertices: s- source and t– drain. Stream on the network s→t let's call the numerical function f, defined on a set of arcs and satisfying the following linear equations and inequalities:

0≤ f(i,j) ≤c(i,j) for any (i,j)

Required to maximize a variable x

Cut L in a network separating vertices s t called the set of arcs

Any way s→t contains at least one cut arc.

OPTIMALITY CRITERIA: on a real network, the value of an arbitrary flow does not exceed the throughput of the cut, and the value of the maximum flow is equal to the minimum throughput of the cut.

EXAMPLE 3.12.

M 9 K

M 8 K

EXAMPLE 3.13.

M 2 K

SOLUTION :

The capacity of the outgoing arc (T,B) exceeds the total capacity of the arcs entering the corresponding vertex. In order for the network to become real, we replace c(T,B)=5.

Let's find and calculate the value of the throughput capacities of all cuts. (K,V) – (T,V) cut with minimum throughput =6. Therefore, the maximum flow =6.

A network with several sources and sinks can be reduced to a network with one source and sink.

EXAMPLE. Let there be several sources S and sinks T (transport problem). Let's expand the network by adding two nodes s*, t* and all arcs (s*, S) , (T,t*). Let us define the capacity function by setting

METHOD OF PLACEMENT OF MARKS.

1. Initial flow f(i,j) = 0.
Let us assign labels to the vertices of this network that will have the form (i+, ε) or
(i - , ε). Let's mark the source (-, ∞), those . ε(s)= ∞.

2. For any marked vertex i select all unlabeled vertices j for which f(i,j) and add notes to them (i+, ε(j)), Where ε(j)=min[ε(i), f(i,j)]. Those vertices that will remain unmarked, but for which f(i,j)>0, attribute the note (i-, ε(j)).

We repeat this operation until the drain is marked. If the flow remains unlabeled, then the flow found is maximum, and the set of arcs connecting marked vertices with unmarked ones form a minimal cut.

3. Let the stock be labeled (j+, ε(t)), Then f(j,t) replace with f(j,t)+ε(t). If the stock is marked (j-, ε(t)), That f(j,t) replace with f(j,t)-ε(t). Let's go to the top j. If j has a mark (i+, ε(j)), then we replace f(i,j) on f(i,j)+ε(t), and if (i-, ε(j)), f(j,i) replace with f(j,i)-ε(t). Let's go to the top i. We repeat this operation until we reach the source s. The flow change stops, all marks are erased and go to step 2

EXAMPLE 3.14.

M 4 K

1 step A → (-, ∞) M → (A+,8) P → (A+,3) K → (P+,3) T → (P+,3) B → (T+,3) f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(A,M)=0 f(M,P)=0 f(M,K)=0 f(M,T)=0 f(K,T)=0 f( K,V)=0
Step 2 A → (-, ∞) M → (A+,8) P → (M+,1) K → (M+,4) T → (M+,2) f(K,B)=3 f(M,K)=3 f(A,M)=3 f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,T)=0 f(M,P)=0 f(K,T)=0
Step 3 A → (-, ∞) M → (A+,5) P → (M+,1) K → (M+,1) T → (M+,2) B → (T+,2) f(T,B)=5 f(M,T)=2 f(A,M)=5 f(K,B)=3 f(M,K)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,P)=0 f(K,T)=0
Step 4 A → (-, ∞) M → (A+,3) P → (M+,1) K → (M+,1) T → (P+,1) B → (T+,1) f(A,M)=6 f(T,B)=6 f(P,T)=4 f(M,P)=1 f(M,T)=2 f(K,B)=3 f(M,K)=3 f(A,P)=3 f(P,K)=0 f(K,T)=0
Step 5 A → (-, ∞) M → (A+,2) P → (M-,1) K → (M+,1) T → (K+,1) B → (T+,1) f(A,M)=7 f(M,K)=4 f(K,T)=1 f(T,B)=7 f(P,T)=4 f(M,P)=1 f( M,T)=2 f(K,B)=3 f(A,P)=3 f(P,K)=0
Step 6 A → (-, ∞) M → (A+,1) Flow is optimal f=10 Minimum cut: M→T-M→R-M→TO
TASK. Find the highest flow on the network

ALGORITHM

Let's denote the vertex s= x 0 . All others are x i.

Stage 1.

1. Choose any path all of whose arcs are not saturated.

2. We increase the amount of flow along this path by one until there is no saturated arc in it.

We continue the process of increasing the flow until the full flow is built, i.e. any path will contain at least one saturated arc.

Stage 2.

2. If х i is already a marked vertex, then we mark (+i) all unlabeled vertices to which unsaturated arcs go from х i, and with the index (–i) all unmarked vertices from which arcs with non-zero flow go to х i.

3. If as a result of this process a vertex is marked t, then between s And t there is a path all of whose vertices are marked with the numbers of the previous vertices. We increase the flow in all arcs of this path by one if, when moving from s To t the orientation of the arc coincides with the direction of movement, and is reduced by one if the arc has the opposite orientation. Let's move on to step 1.

4. When the top t it is impossible to mark the process is terminated and the resulting flow is the largest flow of the network.

NOTE. You can go to stage 2 without completing the first stage (see example 3.16).

EXAMPLE 3.15.

9

SOLUTION:

A complete flow has been found on a given transport network. Saturated arcs are highlighted

In this network, you can also mark the final vertex, and the result of the marking will be the same. By changing the flow, we get a network in which it is impossible to mark the final vertex, so the flow in it is the largest and equal to 10.

EXAMPLE 3.16.

8 2 1

An incomplete flow was found on a given transport network

Let's mark the network and increase the flow in it according to the algorithm. We get

In this network, you can also mark the final vertex, and the result of the marking will be the same. By changing the flow, we get a network in which it is impossible to mark the final vertex, so the flow in it is the largest and equal to 6.

Section IV. DYNAMIC PROGRAMMING.

Dynamic programming is used to find optimal multi-stage solutions. For example, long-term planning for equipment replacement; activity of the industry over a number of years. It uses the principle of optimality, according to which any new partial solution must be optimal relative to the achieved state.

It is better to solve one simple problem many times than to solve a difficult one once.

PROBLEM 1. About the most advantageous route between two points.

It is required to build a path connecting two points A and B, of which the second lies to the northeast of the first. For simplicity, let's say that laying out a path consists of a series of steps, and at each step we can move either due north or due east. Then any path is a stepped broken line, the segments of which are parallel to one of the coordinate axes. The costs of constructing each of these sections are known.

EXAMPLE 4.1. Find the minimum path from A to B.

The last step is to achieve T.V. Before the last step, we could be at points from where we could reach T.V. in one step. There are two such points (the system could be in one of two states). For each of them, there is only one option to reach t.V: for one - move east; for the other - to the north. Let's write costs 4 and 3 in each case.

4

Now let's optimize the penultimate step. After the previous step, we could end up in one of three points: C 1, C 2, C 3.

For point C 1, there is only one control (let’s mark it with an arrow) - move east, and the costs will be 2 (at this step) + 4 (at the next step) = 6. Similarly, for item C 3 the costs will be 2+3=5. For t.C 2 there are two controls: go east or north. In the first case, the costs will be 3+3=6, and in the second case – 1+4=5. This means that the conditional optimal control is to go north. Let's mark it with an arrow and enter the corresponding costs.

2 4

TASK 2. About loading the car (about the backpack).

There are N items. Known weight a i and value φi each item. Required to fill a backpack capable of holding ≤ weight R , such a set of items that would have the greatest value.

The process of loading a backpack can be divided into N steps. At each step we decide the question: to take this item or not to take it? At each step there are only 2 controls: control =1, if we take this item; and 0 – if we don’t take it.

The state of the system before the next step is characterized by the weight S, which still remains at our disposal until the end of full loading after the previous steps have been completed (some items have already been loaded), i.e. the amount of free space in the backpack.

ALGORITHM.

1. Let's start from the last step. Let's make various assumptions about the free space in the backpack: S=0.1,…R. Let's put the last item in the backpack if it has enough storage space.

2. At each previous step, for all possible states S, we consider 2 options: take or not take the object. Let us find the gain in each case as the sum of the gains at the current step and at the next already optimized step. We will enter the results into the auxiliary table.

3. At the first step, we consider only the only possible state S=R.

4. Let’s find a solution by “moving backwards”, i.e. Taking optimal control at the first step, we change the state of the system at the second step: S=R– x 1 a 1 and choose the optimal control x 2 for this state. Etc.

EXAMPLE 4.2.

Initial data

P1 P2 P3 P4
weight a i
costj i
Main table

S i=4 i=3 i=2 i=1
x 4 W 4 x 3 W 3 x 2 W 2 x 1 W 1

Auxiliary table.

state x A S- A j i (x) W i+1 (S- A) j i (x)+ W i+1 (S- A)
i=3 S=5
S=6
S=7
S=8
S=9
S=10
i=2 S=5
S=6
S=7
S=8
S=9
S=10
i=1 S=10
Answer: x 4 =0; x 3 =1; x 2 =0; x 1 =1; W=15

TASK 3. On the distribution of resources.

There are N enterprises P 1, P 2,… P N, each of which generates income φ k (x) if it is allocated a resource in the amount of x. It is required to distribute the resource available in quantity A between objects so that the total income is maximum.

Let x k be the amount of resource allocated to the kth enterprise. Then the problem under consideration is reduced to a conventional nonlinear programming problem.

Let us formulate the problem as a dynamic programming problem.

For the first step we will take the investment of funds in enterprise P 1, for the second - in P 2, etc. The managed system in this case is the funds that are distributed. The state of the system before each step is characterized by one parameter - the available stock of funds not yet invested. In this problem, the step controls are the funds allocated to enterprises. It is required to find the optimal control (x 1, x 2,...x N), at which the total income is maximum:
1,1 0,5
S=3 0,1 0,5 1,1 1,5
S=4 0,1 0,5 2,1 1,5
S=5 0,1 0,5 2,5 3,1 2,5 2,5
i=1 S=5 0,5 1,5 3,1 1,1 3,1 3,5 2,1 2,6
Answer: x 1 =1; x 3 =0; x 3 =4; W=3.5

GENERALIZED ALGORITHM

1. Describe the system. That is, find out what parameters characterize the state of the controlled system before each step. It is important to be able to correctly and “modestly” set the task, without overburdening it with unnecessary details, simplifying the description of the controlled system as much as possible.

2. Divide the operation into steps (stages). All reasonable restrictions imposed on management must be taken into account here. The step must be small enough so that the step control optimization procedure is fairly simple; and the step, at the same time, should not be too small so as not to make unnecessary calculations that complicate the procedure for finding the optimal solution, but do not lead to a significant change in the optimum of the objective function.

3. Find out the set of step controls x i for each step and the restrictions imposed on them.

4. Determine what gain the control x i brings at the i-step, if before that the system was in state S, i.e. write down the payoff functions:

w i =f i (S, x i)

5. Determine how the state of the system changes under the influence of control x i at the first step, i.e. write state change functions.

S / =φ i (S, x i)

6. Write down the main recurrent dynamic programming equation, expressing the conditional optimal gain through an already known function

W i (S)= max(f i (S, x i)+W i+1 (φ i (S, x i)))

7. Carry out conditional optimization of the last step, making various assumptions about how the penultimate step ended, and for each of these assumptions find the conditional (selected based on the condition that the step ended with something) optimal control at the last step.

W m (S)= max(f m (S, x m))

8. Perform conditional optimization, starting from the penultimate step and ending with the first step (backing back).

9. Carry out unconditional control optimization, “reading” the corresponding recommendations at each step: take the found optimal control in the first step and change the state of the system, find the optimal control for the found state in the second step, etc. until the last step.

PRINCIPLE OF OPTIMALITY. Whatever the state of the system before the next step, it is necessary to choose control at this step so that the gain at this step plus the optimal gain at all subsequent steps is maximum.

The principle of dynamic programming does not imply that each step is optimized separately, independently of the others. What is the point of choosing a control whose effectiveness is maximum at one specific step, if this step will deprive us of the opportunity to win well at subsequent steps?

In practice, there are cases when an operation has to be planned for an indefinitely long period of time. The model for such a case is an infinite-step controlled process, where all steps are equal. Here the winning function and the state change function do not depend on the step number.

Section V. SIMULATION MODELING
Extreme case: if the matrix is all the same color - the answer is 0.
Let's add fictitious source and drain. From the source to all white vertices we draw edges with a weight of B (the cost of repainting them black). From the black vertices to the drain we draw edges with a weight of W (the cost of repainting it white). And between all neighboring vertices (whether they are the same or different colors) we place an edge with a weight of G (gray line). The value of the maximum flow will be the answer to the problem.
Source: All-Ukrainian School Olympiad in Informatics, 2007, Day 1
Vertex constraint problem. Suppose we need to find the value of the maximum flow and a limit is imposed on the vertices as to how much they can pass.
Solution
All we need is to divide each vertex into two, and between them put an edge with a weight equal to the capacity limitation of this vertex

Minimal incision. Dan Count. How many vertices must be removed so that there is no path from A to B?
Solution
In the classic minimum cut problem, edges need to be removed. No problem! Let's split the vertices into 2, and put an edge between them with a weight of 1. Then the answer to the problem is finding the minimum cut in the graph (which is the maximum flow).
Source: Kharkov winter school on programming, 2009, Day 3

Writer of poetry. There is a deterministic finite automaton with one initial state A and one final state B. Each transition is specified by a triple of numbers (i, j, k), a transition from state i to state j along edge k.
After moving through the automaton from i to j along edge k, all transitions from i along edge k, as well as all transitions to j along edge k, are erased. You need to print the number of paths from A to B along such an automaton.
Solution
The problem boils down to finding the maximum number of paths without more than one edge of the same color coming from one vertex. Let us reduce the problem to finding the maximum flow. For each vertex, we will create k+1 vertices in the rebuilt network. The first vertex will be the input, the remaining vertices will represent the colors. From the input vertex we draw along an edge with capacity 1 to each of the k vertices corresponding to the color. From the vertices corresponding to color i we draw all edges of color i to the inputs of the ends of the edges. Having found the maximum flow in such a network, we obtain the maximum number of paths that satisfy the required property.

Collecting coins. Eat n collectors and m types of coins. To join the club, you must have at least one coin of each type. You (you are number 1) can exchange existing coins with collectors. Any collector will exchange a coin for his coin a to your coin b if he has more one coin type a and there is not a single coin like b. You, in turn, can break this rule. You need to collect as many types of coins as possible according to a known situation from all collectors.
Solution
Let's build a network. Let's create one vertex for each type of coin. These tops will correspond to your coins. We need to collect as many unique coins as possible, so we draw capacity edge 1 to the sink from each such vertex. At the vertices corresponding to the coins that you initially have, we will draw an edge whose capacity is equal to the number of such coins you have.
For each club member (except 1, that is, you) we will create one vertex. This vertex can accept at most one coin that it does not have and give
at most k-1 coins, of which he has k (k > 1). Naturally, the club member gives one coin in exchange for one received.
Thus, to each such vertex you need to draw a capacity edge of 1 of the vertices corresponding to coins that this club member does not have. And from these vertices you need to draw edges with capacity k i - 1 to vertex i, corresponding to coins of which a club member has more than one.
The constructed network reflects the exchange processes in the club. The maximum flow in such a network will be equal to the maximum number of coins that can be collected by you.
Source: Kharkov winter school on programming, 2009, Day 4

Circulation. The reactor cooling system is a set of pipes connecting the units. Liquid flows through pipes, and for each pipe there is a strictly defined direction in which it should flow through it. The cooling system components are numbered from 1 to N. The cooling system must be designed in such a way that for each component per unit of time, the amount of liquid flowing into the component is equal to the amount of liquid flowing out of the component. Each pipe has a capacity c ij . In addition, to ensure sufficient cooling, it is required that at least l ij units of liquid flow through the pipe per unit of time. That is, for a pipe leading from the i-th node to the j-th node, l ij ≤ f ij ≤ c ij must be satisfied.
A description of the cooling system is given. It is necessary to find out how the liquid can be passed through the pipes so that all the specified conditions are met.
Solution
This is a problem of finding circulation in a network with given lower restrictions on the edges. If a flow must pass along the edge (u, v) in the segment , then the rebuilt network will have three edges (from, to, weight): (u, v, r - l), (S, v, l), (u, T, l). S, T - additionally introduced drain and source, respectively. In fact, we pass the required minimum flow along the edge, and then balance it so as to obtain circulation.

Solve the problem of finding the maximum flow in a transport network using the Ford-Fulkerson algorithm, and construct a network section S.
Initial data:
Given a network S(X,U)
- source of the network; - network drain, where ∈X; ∈X.
The arc capacity values are specified in the direction of arc orientation: from index i to index j.

r = 39; r = 44; r = 33; r = 53; r = 10;
r = 18; r = 95; r = 16; r = 23; r = 61;
r = 81; r = 71; r = 25; r = 15; r = 20

1. Set a zero flow on the network (on all arcs the flow value is 0). Flow zero is the initial allowed flow on the network. The flow value on each arc will be indicated outside the arc capacity brackets.). The flow value equal to “0” is not specified.
2. Select (arbitrarily) a path on the network leading from vertex x0 to vertex x7:
X0-X1-X4-X6-X7
3. Find and increase the flow by this amount. Edge X1-X4 is marked as considered.

4. Choose another path, for example: X0-X2-X5-X7, find and increase the flow by this amount. Edge X0-X2 is marked as considered.

5. Choose another path, for example: X0-X3-X2-X5-X7, find and increase the flow by this amount. Edge X3-X2 is marked as considered.

6. There are no more paths from X0 to X7, let’s sum up the increase in flow: 25+10+20=55.
Conclusion: the maximum flow is 55.

2) Construct a section of the network S.
The “vertex marking” procedure.
Initial state: all vertices are unlabeled.
The vertex X0 is assigned a label. All vertices for which the arc is not saturated are assigned marks (red circles)

We define minimal cut arcs: these are arcs whose beginnings are at marked vertices and whose ends are at unlabeled vertices.
These are the arcs:
Thus, the minimum cut of this network
Calculation of the maximum flow value

When planning the rational distribution of products in the distribution network, it is necessary to coordinate the channel capacity with the needs of customers and with the capacity of the production plant. This class of problems is solved by finding the maximum flow.

Let's consider a distribution network (Fig. 4.21), in which points 0 (entrance, for example, a manufacturer's warehouse of finished products) and P (exit, distribution centers, warehouses of wholesale and retail organizations, consumer) and each arc (segment) connecting points i And j, the number dij > 0 is associated, called throughput arcs. The throughput value characterizes the maximum permissible amount of material flow that can pass along the corresponding arc per unit of time.

Rice. 4.21.

The quantity of products passing along an arc from i before j , we will call it a flow along the arc ( i ,j ) and denoted by . It's obvious that

If we take into account that the entire material flow entering the intermediate point of the network must completely exit it, we obtain

From the natural requirement of equality of flows at the input and output we have

We will call the value of Z the value of the flow in the network and pose the problem of maximizing Z subject to the above conditions.

Finding the maximum flow comes down to finding the throughput of the minimum cut.

Let's consider a universal search algorithm in matrix form.

The initial stage of the algorithm consists of constructing a matrix D 0, into which the throughput values are entered (for an unoriented arc we take the symmetrical values of the matrix elements).

The main steps of the algorithm are to find a certain path and correct the flow along this path.

When finding a path, we use a marking process. We mark with the symbol * the zero row and column of the matrix (network input). In the 0th line we look for , mark the corresponding columns with indices

and move the column labels to the rows. Then we take the ith marked row, look for an unmarked column in it with , to which we match index labels

We transfer the column labels to the rows, and continue this process until the nth column is marked.

Then, using the indices, we find out the path that led to the η-th vertex using the indices, and reduce the capacity of the arcs of the path (matrix elements) by V n and increase the symmetrical elements by the same amount.

This procedure continues until the marking n -tops will not become impossible.

The maximum flux can be found by subtracting from the original matrix D 0, obtained after the above correction of the capacity matrix:

Example 4.4

Production is located in Moscow. To distribute products, the company attracts intermediaries who work with the company through distribution centers at various levels. In the European part of Russia there is a wholesale enterprise 1, serviced by a central distribution center. Wholesale enterprise 2 operates in the near abroad (Ukraine, Belarus) and is serviced by a regional distribution center. The company has its own clients in the local market (Moscow and Moscow region) - retailers who receive products from the city distribution center. Regional and city distribution centers are restocked from the central distribution center.

Let us highlight a fragment of the distribution network:

warehouse of finished products of a manufacturing enterprise;

central distribution center;

regional distribution center;

city distribution center;

two wholesale enterprises;

company-owned retail outlet;

consumers.

Rice. 4.22.

Let's designate each link of the distribution network with a number, and put the capacity above the arcs. The throughput capacity, depending on the type of link, can be expressed in terms of the volume of production capacity, the planned need (demand) of consumers and market capacity.

The product distribution network graph is shown in Fig. 4.23. Let's build a matrix D 0, into which we enter the values of the throughput capacities of the distribution network links (Fig. 4.24).

Rice. 4.23.

Rice. 4.24.

From the zero row we mark the vertices (rows-columns) 1, 2 and 3 with indices μ = 0 and V, equal to 30.10 and 10.

From marked line 1, mark vertices 4 and 5 with indices μ = 1 and V4 = min (30,15) = 15, V5 = min (30,10) = 10.

From line 3 we mark vertex 6 and, finally, from line 4 – vertex 7 (Fig. 4.25).

Rice. 4.25.

By going back along μ we find the path: to vertex 7 from 4, to vertex 4 from 1, to vertex 1 from 0; adjusting elements D 0 per flow value V7 = 15.

The next step gives a path with flow 5 (Fig. 4.26).

Rice. 4.26.

The next step gives the result shown in Fig. 4.27.

Rice. 4.27.

No further marking is possible. From here we obtain the maximum flow matrix (Fig. 4.28).

Rice. 4.28.

As a result of applying the algorithm for finding the maximum flow in the network, the results presented in Fig. 4.29. The pairs of numbers in brackets shown on the arcs of the graph indicate the maximum throughput of the arc and the recommended volume of goods supplied to the network.

Algorithm for calculating maximum flow in networks
STEP 1. Initial assignments. Current value A t The maximum flow in the network is assigned the value 0. STEP 2. Selecting independent routes in the network and determining the flows in them. From the entire set of possible routes in the network from source to sink, we select independent routes M 1 , … , M k, having no common vertices except the initial one (source v and) and final (drain v with). For each selected route M i(1£ i£ k) determine the maximum flow A(M i).STEP 3. Correction of the current value of the maximum flow in the network. We add those found on STEP 2 values of maximum flows in independent routes M 1 , … , M k to the current total maximum network flow: A t:= A t + A(M 1)+ A(M 2)+…+ A(M k)STEP 4. Network correction. Found on STEP 2 maximum flows A(M 1), … , A(M k) subtracted from the capacity of the corresponding network arcs. Arcs with zero residual capacity are removed. STEP 5. Checking the completion of the algorithm. If after correction there are no routes from the source left in the network v and to stock v with, then the required maximum flow in the network is equal to the found current A:= A t, the algorithm terminates because all network capacity has been exhausted. If in the adjusted network there are routes from the source v and to stock v with, then go to STEP 2 and continuation of the algorithm execution . Example 2. Find the maximum flow in the network in Fig. 1.15 using this algorithm. Solution.STEP 1. Initial assignments. A t: = 0.
I iteration. STEP 2. Selecting independent routes in the network and determining the flows in them. As M 1 take route( v and =V 1 , V 2 , V 5 , v with =V 7), considered in example 1. For him A(M 1) = 10.

It is also easy to isolate independent M 1 route M 2 = (v and =V 1 , V 3 , V 6 , v with =V 7). Let's calculate the maximum throughput for it and adjust the throughput of the arcs: A(M 2)= min{d 13 , d 36 , d 67 } = min{45, 40, 30} = 30. d 13¢ =d 13 - 30 = 15, d 36¢ =d 36 - 30 = 10, d 67¢ =d 67 - 30 = 0.
STEP 3. Correction of the current value of the maximum flow in the network. A t:= A t + A(M 1)+ A(M 2) = 0 + 10+ 30 = 40.STEP 4. Network correction. Found on STEP 2 maximum flows A(M 1), A(M 2) in routes M 1 , M 2 is subtracted from the capacity of their arcs. Arcs with zero residual capacity are removed. The result is given in Fig. 1.16 a. a) b) Fig. 1.16. The result of network correction after iterations I And IISTEP 5. Checking the completion of the algorithm. In the adjusted network (Fig. 1.16 a) there are routes from the source v and to stock v with, For example M 3 = (v and =V 1 , V 4 , V 2 , V 5 , v with =V 7). Continuing the execution of the algorithm .
II iteration. STEP 2. As the only independent route we take M 3 = (v and =V 1 , V 4 , V 2 , V 5 , v with =V 7). For him:

A(M 3)= min{d 14 , d 42 , d 25 , d 57 } = min{15, 10, 10, 15} = 10.

d 14¢ =d 14 - 10 = 5, d 42¢ =d 42 - 10 = 0, d 25¢ =d 25 - 10 = 0, d 57¢ =d 57 - 10 = 5.
STEP 3. A t:= A t + A(M 3) = 40 + 10= 50.
STEP 4. Network correction. Maximum flow A(M 3) subtract from the arcs of the route M 13 . The result is given in Fig. 1.16 b.
STEP 5. There are no source-to-sink routes left in the adjusted network. A:= A t:= 50, completion of the algorithm. Answer: the maximum flow in the network in Fig. 1.15 is 50.
If several sources are specified in the network, it is completed by introducing a new common source, which is connected to the original sources by arcs having unlimited capacity. Then the problem is solved using the usual algorithm. The required flows through the original sources will be flows along the newly added arcs entering them from a new common source. Do the same if there are several drains in the network.

Network planning

Any task of designing or constructing a fairly complex object ( project) can be broken down into a number of smaller component steps. The timing of the entire project depends on the correct choice of the sequence of these steps.

The entire range of actions to implement the project is presented as a set events And works. Events are called individual stages of a project. Work is the process of completing it. The entire complex of events and work necessary to complete the project can be represented in the form of a two-pole network G =({v and, v z} , V, X), wherein:

and all events marked by a set of vertices V, highlighted among them initial event v and(start of work) and final event v z(completion of the entire project), the internal vertices of the network define intermediate events- stages that need to be completed during the project implementation process,

b) everything work are indicated by arcs connecting pairs of events - vertices.

The graphical representation of this network is called network diagram. To indicate the sequence of actions, also enter into the network diagram fictitious works, which are not associated with performing any actions. The corresponding works are indicated by dashed arcs.

As an example, consider the organization of some production. The project requires the following work:

I) marketing research, II) pre-project research on equipment, III) organizing a sales network, IV) conducting an advertising campaign, V) development of technical specifications for production equipment, VI) development of technical documentation for production premises and communications, VII) purchase of standard equipment, VIII) design and manufacture of non-standard equipment, IX) construction of production facilities and installation of communications, X) installation of standard equipment, XI) installation of non-standard equipment, XII) commissioning.

We will denote these works in the network diagram by arcs with corresponding numbers.

The events in this project will be the following:

1) start of work (initial event), 2) completion of marketing research, 3) completion of pre-project research, 4) organization of a sales network, 5) organization of an advertising campaign, 6) preparation of technical specifications for production equipment, 7) completion of the development of technical documentation for production premises and communications, 8) completion of the purchase of standard equipment, 9) completion of the design and manufacture of non-standard equipment, 10) completion of the construction of production facilities and installation of communications, 11) completion of installation of equipment and commissioning works,

12) completion of the project (final event).

We associate vertices with corresponding numbers to events. The network schedule for the project is shown in Fig. 1.17:

Fig.1.17. Project implementation network schedule