📄 chap27.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 27: MAXIMUM FLOW</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="partvii.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap26.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="08f5_1890">CHAPTER 27: MAXIMUM FLOW<a name="08f5_1890"></h1><P>
Just as we can model a road map as a directed graph in order to find the shortest path from one point to another, we can also interpret a directed graph as a "flow network" and use it to answer questions about material flows. Imagine a material coursing through a system from a source, where the material is produced, to a sink, where it is consumed. The source produces the material at some steady rate, and the sink consumes the material at the same rate. The "flow" of the material at any point in the system is intuitively the rate at which the material moves. Flow networks can be used to model liquids flowing through pipes, parts through assembly lines, current through electrical networks, information through communication networks, and so forth.<P>
Each directed edge in a flow network can be thought of as a conduit for the material. Each conduit has a stated capacity, given as a maximum rate at which the material can flow through the conduit, such as 200 gallons of liquid per hour through a pipe or 20 amperes of electrical current through a wire. Vertices are conduit junctions, and other than the source and sink, material flows through the vertices without collecting in them. In other words, the rate at which material enters a vertex must equal the rate at which it leaves the vertex. We call this property "flow conservation," and it is the same as Kirchhoff's Current Law when the material is electrical current.<P>
<a name="08f5_188f">The maximum-flow problem is the simplest problem concerning flow networks. It asks, What is the greatest rate at which material can be shipped from the source to the sink without violating any capacity constraints? As we shall see in this chapter, this problem can be solved by efficient algorithms. Moreover, the basic techniques used by these algorithms can be adapted to solve other network-flow problems.<P>
This chapter presents two general methods for solving the maximum-flow problem. Section 27.1 formalizes the notions of flow networks and flows, formally defining the maximum-flow problem. Section 27.2 describes the classical method of Ford and Fulkerson for finding maximum flows. An application of this method, finding a maximum matching in an undirected bipartite graph, is given in Section 27.3. Section 27.4 presents the preflow-push method, which underlies many of the fastest algorithms for network-flow problems. Section 27.5 covers the "lift-to-front" algorithm, a particular implementation of the preflow-push method that runs in time <I>O</I>(<I>V</I><SUP>3</SUP>). Although this algorithm is not the fastest algorithm known, it illustrates some of the techniques used in the asymptotically fastest algorithms, and it is reasonably efficient in practice.<P>
<h1><a name="08f7_1892">27.1 Flow networks<a name="08f7_1892"></h1><P>
<a name="08f7_1890"><a name="08f7_1891">In this section, we give a graph-theoretic definition of flow networks, discuss their properties, and define the maximum-flow problem precisely. We also introduce some helpful notation.<P>
<h2>Flow networks and flows</h2><P>
<a name="08f8_1892"><a name="08f8_1893"><a name="08f8_1894"><a name="08f8_1895">A <I><B>flow network</I> </B><I>G</I> = (<I>V</I>, <I>E</I>) is a directed graph in which each edge (<I>u,v</I>) <img src="../images/memof12.gif"> <I>E</I> has a nonnegative<B> </B><I><B>capacity</I> </B><I>c</I>(<I>u, v</I>) <img src="../images/gteq.gif"> 0. If (<I>u, v)</I> <img src="../images/notmem.gif"> <I>E,</I> we assume that <I>c</I>(<I>u, v</I>) = 0. We distinguish two vertices in a flow network: a <I><B>source</I></B> <I>s</I> and a <I><B>sink</I></B> <I>t</I>. For convenience, we assume that every vertex lies on some path from the source to the sink. That is, for every vertex <I>v </I><img src="../images/memof12.gif"> <I>V</I>, there is a path <img src="580_a.gif">. The graph is therefore connected, and |<I>E| </I><img src="../images/gteq.gif"> |<I>V</I>| - 1. Figure 27.1 shows an example of a flow network.<P>
We are now ready to define flows more formally. Let <I>G</I> = (<I>V</I>,<I>E</I>) be a flow network (with an implied capacity function <I>c</I>). Let <I>s</I> be the source of the network, and let <I>t</I> be the sink. A <I><B>flow</I></B> in <I>G</I> is a real-valued function <I>f</I>: <I>V</I> x <I>V</I> <img src="../images/arrow12.gif"> <B>R</B> that satisfies the following three properties:<P>
<a name="08f8_1896"><B>Capacity constraint: </B>For all <I>u</I>, <I>v</I> <img src="../images/memof12.gif"> <I>V</I>, we require â (<I>u, v) </I><img src="../images/lteq12.gif"> <I>c</I>(<I>u, v</I>).<P>
<a name="08f8_1897"><B>Skew symmetry: </B>For all <I>u, v</I> <img src="../images/memof12.gif"> <I>V</I>, we require â (<I>u, v</I>) = -â (<I>v, u</I>).<P>
<a name="08f8_1898"><a name="08f8_1899"><B>Flow conservation: </B>For all <I>u</I> <img src="../images/memof12.gif"> <I>V</I> - {<I>s</I>, <I>t</I>}, we require<P>
<img src="580_b.gif"><P>
<a name="08f8_189a"><a name="08f8_189b"><a name="08f8_189c">The quantity â (<I>u, v</I>), which can be positive or negative, is called the <I><B>net flow</I></B> from vertex <I>u</I> to vertex <I>v</I>. The <I><B>value</I></B> of a flow <I>f</I> is defined as<P>
<img src="580_c.gif"><P>
<h4><a name="08f8_189e">(27.1)<a name="08f8_189e"></sub></sup></h4><P>
that is, the total net flow out of the source. (Here, the |<img src="../images/dot10.gif">| notation denotes flow value, not absolute value or cardinality.) In the <I><B>maximum-flow problem</I>,</B> we are given a flow network<I> G</I> with source <I>s </I>and sink <I>t</I>, and we wish to find a flow of maximum value from <I>s</I> to <I>t</I>.<P>
Before seeing an example of a network-flow problem, let us briefly explore the three flow properties. The capacity constraint simply says that the net flow from one vertex to another must not exceed the given capacity. Skew symmetry says that the net flow from a vertex <I>u</I> to a vertex <I>v </I>is the negative of the net flow in the reverse direction. Thus, the net flow from a vertex to itself is 0, since for all <I>u</I> <img src="../images/memof12.gif"> <I>V,</I> we have â (<I>u, u</I>) = - <I>f</I> (<I>u,u</I>), which implies that â (<I>u, u</I>) = 0. The flow-conservation property says that the total net flow out of a vertex other than the source or sink is 0. By skew symmetry, we can rewrite the flow-conservation property as<P>
<img src="581_b.gif"><P>
for all <I>v</I> <img src="../images/memof12.gif"><I> V</I> - {<I>s, t</I>}. That is, the total net flow into a vertex is 0.<P>
<img src="581_a.gif"><P>
<h4><a name="08f8_189f">Figure 27.1 (a) A flow network G = (V, E) for the Lucky Puck Company's trucking problem. The Vancouver factory is the source s, and the Winnipeg warehouse is the sink t. Pucks are shipped through intermediate cities, but only c (u, v) crates per day can go from city u to city v. Each edge is labeled with its capacity. (b) A flow â in G with value |â| = 19. Only positive net flows are shown. If â (u, v) > 0, edge (u, v) is labeled by â (u, v)/c(u, v). (The slash notation is used merely to separate the flow and capacity; it does not indicate division.) If â (u,v) <img src="../images/lteq12.gif"> 0, edge (u, v) is labeled only by its capacity.<a name="08f8_189f"></sub></sup></h4><P>
Observe also that there can be no net flow between <I>u</I> and <I>v</I> if there is no edge between them. If neither (<I>u, v</I>) <img src="../images/memof12.gif"> <I>E</I> nor (<I>v, u</I>) <I>E</I>, then <I>c</I>(<I>u, v</I>) = <I>c</I>(<I>v, u</I>) = 0. Hence, by the capacity constraint, â(<I>u, v</I>) <img src="../images/lteq12.gif"> 0 and â (<I>v, u</I>) <img src="../images/lteq12.gif"> 0. But since â (<I>u, v</I>) = - â (<I>v, u</I>), by skew symmetry, we have â(<I>u, v</I>) = â(<I>v, u</I>) = 0. Thus, nonzero net flow from vertex <I>u</I> to vertex <I>v </I>implies that (<I>u, v</I>) <img src="../images/memof12.gif"> <I>E</I> or (<I>v, u</I>) <img src="../images/memof12.gif"> <I>E</I> (or both).<P>
<a name="08f8_189d">Our last observation concerning the flow properties deals with net flows that are positive. The <I><B>positive net flow</I></B> entering a vertex <I>v</I> is defined by<P>
<img src="581_c.gif"><P>
<h4><a name="08f8_18a0">(27.2)<a name="08f8_18a0"></sub></sup></h4><P>
The positive net flow leaving a vertex is defined symmetrically. One interpretation of the flow-conservation property is that the positive net flow entering a vertex other than the source or sink must equal the positive net flow leaving the vertex.<P>
<P>
<h2>An example of network flow</h2><P>
A flow network can model the trucking problem shown in Figure 27.1. The Lucky Puck Company has a factory (source <I>s</I>) in Vancouver that manufactures hockey pucks, and it has a warehouse (sink <I>t</I>) in Winnipeg that stocks them. Lucky Puck leases space on trucks from another firm to ship the pucks from the factory to the warehouse. Because the trucks travel over specified routes between cities and have a limited capacity, Lucky Puck can ship at most <I>c</I>(<I>u, v</I>) crates per day between each pair of cities <I>u </I>and <I>v</I> in Figure 27.1 (a). Lucky Puck has no control over these routes and capacities and so cannot alter the flow network shown in Figure 27.1(a). Their goal is to determine the largest number <I>p</I> of crates per day that can be shipped and then to produce this amount, since there is no point in producing more pucks than they can ship to their warehouse.<P>
The rate at which pucks are shipped along any truck route is a flow. The pucks emanate from the factory at the rate of <I>p</I> crates per day, and <I>p </I>crates must arrive at the warehouse each day. Lucky Puck is not concerned with how long it takes for a given puck to get from the factory to the warehouse; they care only that <I>p</I> crates per day leave the factory and <I>p </I>crates per day arrive at the warehouse. The capacity constraints are given by the restriction that the flow â(<I>u, v</I>) from city <I>u </I>to city <I>v</I> to be at most <I>c</I>(<I>u, v</I>) crates per day. In a steady state, the rate at which pucks enter an intermediate city in the shipping network must equal the rate at which they leave; otherwise, they would pile up. Flow conservation is therefore obeyed. Thus, a maximum flow in the network determines the maximum number <I>p</I> of crates per day that can be shipped.<P>
Figure 27.1(b) shows a possible flow in the network that is represented in a way that naturally corresponds to shipments. For any two vertices <I>u </I>and <I>v</I> in the network, the net flow â(<I>u, v</I>) corresponds to a shipment of â(<I>u, v</I>) crates per day from <I>u</I> to <I>v</I>. If â(<I>u, v</I>) is 0 or negative, then there is no shipment from <I>u</I> to <I>v</I>. Thus, in Figure 27.1(b), only edges with positive net flow are shown, followed by a slash and the capacity of the edge.<P>
We can understand the relationship between net flows and shipments somewhat better by focusing on the shipments between two vertices. Figure 27.2(a) shows the subgraph induced by vertices <I>v</I><SUB>1</SUB> and <I>v</I><SUB>2</SUB> in the flow network of Figure 27.1. If Lucky Puck ships 8 crates per day from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2,</SUB> the result is shown in Figure 27.2(b): the net flow from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB> is 8 crates per day. By skew symmetry, we also say that the net flow in the reverse direction, from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB>, is -8 crates per day, even though we do not ship any pucks from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB>. In general, the net flow from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB> is the number of crates per day shipped from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB> minus the number per day shipped from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB>. Our convention for representing net flows is to show only positive net flows, since they indicate the actual shipments; thus, only an 8 appears in the figure, without the corresponding -8.<P>
<img src="583_a.gif"><P>
<h4><a name="08f9_189f">Figure 27.2 Cancellation. (a) Vertices v<SUB>1</SUB>, and v<SUB>2,</SUB> with c(v<SUB>1</SUB><FONT FACE="Times New Roman" SIZE=2>, v<SUB>2</SUB><FONT FACE="Times New Roman" SIZE=2>)</FONT></FONT> = 10 and c(v<SUB>2</SUB><FONT FACE="Times New Roman" SIZE=2>, v<SUB>1</SUB><FONT FACE="Times New Roman" SIZE=2> )</FONT></FONT> = 4. (b) How we indicate the net flow when 8 crates per day are shipped from v<SUB>1</SUB> to v<SUB>2</SUB>. (c) An additional shipment of 3 crates per day is made from v<SUB>2</SUB> to v<SUB>1</SUB>. (d) By cancelling flow going in opposite directions, we can represent the situation in (c) with positive net flow in one direction only. (e) Another 7 crates per day is shipped from v<SUB>2</SUB> to v<SUB>1</SUB>.<a name="08f9_189f"></sub></sup></h4><P>
Now let's add another shipment, this time of 3 crates per day from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB>. One natural representation of the result is shown in Figure 27.2(c). We now have a situation in which there are shipments in both directions between <I>v</I><SUB>1</SUB> and <I>v</I><SUB>2</SUB>. We ship 8 crates per day from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB> and 3 crates per day from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB>. What are the net flows between the two vertices? The net flow from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB> is 8 - 3 = 5 crates per day, and the net flow from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB> is 3 - 8 = -5 crates per day.<P>
<a name="08f9_189e">The situation is equivalent in its result to the situation shown in Figure 27.2(d), in which 5 crates per day are shipped from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB> and no shipments are made from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB>. In effect, the 3 crates per day from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB> are <I><B>cancelled</I> </B>by 3 of the 8 crates per day from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB>. In both situations, the net flow from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB> is 5 crates per day, but in (d), actual shipments are made in one direction only.<P>
In general, cancellation allows us to represent the shipments between two cities by a positive net flow along at most one of the two edges between the corresponding vertices. If there is zero or negative net flow from one vertex to another, no shipments need be made in that direction. That is, any situation in which pucks are shipped in both directions between two cities can be transformed using cancellation into an equivalent situation in which pucks are shipped in one direction only: the direction of positive net flow. Capacity constraints are not violated by this transformation, since we reduce the shipments in both directions, and conservation constraints are not violated, since the net flow between the two vertices is the same.<P>
Continuing with our example, let us determine the effect of shipping another 7 crates per day from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB>. Figure 27.2(e) shows the result using the convention of representing only positive net flows. The net flow from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB> becomes 5 - 7 = -2, and the net flow from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB> becomes 7 - 5 = 2. Since the net flow from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB> is positive, it represents a shipment of 2 crates per day from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB>. The net flow from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB> is -2 crates per day, and since the net flow is not positive, no pucks are shipped in this direction. Alternatively, of the 7 additional crates per day from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB>, we can view 5 of them as cancelling the shipment of 5 per day from <I>v</I><SUB>1</SUB> to <I>v</I><SUB>2</SUB>, which leaves 2 crates as the actual shipment per day from <I>v</I><SUB>2</SUB> to <I>v</I><SUB>1</SUB>.<P>
<img src="584_a.gif"><P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -