北京邮电大学计算机学院离散数学 第十章补充传输+网络流

1、Yang JCollege of Computer Science & TechnologyBeijing University of Posts & TelecommunicationsTransport networks（传输网） 22021-10-30College of Computer Science & Technology, BUPTContentnApplication of digraphnConceptnCapacity (容量)nTransport network (传输网)nFlow (流量)nVirtual flow (虚流量)nMaximal

2、 flow (最大流量)nLabeling algorithm(标记算法)32021-10-30College of Computer Science & Technology, BUPTDirected graph (Digraph)nAn important use of labeled digraphs is to model what are commonly called transport networks.nThe label on an edge represents the maximum flow that can be passed through that ed

3、ge and is called the capacity（容量） of the edge. Many situations can be modeled in this way.42021-10-30College of Computer Science & Technology, BUPTExamplenFigure below might as easily represent an oil pipeline, a highway system, a communications network, or an electric power grid. 52021-10-30Col

4、lege of Computer Science & Technology, BUPTExamplenThe vertices of a network are usually called nodes and may denote pumping stations, shipping depots, relay stations, or highway interchanges.62021-10-30College of Computer Science & Technology, BUPTTransport networknMore formally, a transpor

5、t network, or a network, is a connected digraph N with the following properties:nThere is a unique node, the source（源端）, that has in-degree 0. We generally label the source node l.nThere is a unique node, the sink（宿端）, that has out-degree 0. If N has n nodes, we generally label the sink as node n.nT

6、he graph N is labeled. The label, Cij, on edge (i, j) is a nonnegative number called the capacity of the edge.72021-10-30College of Computer Science & Technology, BUPTFlowsnMathematically, a flow（流量） in a network N is a function that assigns to each edge (i, j) of N a nonnegative number Fij that

7、 does not exceed Cij.nConservation of flow（流量守恒）nValue of the flow82021-10-30College of Computer Science & Technology, BUPTFlowsnWe can represent a flow F by labeling each edge (i, j) with the pair (Cij, Fij)nExample 1nHere value(F) = 592021-10-30College of Computer Science & Technology, BUP

8、T Maximum Flows（最大流量）nFor any network an important problem is to determine the maximum value of a flow through the network and to describe a flow that has the maximum value. nFor obvious reasons this is commonly referred to the maximum flow problem.102021-10-30College of Computer Science & Techn

9、ology, BUPTExample 2nEven for a small network, we need a systematic procedure for solving the maximum flow problem.112021-10-30College of Computer Science & Technology, BUPTVirtual Flow122021-10-30College of Computer Science & Technology, BUPTnLet N be a network and let G be the symmetric cl

10、osure of N.nChoose a path in G and let an edge (i,j) in this path.nIf (i,j)N and eij=Cij-Fij0,then we say this edge has positive excess capacity（剩余容量）.n If (i,j) is not an edge of N then we are traveling this edge in the wrong direction. In this case eij=Fji if Fji 0. Increasing flow through edge(i,

11、j) will have the effect of reducing Fji. 132021-10-30College of Computer Science & Technology, BUPTA Maximum Flow AlgorithmnThe algorithm we present is due to Ford and Fulkerson and is often called the labeling algorithm（标记算法）. nThe labeling referred to is an additional labeling of nodes.nWe hav

12、e used integer capacities for simplicity, but Ford and Fulkerson show that this algorithm will stop in a finite number of steps if the capacities are rational numbers.142021-10-30College of Computer Science & Technology, BUPTLABELING ALGORITHMnLet N be a network with n nodes and G be the symmetr

13、ic closure of N. All edges and paths used are in G.nBegin with all flows set to 0. nAs we proceed, it will be convenient to track the excess capacities in the edges and how they change rather than tracking the increasing flows. nWhen the algorithm terminates, it is easy to find the maximum flow from

14、 the final excess capacities. Example 3152021-10-30College of Computer Science & Technology, BUPTStep 1nLet N1 be the set of all nodes connected to the source by an edge with positive excess capacity. nLabel each j in N1 with Ej, l, where Ej is the excess capacity e1j of edge (l, j). nThe l in t

15、he label indicates that j is connected to the source, node l. 162021-10-30College of Computer Science & Technology, BUPTStep 2nLet node j in N1 be the node with smallest node number and let N2(j) be the set of all unlabeled nodes, other than the source, that are joined to node j and have positiv

16、e excess capacity.nSuppose that node k is in N2(j) and (j, k) is the edge with positive excess capacity. Label node k with Ek, j, where Ek is the minimum of Ej and the excess capacity ejk of edge (j, k).nWhen all the nodes in N2(j) are labeled in this way, repeat this process for the other nodes in

17、N1. Let172021-10-30College of Computer Science & Technology, BUPTStep 3nRepeat Step 2, labeling all previously unlabeled nodes N3 that can be reached from a node in N2 by an edge having positive excess capacity. nContinue this process forming sets N4, N5. . . . until after a finite number of ste

18、ps eithern(i) the sink has not been labeled and no other nodes can be labeled. It can happen that no nodes have been labeled; remember that the source is not labeled. orn(ii) the sink has been labeled.182021-10-30College of Computer Science & Technology, BUPTStep 4nIn case (i), the algorithm ter

19、minates and the total flow then is a maximum flow. n(i) the sink has not been labeled and no other nodes can be labeled. It can happen that no nodes have been labeled; remember that the source is not labeled.192021-10-30College of Computer Science & Technology, BUPTStep 5nIn case (ii) the sink,

20、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 . n(ii) the sink has been labeled.202021-10-30College of Computer Science & Technology, BUPTStep 5nWe examine in reverse order. nIf edge (i, j) N, then we increase the flow

21、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.nIf, on the other hand, (i, j) N, we decrease the flow in (j, i) by En and increase its

22、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. nWe now have a new flow that is En units greater than before and we return to Step 1. Example 4212021-10-30College of Computer Science & Technology,

23、BUPTExample 3nThe initial flow in all edges is zeroe56 = 4e65 = 0e36 = 3e63 = 0412356e14 = 4e41 = 0e12 = 5e21 = 0e24 = 2e42 = 0e25 = 2e52 = 0e45 = 3 e54 = 0e23 = 3 e32 = 0222021-10-30College of Computer Science & Technology, BUPTExample 3: step 1nStarting at the source, we can reach nodes 2 and

24、4 by edges having excess capacity, so N1= 2, 4e56 = 4e65 = 0e36 = 3e63 = 0412356e14 = 4e41 = 0e12 = 5e21 = 0e24 = 2e42 = 0e25 = 2e52 = 0e45 = 3 e54 = 0e23 = 3 e32 = 04,15,1232021-10-30College of Computer Science & Technology, BUPTExample 3: step 2nFrom node 2 we can reach nodes 5 and 3nLabel nod

25、e 5 and node 3nWe cannot travel from node 4 to any unlabeled node by one edge. Thus, N2 = 3, 5e56 = 4e65 = 0e36 = 3e63 = 0412356e14 = 4e41 = 0e12 = 5e21 = 0e24 = 2e42 = 0e25 = 2e52 = 0e45 = 3 e54 = 0e23 = 3 e32 = 04,15,12,23,2242021-10-30College of Computer Science & Technology, BUPTExample 3: s

26、tep 3nWe repeat Step 2 using N2. We can reach the sink from node 3 and 3 units through edge (3, 6). Thus the sink is labeled with 3, 3e56 = 4e65 = 0e36 = 3e63 = 0412356e14 = 4e41 = 0e12 = 5e21 = 0e24 = 2e42 = 0e25 = 2e52 = 0e45 = 3 e54 = 0e23 = 3 e32 = 04,15,12,23,23,3252021-10-30College of Computer

27、 Science & Technology, BUPTExample 3 : step 5nthe path is l, 2, 3, 6n subtract 3 from the excess capacity of each edge, indicating an increased flow through that edge, and adding an equal amount to the excess capacities of the (virtual) edges.262021-10-30College of Computer Science & Technol

28、ogy, BUPTExample 3nWe now return to Step l with the situation shown ase56 = 4e65 = 0e36 = 0e63 = 3412356e14 = 4e41 = 0e12 = 2e21 = 3e24 = 2e42 = 0e25 = 2e52 = 0e45 = 3 e54 = 0e23 = 0 e32 = 3272021-10-30College of Computer Science & Technology, BUPTSteps 1,2,3e56 = 4e65 = 0e36 = 0e63 = 3412356e14

29、 = 4e41 = 0e12 = 2e21 = 3e24 = 2e42 = 0e25 = 2e52 = 0e45 = 3 e54 = 0e23 = 0 e32 = 34,12,12,22,5282021-10-30College of Computer Science & Technology, BUPTStep 5nWork back along path 1,2,5,6, subtracting 2 from the excess capacities of these edgesnAnd return to Step 1.e56 = 2e65 = 2e36 = 0e63 = 34

30、12356e14 = 4e41 = 0e12 = 0e21 = 5e24 = 2e42 = 0e25 = 0e52 = 2e45 = 3 e54 = 0e23 = 0 e32 = 3292021-10-30College of Computer Science & Technology, BUPTStep 1,2,3e56 = 2e65 = 2e36 = 0e63 = 3412356e14 = 4e41 = 0e12 = 0e21 = 5e24 = 2e42 = 0e25 = 0e52 = 2e45 = 3 e54 = 0e23 = 0 e32 = 34,13,42,52,530202

31、1-10-30College of Computer Science & Technology, BUPTStep 5nWork back along the path 1,4,5,6, adjusting excess capacities.nReturn to Step 1.e56 = 0e65 = 4e36 = 0e63 = 3412356e14 = 2e41 = 2e12 = 0e21 = 5e24 = 2e42 = 0e25 = 0e52 = 2e45 = 1 e54 = 2e23 = 0 e32 = 3312021-10-30College of Computer Scie

32、nce & Technology, BUPTGo further?nStep 1,2,32,11,51,4e56 = 0e65 = 4e36 = 0e63 = 3412356e14 = 2e41 = 2e12 = 0e21 = 5e24 = 2e42 = 0e25 = 0e52 = 2e45 = 1 e54 = 2e23 = 0 e32 = 3322021-10-30College of Computer Science & Technology, BUPTstep 4nTerminated with the final overall flow 7.nQ.E.D.4 3412

33、356 2 5 02 2 3Go back332021-10-30College of Computer Science & Technology, BUPTExample 4e36 = 6e63 = 0e46 = 7e64 = 0512436e15 = 8e51 = 0e12 = 5e21 = 0e25= 2e52 = 0e23 = 3e32 = 0e53 = 6 e35 = 0e24 = 4 e42 = 0342021-10-30College of Computer Science & Technology, BUPTStep 1,2,3e36 = 6e63 = 0e46

34、 = 7e64 = 0512436e15 = 8e51 = 0e12 = 5e21 = 0e25= 2e52 = 0e23 = 3e32 = 0e53 = 6 e35 = 0e24 = 4 e42 = 08,15,14,23,23,3352021-10-30College of Computer Science & Technology, BUPTStep 5e36 = 3e63 = 3e46 = 7e64 = 0512436e15 = 8e51 = 0e12 = 2e21 = 3e25= 2e52 = 0e23 = 0e32 = 3e53 = 6 e35 = 0e24 = 4 e42

35、 = 0362021-10-30College of Computer Science & Technology, BUPTStep 1,2,3e36 = 3e63 = 3e46 = 7e64 = 0512436e15 = 8e51 = 0e12 = 2e21 = 3e25= 2e52 = 0e23 = 0e32 = 3e53 = 6 e35 = 0e24 = 4 e42 = 08,12,12,23,36,5372021-10-30College of Computer Science & Technology, BUPTStep 5e36 = 0e63 = 6e46 = 7e

36、64 = 0512436e15 = 5e51 = 3e12 =2 e21 = 3e25= 2e52 = 0e23 = 0e32 = 3e53 = 3 e35 = 3e24 = 4 e42 = 0382021-10-30College of Computer Science & Technology, BUPTStep 1,2,3e36 =0e63 =6e46 = 7e64 = 0512436e15 = 5e51 = 3e12 =2 e21 = 3e25= 2e52 = 0e23 = 0e32 = 3e53 = 3 e35 = 3e24 = 4 e42 = 05,13,52,12,42,

37、2392021-10-30College of Computer Science & Technology, BUPTStep 5e36 = 0e63 = 6e46 = 5e64 = 2512436e15 = 5e51 = 3e12 =0 e21 = 5e25= 2e52 = 0e23 = 0e32 = 3e53 = 3 e35 = 3e24 = 2 e42 = 2402021-10-30College of Computer Science & Technology, BUPTStep 1,2,3e36 = 0e63 = 6e46 = 5e64 = 2512436e15 = 5e51 = 3e12 =0 e21 = 5e25= 2e52 = 0e23 = 0e32 = 3e53 = 3 e35 = 3e24 = 2 e42 = 25,13,53,32,22,4412021-10-30College of Computer Science & Technology, BUPTStep 5e36 = 0e6