chap27.htm

介绍算法的书籍

<h2>Augmenting paths</h2><P>
<a name="08ff_18b7"><a name="08ff_18b8">Given a flow network <I>G</I> = (<I>V, E</I>) and a flow <I>f</I>, an <B>augmenting path</B> <I>p</I> is a simple path from <I>s</I> to <I>t</I> in the residual network <I>G<SUB>f</I></SUB>. By the definition of the residual network, each edge (<I>u, v</I>) on an augmenting path admits some additional positive net flow from <I>u</I> to <I>v</I> without violating the capacity constraint on the edge.<P>
<a name="08ff_18b9"><a name="08ff_18ba">The shaded path in Figure 27.4(b) is an augmenting path. Treating the residual network <I>G<SUB>f</I> </SUB>in the figure as a flow network, we can ship up to 4 units of additional net flow through each edge of this path without violating a capacity constraint, since the smallest residual capacity on this path is <I>c<SUB>f</I></SUB>(<I>v</I><SUB>2</SUB>, <I>v</I><SUB>3</SUB>) = 4. We call the maximum amount of net flow that we can ship along the edges of an augmenting path <I>p</I> the <I><B>residual capacity</I></B> of <I>p</I>, given by<P>
<pre><I>c<SUB>f</I></SUB>(<I>p</I>) = min{<I>c<SUB>f</I></SUB>(<I>u, v</I>): (<I>u, v</I>) is on <I>p</I>}.</sub></sup></pre><P>
The following lemma, whose proof is left as Exercise 27.2-7, makes the above argument more precise.<P>
<a name="08ff_18bb">Lemma 27.3<a name="08ff_18bb"><P>
Let <I>G</I> = (<I>V</I>, <I>E</I>) be a flow network, let &acirc; be a flow in <I>G</I>, and let <I>p</I> be an augmenting path in G<SUB>&acirc;</SUB>. Define a function &acirc;<I><SUB>p</I></SUB> : <I>V</I> x <I>V</I> <img src="../images/arrow12.gif"> <B>R</B> by<P>
<img src="591_a.gif"><P>
<h4><a name="08ff_18bc">(27.6)<a name="08ff_18bc"></sub></sup></h4><P>
Then, &acirc;<I><SUB>p</I></SUB> is a flow in <I>G</I><SUB>&acirc;</SUB> with value |&acirc;<I><SUB>p</I></SUB>| = <I>c</I><SUB>&acirc;</SUB>(<I>p</I>) &gt; 0.      <P>
The following corollary shows that if we add &acirc;<I><SUB>p</I></SUB> to &acirc;, we get another flow in <I>G</I> whose value is closer to the maximum. Figure 27.4(c) shows the result of adding &acirc;<I><SUB>p</I></SUB> in Figure 27.4(b) to &acirc; from Figure 27.4(a).<P>
<a name="08ff_18bd">Corollary 27.4<a name="08ff_18bd"><P>
Let <I>G</I> = (<I>V</I>, <I>E</I>) be a flow network, let &acirc; be a flow in <I>G</I>, and let <I>p</I> be an augmenting path in G<SUB>&acirc;</SUB>. Let &acirc;<I><SUB>p</I></SUB> be defined as in equation (27.6). Define a function &acirc;' : <I>V</I> x <I>V</I> <img src="../images/arrow12.gif"> <B>R</B> by &acirc;' = &acirc; + &acirc;<I><SUB>p</I></SUB>. Then, &acirc;' is a flow in <I>G</I> with value | &acirc;' | =  | &acirc; | + |&acirc;<I><SUB>p</I></SUB>| &gt; | &acirc; |.<P>
<I><B>Proof     </I></B>Immediate from Lemmas 27.2 and 27.3.      <P>
<P>







<h2>Cuts of flow networks</h2><P>
The Ford-Fulkerson method repeatedly augments the flow along augmenting paths until a maximum flow has been found. The max-flow min-cut theorem, which we shall prove shortly, tells us that a flow is maximum if and only if its residual network contains no augmenting path. To prove this theorem, though, we must first explore the notion of a cut of a flow network.<P>
<a name="0900_18bb"><a name="0900_18bc"><a name="0900_18bd"><a name="0900_18be">A <I><B>cut</I></B> (<I>S</I>, <I>T</I>) of flow network <I>G</I> = (<I>V</I>, <I>E</I>) is a partition of <I>V</I> into <I>S</I> and <I>T</I> = <I>V</I> - <I>S</I> such that <I>s</I> <img src="../images/memof12.gif"> <I>S</I> and <I>t</I> <img src="../images/memof12.gif"> <I>T</I>. (This definition is like the definition of &quot;cut&quot; that we used for minimum spanning trees in Chapter 24, except that here we are cutting a directed graph rather than an undirected graph, and we insist that <I>s</I> <img src="../images/memof12.gif"> <I>S</I> and <I>t</I> <img src="../images/memof12.gif"> <I>T</I>.) If <I>f</I> is a flow, then the <I><B>net flow</I></B> across the cut (<I>S</I>, <I>T</I>) is defined to be &acirc;(<I>S</I>, <I>T</I>). The <I><B>capacity</I></B> of the cut (<I>S</I>, <I>T</I>) is <I>c</I>(<I>S</I>, <I>T</I>).<P>
Figure 27.5 shows the cut ({<I>s</I>, <I>v</I><SUB>l</SUB>, <I>v</I><SUB>2</SUB>}, {<I>v</I><SUB>3</SUB>, <I>v</I><SUB>4</SUB>, <I>t</I>}) in the flow network of Figure 27.1(b). The net flow across this cut is<P>
<pre>&acirc;(<I>v</I><SUB>1</SUB>, <I>v</I><SUB>3</SUB>) + &acirc;(<I>v</I><SUB>2</SUB>, <I>v</I><SUB>3</SUB>) + &acirc;(<I>v</I><SUB>2</SUB>, <I>v</I><SUB>4</SUB>)  =  12 + (-4) + 11</sub></sup></pre><P>
<pre>=  19,</sub></sup></pre><P>
and its capacity is<P>
<pre><I>c</I>(<I>v</I><SUB>l</SUB>, <I>v</I><SUB>3</SUB>) + <I>c</I>(<I>v</I><SUB>2</SUB>, <I>v</I><SUB>4</SUB>)  =  12 + 14</sub></sup></pre><P>
<pre>=  26.</sub></sup></pre><P>
<img src="592_a.gif"><P>
<h4><a name="0900_18c0">Figure 27.5 A cut (S, T) in the flow network of Figure 27.1(b), where S = {s, v<SUB>1</SUB>, v<SUB>2</SUB> } and T = {v<SUB>3</SUB>, v<SUB>4</SUB>, t}. The vertices in S are black, and the vertices in T are white. The net flow across (S, T) is &acirc;(S, T) = 19, and the capacity is c(S, T) = 26.<a name="0900_18c0"></sub></sup></h4><P>
Observe that the net flow across a cut can include negative net flows between vertices, but that the capacity of a cut is composed entirely of non-negative values.<P>
The following lemma shows that the value of a flow in a network is the net flow across any cut of the network.<P>
<a name="0900_18c1">Lemma 27.5<a name="0900_18c1"><P>
Let &acirc; be a flow in a flow network <I>G</I> with source <I>s</I> and sink <I>t</I>, and let (<I>S</I>, <I>T</I>) be a cut of <I>G</I>. Then, the net flow across (<I>S</I>, <I>T</I>) is &acirc;(<I>S</I>, <I>T</I>) = | &acirc; |.<P>
<I><B>Proof     </I></B>Using Lemma 27.1 extensively, we have<P>
<pre>&acirc;(<I>S</I>, <I>T</I>)  =  &acirc;(<I>S</I>, <I>V</I>) - &acirc;(<I>S</I>, <I>S</I>)</sub></sup></pre><P>
<pre>=  &acirc;(<I>S</I>, <I>V</I>)</sub></sup></pre><P>
<pre>=  &acirc;(<I>s</I>, <I>V</I>) + &acirc;(<I>S</I> - <I>s</I>, <I>V</I>)</sub></sup></pre><P>
<pre>=  &acirc;(<I>s</I>, <I>V</I>)</sub></sup></pre><P>
<pre>=  | &acirc; | .      </sub></sup></pre><P>
An immediate corollary to Lemma 27.5 is the result we proved earlier--equation (27.3)--that the value of a flow is the net flow into the sink.<P>
Another corollary to Lemma 27.5 shows how cut capacities can be used to bound the value of a flow.<P>
<a name="0900_18c2">Corollary 27.6<a name="0900_18c2"><P>
The value of any flow &acirc; in a flow network <I>G</I> is bounded from above by the capacity of any cut of <I>G</I>.<P>
<I><B>Proof     </I></B>Let (<I>S</I>, <I>T</I>) be any cut of <I>G</I> and let &acirc; be any flow. By Lemma 27.5 and the capacity constraints,<P>
<pre>|<I>&acirc;</I>|  =  <I>&acirc;</I>(<I>S</I>, <I>T</I>)</sub></sup></pre><P>
<img src="593_a.gif"><P>
We are now ready to prove the important max-flow min-cut theorem.<P>
<a name="0900_18c3">Theorem 27.7<a name="0900_18c3"><P>
<a name="0900_18bf">If &acirc; is a flow in a flow network <I>G</I> = (<I>V</I>, <I>E</I>) with source <I>s</I> and sink <I>t</I>, then the following conditions are equivalent:<P>
1.     &acirc; is a maximum flow in <I>G</I>.<P>
2.     The residual network <I>G</I><SUB>&acirc;</SUB> contains no augmenting paths.<P>
3.     | &acirc; | = <I>c</I>(<I>S</I>, <I>T</I>) for some cut (<I>S</I>, <I>T</I>) of <I>G</I>.<P>
<I><B>Proof     </I></B>(1) <img src="../images/rtbigar.gif"> (2): Suppose for the sake of contradiction that &acirc; is a maximum flow in <I>G</I> but that <I>G</I><SUB>&acirc;</SUB> has an augmenting path <I>p</I>. Then, by Corollary 27.4, the flow sum &acirc; + &acirc;<I><SUB>p</I></SUB>, where &acirc;<I><SUB>p</I></SUB> is given by equation (27.6), is a flow in <I>G</I> with value strictly greater than | &acirc; |, contradicting the assumption that &acirc; is a maximum flow.<P>
(2) <img src="../images/rtbigar.gif"> (3): Suppose that <I>G</I><SUB>&acirc;</SUB> has no augmenting path, that is, that <I>G</I><SUB>&acirc; </SUB>contains no path from <I>s</I> to <I>t</I>. Define<P>
<I>S</I> = {<I>v</I> <img src="../images/memof12.gif"> <I>V </I>: there exists a path from <I>s</I> to <img src="../images/upsil12.gif"><I></I> in <I>G</I><SUB>&acirc;</SUB>}<P>
and <I>T</I> = <I>V</I> - <I>S</I>. The partition (<I>S</I>, <I>T</I>) is a cut: we have <I>s</I> <img src="../images/memof12.gif"> <I>S</I> trivially and <I>t</I> <img src="../images/notmem.gif"> <I>S</I> because there is no path from <I>s</I> to <I>T</I> in <I>G</I><SUB>&acirc;</SUB>. For each pair of vertices <I>u</I> and <I>v</I> such that <I>u</I> <img src="../images/memof12.gif"> <I>S</I> and <I>v</I> <img src="../images/memof12.gif"> <I>T</I>, we have &acirc;(<I>u</I>, <I>v</I>) = <I>c</I>(<I>u</I>, <I>v</I>), since otherwise (<I>u</I>, <I>v</I>) <img src="../images/memof12.gif"> <I>E</I><SUB>&acirc;</SUB> and <I>v</I> is in set <I>S</I>. By Lemma 27.5, therefore, | &acirc; | = &acirc;(<I>S</I>, <I>T</I>) = <I>c</I>(<I>S</I>, <I>T</I>).<P>
(3) <img src="../images/rtbigar.gif"> (1): By Corollary 27.6, | &acirc; | <img src="../images/lteq12.gif"> <I>c</I>(<I>S</I>, <I>T</I>) for all cuts (<I>S</I>, <I>T</I>). The condition | &acirc; | = <I>c</I>(<I>S</I>, <I>T</I>) thus implies that &acirc; is a maximum flow.      <P>
<P>