1、Yang JCollege of Computer Science & TechnologyBeijing University of Posts & TelecommunicationsDiscrete Mathematical StructuresTransport networks（ 传输网） 2* College of Computer Science & Technology, BUPTContentn Application of digraphn Conceptn Capacity (容量 )n Transport network (传输网 )n Flow (流量 )n Virt
2、ual flow (虚流量 )n Maximal flow (最大流量 )n Labeling algorithm (标记算法 )3* College of Computer Science & Technology, BUPTDirected graph (Digraph)n An important use of labeled digraphs is to model what are commonly called transport networks.n The label on an edge represents the maximum flow that can be pass
3、ed through that edge and is called the capacity（ 容量） of the edge. Many situations can be modeled in this way.4* College of Computer Science & Technology, BUPTExamplen Figure below might as easily represent an oil pipeline, a highway system, a communications network, or an electric power grid. 5* Col
4、lege of Computer Science & Technology, BUPTExamplen The vertices of a network are usually called nodes and may denote pumping stations, shipping depots, relay stations, or highway interchanges.6* College of Computer Science & Technology, BUPTTransport networkn More formally, a transport network, or
5、a network, is a connected digraph N with the following properties:n There is a unique node, the source（ 源端） , that has in-degree 0. We generally label the source node l.n There is a unique node, the sink（ 宿端） , that has out-degree 0. If N has n nodes, we generally label the sink as node n.n The grap
6、h N is labeled. The label, Cij, on edge (i, j) is a nonnegative number called the capacity of the edge.7* College of Computer Science & Technology, BUPTFlowsn Mathematically, a flow（ 流量） in a network N is a function that assigns to each edge (i, j) of N a nonnegative number Fij that does not exceed
7、Cij.n Conservation of flow（ 流量守恒）n Value of the flow8* College of Computer Science & Technology, BUPTFlowsn We can represent a flow F by labeling each edge (i, j) with the pair (Cij, Fij)n Example 1n Here value(F) = 59* College of Computer Science & Technology, BUPTMaximum Flows（ 最大流量）n For any netw
8、ork 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. n For obvious reasons this is commonly referred to the maximum flow problem.10* College of Computer Science & Technology, BUPTExample 2n Even for a small network, we need a systematic procedure for solving the maximum flow problem.
