1、Transport networks（傳輸網(wǎng)）,2,2020/9/3,College of Computer Science remember that the source is not labeled. or (ii) the sink has been labeled.,18,2020/9/3,College of Computer Science remember that the source is not labeled.,19,2020/9/3,College of Computer Science & Technology, BUPT,Step 5,In case (ii) t

2、he sink, node n, has been labeled with En, m where En is the amount of extra flow that can be made to reach the sink through a path . (ii) the sink has been labeled.,20,2020/9/3,College of Computer Science & Technology, BUPT,Step 5,We examine in reverse order. If edge (i, j) N, then we increase the

3、flow in (i, j) by En and decrease the excess capacity eij by the same amount. Simultaneously, we increase the excess capacity of the (virtual) edge (j, i) by En since there is that much more flow in (i, j) to reverse. If, on the other hand, (i, j) N, we decrease the flow in (j, i) by En and increase

4、 its excess capacity by En. We simultaneously decrease the excess capacity in (i, j) by the same amount, since there is less flow in (i, j) to reverse. We now have a new flow that is En units greater than before and we return to Step 1.,Example 4,21,2020/9/3,College of Computer Science & Technology,

5、 BUPT,Example 3,The initial flow in all edges is zero,22,2020/9/3,College of Computer Science & Technology, BUPT,Example 3: step 1,Starting at the source, we can reach nodes 2 and 4 by edges having excess capacity, so N1= 2, 4,4,1,5,1,23,2020/9/3,College of Computer Science & Technology, BUPT,Exampl

6、e 3: step 2,From node 2 we can reach nodes 5 and 3 Label node 5 and node 3 We cannot travel from node 4 to any unlabeled node by one edge. Thus, N2 = 3, 5,4,1,5,1,2,2,3,2,24,2020/9/3,College of Computer Science & Technology, BUPT,Example 3: step 3,We repeat Step 2 using N2. We can reach the sink fro

7、m node 3 and 3 units through edge (3, 6). Thus the sink is labeled with 3, 3,4,1,5,1,2,2,3,2,3,3,25,2020/9/3,College of Computer Science & Technology, BUPT,Example 3 : step 5,the path is l, 2, 3, 6 subtract 3 from the excess capacity of each edge, indicating an increased flow through that edge, and

8、adding an equal amount to the excess capacities of the (virtual) edges.,26,2020/9/3,College of Computer Science & Technology, BUPT,Example 3,We now return to Step l with the situation shown as,27,2020/9/3,College of Computer Science & Technology, BUPT,Steps 1,2,3,4,1,2,1,2,2,2,5,28,2020/9/3,College

9、of Computer Science & Technology, BUPT,Step 5,Work back along path 1,2,5,6, subtracting 2 from the excess capacities of these edges And return to Step 1.,29,2020/9/3,College of Computer Science & Technology, BUPT,Step 1,2,3,4,1,3,4,2,5,2,5,30,2020/9/3,College of Computer Science & Technology, BUPT,S

10、tep 5,Work back along the path 1,4,5,6, adjusting excess capacities. Return to Step 1.,31,2020/9/3,College of Computer Science & Technology, BUPT,Go further?,Step 1,2,3,2,1,1,5,1,4,32,2020/9/3,College of Computer Science & Technology, BUPT,step 4,Terminated with the final overall flow 7. Q.E.D.,Go b

11、ack,33,2020/9/3,College of Computer Science & Technology, BUPT,Example 4,34,2020/9/3,College of Computer Science & Technology, BUPT,Step 1,2,3,8,1,5,1,4,2,3,2,3,3,35,2020/9/3,College of Computer Science & Technology, BUPT,Step 5,36,2020/9/3,College of Computer Science & Technology, BUPT,Step 1,2,3,8

12、,1,2,1,2,2,3,3,6,5,37,2020/9/3,College of Computer Science & Technology, BUPT,Step 5,38,2020/9/3,College of Computer Science & Technology, BUPT,Step 1,2,3,5,1,3,5,2,1,2,4,2,2,39,2020/9/3,College of Computer Science & Technology, BUPT,Step 5,40,2020/9/3,College of Computer Science & Technology, BUPT,

13、Step 1,2,3,5,1,3,5,3,3,2,2,2,4,41,2020/9/3,College of Computer Science & Technology, BUPT,Step 5,42,2020/9/3,College of Computer Science & Technology, BUPT,Go further?,Step 1,2,3,3,1,1,5,1,3,43,2020/9/3,College of Computer Science & Technology, BUPT,Step 4,44,2020/9/3,College of Computer Science & T

14、echnology, BUPT,Cut（割集）,A cut in a network N is a set K of edges having the property that every path from the source to the sink contains at least one edge from K.,45,2020/9/3,College of Computer Science & Technology, BUPT,Capacity of a cut K,The capacity of a cut K, c(K), is the sum of the capacities of all edges in K. If F is any flow and K is any cut, then value(F) c(K).,46,2020/9/3,College of Computer Science & Technology, BUPT,Th