chap27.htm

CLRS-算法导论

<a name="08fc_18b6">27.1-7<a name="08fc_18b6"><P>
<a name="08fc_18a8"><a name="08fc_18a9">Let <I>f</I> be a flow in a network, and let <img src="../images/alpha12.gif"> be a real number. The <I><B>scalar flow product</I></B> <img src="../images/alpha12.gif"><I>f</I> is a function from <I>V</I> X <I>V</I> to <B>R</B> defined by<P>
<pre>(<img src="../images/alpha12.gif"><I>f</I>)(<I>u</I>, <I>v</I>) = <img src="../images/alpha12.gif"> <img src="../images/dot10.gif"> <I>f</I>(<I>u</I>, <I>v</I>).</sub></sup></pre><P>
Prove that the flows in a network form a convex set by showing that if <I>f</I><SUB>1 </SUB>and <I>f</I><SUB>2</SUB> are flows, then so is <img src="../images/alpha12.gif"><I>f</I><SUB>1</SUB> + (1 - <img src="../images/alpha12.gif">) <I>f</I><SUB>2</SUB> for all <img src="../images/alpha12.gif"> in the range 0 <img src="../images/lteq12.gif"> <img src="../images/alpha12.gif"> <img src="../images/lteq12.gif"> 1.<P>
<a name="08fc_18b7">27.1-8<a name="08fc_18b7"><P>
<a name="08fc_18aa">State the maximum-flow problem as a linear-programming problem.<P>
<a name="08fc_18b8">27.1-9<a name="08fc_18b8"><P>
<a name="08fc_18ab"><a name="08fc_18ac"><a name="08fc_18ad">The flow-network model introduced in this section supports the flow of one commodity; a <I><B>multicommodity flow network</I></B> supports the flow of <I>p </I>commodities between a set of <I>p</I> <I><B>source vertices</I></B> <I>S</I> = {<I>s</I><SUB>1</SUB>, <I>s</I><SUB>2</SUB>, . . .,<I>s</I><SUB>p</SUB>} and a set of <I>p</I> <I><B>sink vertices</I></B> <I>T</I> = {<I>t</I><SUB>1</SUB>, <I>t</I><SUB>2</SUB>, . . .,<I>t</I><SUB>p</SUB>}. The net flow of the <I>i</I>th commodity from <I>u</I> to <I>v</I> is denoted <I>f</I><SUB>i</SUB>(<I>u</I>, <I>v</I>). For the <I>i</I>th commodity, the only source is <I>s<SUB>i</I></SUB> and the only sink is <I>t<SUB>i</I></SUB>. There is flow conservation independently for each commodity: the net flow of each commodity out of each vertex is zero unless the vertex is the source or sink for the commodity. The sum of the net flows of all commodities from <I>u</I> to <I>v</I> must not exceed <I>c</I>(<I>u</I>, <I>v</I>), and in this way the commodity flows interact. The <I><B>value</I></B> of the flow of each commodity is the net flow out of the source for that commodity. The <I><B>total flow value</I></B> is the sum of the values of all <I>p</I> commodity flows. Prove that there is a polynomial-time algorithm that solves the problem of finding the maximum total flow value of a multicommodity flow network by formulating the problem as a linear program.<P>
<P>


<P>







<h1><a name="08fd_18b1">27.2 The Ford-Fulkerson method<a name="08fd_18b1"></h1><P>
<a name="08fd_18ae"><a name="08fd_18af">This section presents the Ford-Fulkerson method for solving the maximum-flow problem. We call it a &quot;method&quot; rather than an &quot;algorithm&quot; because it encompasses several implementations with differing running times. The Ford-Fulkerson method depends on three important ideas that transcend the method and are relevant to many flow algorithms and problems: residual networks, augmenting paths, and cuts. These ideas are essential to the important max-flow min-cut theorem (Theorem 27.7), which characterizes the value of a maximum flow in terms of cuts of the flow network. We end this section by presenting one specific implementation of the Ford-Fulkerson method and analyzing its running time.<P>
The Ford-Fulkerson method is iterative. We start with <I>f</I>(<I>u</I>, <I>v</I>) = 0 for all <I>u</I>,<I>v</I> <img src="../images/memof12.gif"> <I>V</I>, giving an initial flow of value 0. At each iteration, we increase the flow value by finding an &quot;augmenting path,&quot; which we can think of simply as a path from the source <I>s</I> to the sink <I>t</I> along which we can push more flow, and then augmenting the flow along this path. We repeat this process until no augmenting path can be found. The max-flow min-cut theorem will show that upon termination, this process yields a maximum flow.<P>
<pre><a name="08fd_18b0">FORD-FULKERSON-METHOD(<I>G</I>, <I>s</I>, <I>t</I>)</sub></sup></pre><P>
<pre>1  initialize flow <I>f</I> to 0</sub></sup></pre><P>
<pre>2  <B>while</B> there exists an augmenting path <I>p</I></sub></sup></pre><P>
<pre>3      <B>do</B> augment flow <I>f</I> along <I>p</I></sub></sup></pre><P>
<pre>4  <B>return</B> <I>f</I></sub></sup></pre><P>





<h2>Residual networks</h2><P>
<a name="08fe_18b1"><a name="08fe_18b2">Intuitively, given a flow network and a flow, the residual network consists of edges that can admit more net flow. More formally, suppose that we have a flow network <I>G</I> = (<I>V</I>, <I>E</I>) with source <I>s</I> and sink <I>t</I>. Let <I>f</I> be a flow in <I>G</I>, and consider a pair of vertices <I>u</I>, <I>v</I> <img src="../images/memof12.gif"> <I>V</I>. The amount of <I>additional </I>net flow we can push from <I>u</I> to <I>v</I> before exceeding the capacity <I>c</I>(<I>u</I>, <I>v</I>) is the <I><B>residual capacity</I></B> of (<I>u</I>, <I>v</I>), given by<P>
<pre><I>c<SUB>f</I></SUB>(<I>u</I>, <I>v</I>) = <I>c</I>(<I>u</I>, <I>v</I>) - <I>f</I>(<I>u</I>, <I>v</I>) .</sub></sup></pre><P>
<h4><a name="08fe_18b7">(27.5)<a name="08fe_18b7"></sub></sup></h4><P>
For example, if <I>c</I>(<I>u</I>, <I>v</I>) = 16 and <I>f</I>(<I>u</I>, <I>v</I>) = 11, then we can ship <I>c<SUB>f</I></SUB>(<I>u</I>, <I>v</I>) = 5 more units of flow before we exceed the capacity constraint on edge(<I>u</I>, <I>v</I>). When the net flow <I>f</I>(<I>u</I>, <I>v</I>) is negative, the residual capacity <I>c<SUB>f</I></SUB>(<I>u</I>, <I>v</I>) is greater than the capacity <I>c</I>(<I>u</I>, <I>v</I>). For example, if <I>c</I>(<I>u</I>, <I>v</I>) = 16 and <I>f</I>(<I>u</I>, <I>v</I>) = -4, then the residual capacity <I>c<SUB>f</I></SUB>(<I>u</I>, <I>v</I>) is 20. We can interpret this as follows. There is a net flow of 4 units from <I>v</I> to <I>u</I>, which we can cancel by pushing a net flow of 4 units from <I>u</I> to <I>v</I>. We can then push another 16 units from <I>u</I> to <I>v</I> before violating the capacity constraint on edge (<I>u</I>, <I>v</I>). We have thus pushed an additional 20 units of flow, starting with a net flow <I>f</I>(<I>u</I>, <I>v</I>) = -4, before reaching the capacity constraint.<P>
<a name="08fe_18b3"><a name="08fe_18b4">Given a flow network <I>G</I> = (<I>V</I>, <I>E</I>) and a flow <I>f</I>, the <I><B>residual network</I></B> of <I>G</I> induced by <I>f</I> is <I>G<SUB>f</I></SUB> = (<I>V</I>, <I>E<SUB>f</I></SUB>), where<P>
<pre><I>Ef</I> = {(<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>V </I>X<I> </I>V<I> : </I>c<SUB>f<I></SUB>(</I>u<I>, </I>v<I>) &gt; 0} .</I></sub></sup></pre><P>
<a name="08fe_18b5"><a name="08fe_18b6">That is, as promised above, each edge of the residual network, or <I><B>residual edge</I></B>, can admit a strictly positive net flow. Figure 27.4(a) repeats the flow network <I>G</I> and flow <I>f</I> of Figure 27.1(b), and Figure 27.4(b) shows the corresponding residual network <I>G<SUB>f</I></SUB>.<P>
Notice that (<I>u</I>, <I>v</I>) may be a residual edge in <I>E<SUB>f</I></SUB> even if it was not an edge in <I>E</I>. In other words, it may very well be the case that <img src="588_a.gif">. The residual network in Figure 27.4(b) includes several such edges not in the original flow network, such as (<I>v</I><SUB>1</SUB>, <I>s</I>) and (<I>v</I><SUB>2</SUB>, <I>v</I><SUB>3</SUB>). Such an edge (<I>u</I>, <I>v</I>) appears in <I>G<SUB>f</I></SUB> only if (<I>v</I>, <I>u</I>) <img src="../images/memof12.gif"> <I>E</I> and there is positi<I>v</I>e net flow from <I>v</I> to <I>u</I>. Because the net flow <I>f</I>(<I>u</I>, <I>v</I>) from <I>u</I> to <I>v</I> is negative, <I>c<SUB>f</I></SUB>(<I>u</I>, <I>v</I>) = <I>c</I>(<I>u</I>, <I>v</I>) - <I>f</I>(<I>u</I>, <I>v</I>) is positive and (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> E<I><SUB>f</I></SUB>. Because an edge (<I>u</I>, <I>v</I>) can appear in a residual network only if at least one of (<I>u</I>, <I>v</I>) and (<I>v</I>, <I>u</I>) appears in the original network, we have the bound<P>
<pre>|<I>E<SUB>f</I></SUB>|<img src="../images/lteq12.gif"> 2 |E| .</sub></sup></pre><P>
<img src="589_a.gif"><P>
<h4><a name="08fe_18b8">Figure 27.4 (a) The flow network G and flow f of Figure 27.1(b). (b) The residual network G<SUB>f </SUB>with augmenting path p shaded; its residual capacity is c<SUB>f</SUB>(p) = c(v<SUB>2</SUB>, v<SUB>3</SUB>) = 4. (c) The flow in G that results from augmenting along path p by its residual capacity 4. (d) The residual network induced by the flow in (c).<a name="08fe_18b8"></sub></sup></h4><P>
Observe that the residual network <I>G<SUB>f</I></SUB> is itself a flow network with capacities given by <I>c<SUB>f</I></SUB>. The following lemma shows how a flow in a residual network relates to a flow in the original flow network.<P>
<a name="08fe_18b9">Lemma 27.2<a name="08fe_18b9"><P>
Let <I>G = </I>(<I>V, E</I>) be a flow network with source <I>s </I>and sink <I>t</I>, and let <I>f</I> be a flow in <I>G</I>. Let <I>G<SUB>f</I></SUB> be the residual network of <I>G</I> induced by <I>f</I>, and let <I>f</I>'<I><SUB> </SUB>be a flow in </I>G<SUB>f<I></SUB>. Then, the flow sum </I>f<I> + </I>f<I>'</I> defined by equation (27.4) is a flow in <I>G</I> with value |<I>f</I> + <I>f</I>'<I>|</I> = |<I>f</I>|<I> + |</I>f<I>'</I>|.<P>
<I><B>Proof     </I></B>We must verify that skew symmetry, the capacity constraints, and  flow conservation are obeyed. For skew symmetry, note that for all <I>u, v </I><img src="../images/memof12.gif"> <I>V</I>, we have<P>
<pre>(<I>f</I> + <I>f</I>')(<I>u</I>, <I>v</I>)  =  <I>f</I>(<I>u</I>, <I>v</I>) + <I>f</I>'(<I>u</I>, <I>v</I>)</sub></sup></pre><P>
<pre>=  -<I>f</I>(<I>v</I>, <I>u</I>) - <I>f</I>'(<I>v</I>, <I>u</I>)</sub></sup></pre><P>
<pre>=  -(<I>f</I>(<I>v</I>, <I>u</I>) + <I>f</I>'(<I>v</I>, <I>u</I>))</sub></sup></pre><P>
<pre>=  -(<I>f</I> + <I>f</I>')(<I>v</I>, <I>u</I>).</sub></sup></pre><P>
For the capacity constraints, note that <I>f</I>'(<I>u, v</I>) <img src="../images/lteq12.gif"> <I>c<SUB>f</I></SUB>(<I>u, v</I>) for all <I>u, v </I><img src="../images/memof12.gif"> <I>V</I>. By equation (27.5), therefore,<P>
<pre>(<I>f</I> + <I>f</I>')(<I>u</I>, <I>v</I>)  =  <I>f</I>(<I>u</I>, <I>v</I>) + <I>f</I>'(<I>u</I>, <I>v</I>)</sub></sup></pre><P>
<pre><img src="../images/lteq12.gif">  <I>f</I>(<I>u, v</I>) + (<I>c</I>(<I>u, v</I>) - <I>f</I>(<I>u, v</I>))</sub></sup></pre><P>
<pre>=  <I>c</I>(<I>u, v</I>) .</sub></sup></pre><P>
For flow conservation, note that for all <I>u </I><img src="../images/memof12.gif"> <I>V - {s, t</I>}, we have<P>
<img src="590_a.gif"><P>
Finally, we have<P>
<img src="590_b.gif"><P>
<P>