chap27.htm

介绍算法的书籍

<h4><a name="08f9_18a0">Figure 27.3 Converting a multiple-source, multiple-sink maximum-flow problem into a problem with a single source and a single sink. (a) A flow network with five sources S = {s<SUB>1</SUB>, s<SUB>2</SUB>, s<SUB>3</SUB>, s<SUB>4</SUB>, s<SUB>5</SUB>} and three sinks T={t<SUB>1</SUB>, t<SUB>2</SUB>, t<SUB>3</SUB>}. (b) An equivalent single-source, single-sink flow network. We add a supersource s' and an edge with infinite capacity from s' to each of the multiple sources. We also add a supersink t' and an edge with infinite capacity from each of the multiple sinks to t'.<a name="08f9_18a0"></sub></sup></h4><P>
<P>







<h2>Networks with multiple sources and sinks</h2><P>
<a name="08fa_189f"><a name="08fa_18a0"><a name="08fa_18a1">A maximum-flow problem may have several sources and sinks, rather than just one of each. The Lucky Puck Company, for example, might actually have a set of <I>m</I> factories {<I>s</I><SUB>1</SUB><I>, s</I><SUB>2</SUB>, . . . ,<I>s<SUB>m</I></SUB>} and a set of <I>n</I> warehouses {t<SUB>1</SUB><I>, t</I><SUB>2</SUB>, . . . , <I>t<SUB>n</I></SUB>}, as shown in Figure 27.3(a). Fortunately, this problem is no harder than ordinary maximum flow.<P>
<a name="08fa_18a2"><a name="08fa_18a3">We can reduce the problem of determining a maximum flow in a network with multiple sources and multiple sinks to an ordinary maximum-flow problem. Figure 27.3(b) shows how the network from (a) can be converted to an ordinary flow network with only a single source and a single sink. We add a <I><B>supersource</I> </B><I>s</I> and add a directed edge (<I>s, s<SUB>i</I></SUB>) with capacity <I>c</I>(<I>s, s<SUB>i</I></SUB>) = <img src="../images/infin.gif"> for each <I>i </I>= 1, 2, . . . , <I>m</I>. We also create a new <I><B>supersink</I></B><I> t</I> and add a directed edge (<I>t<SUB>j</I></SUB>, <I>t</I>) with capacity <I>c</I>(<I>t<SUB>j</I></SUB>, <I>t</I>) = <img src="../images/infin.gif"> for each <I>i</I> = 1, 2, . . . , <I>n</I>. Intuitively, any flow in the network in (a) corresponds to a flow in the network in (b), and vice versa. The single source <I>s</I> simply provides as much flow as desired for the multiple sources <I>s<SUB>i</I></SUB>, and the single sink <I>t</I> likewise consumes as much flow as desired for the multiple sinks <I>t<SUB>i</I></SUB>. Exercise 27.1-3 asks you to prove formally that the two problems are equivalent.<P>
<P>







<h2>Working with flows</h2><P>
<a name="08fb_18a4"><a name="08fb_18a5">We shall be dealing with several functions (like <I>f</I>) that take as arguments two vertices in a flow network. In this chapter, we shall use an <I><B>implicit summation notation</I></B> in which either argument, or both, may be a <I>set</I> of vertices, with the interpretation that the value denoted is the sum of all possible ways of replacing the arguments with their members. For example, if <I>X </I>and <I>Y</I> are sets of vertices, then<P>
<img src="585_a.gif"><P>
As another example, the flow-conservation constraint can be expressed as the condition that <I>f</I>(<I>u</I>, <I>V</I>) = 0 for all <I>u</I> <img src="../images/memof12.gif"> <I>V</I> -{<I>s</I>, <I>t</I>}. Also, for convenience, we shall typically omit set braces when they would otherwise be used in the implicit summation notation. For example, in the equation <I>f</I>(<I>s</I>, <I>V </I>- <I>s</I>) = <I>f</I>(<I>s</I>, <I>V</I>), the term <I>V</I> - <I>s</I> means the set <I>V</I> - {<I>s</I>}.<P>
The implicit set notation often simplifies equations involving flows. The following lemma, whose proof is left as Exercise 27.1-4, captures several of the most commonly occurring identities that involve flows and the implicit set notation.<P>
<a name="08fb_18a6">Lemma 27.1<a name="08fb_18a6"><P>
Let <I>G </I>= (<I>V</I>, <I>E</I>) be a flow network, and let <I>f</I> be a flow in <I>G</I>. Then, for <I>X </I><img src="../images/rgtubar.gif"> V <I>,</I><P>
<pre><I>f</I>(<I>X</I>, <I>X</I>) = 0 .</sub></sup></pre><P>
For X, Y <img src="../images/rgtubar.gif"> V ,<P>
<pre><I>f</I>(<I>X</I>, <I>Y</I>) = -<I>f</I>(<I>Y</I>, <I>X</I>) .</sub></sup></pre><P>
For <I>X</I>, <I>Y</I>, <I>Z </I><img src="../images/rgtubar.gif"><I> V </I>with <img src="585_b.gif">,<P>
<pre><I>f</I>(<I>X</I> <img src="../images/wideu.gif"> <I>Y</I>, <I>Z</I>) = <I>f</I>(<I>X</I>, <I>Z</I>) + <I>f</I>(<I>Y</I>, <I>Z</I>)</sub></sup></pre><P>
and<P>
<pre><I>f</I>(<I>Z</I>, <I>X </I><img src="../images/wideu.gif"> Y<I>) = </I>f<I>(</I>Z<I>, </I>X<I>) + </I>f<I>(</I>Z<I>, </I>Y<I>) .      </I></sub></sup></pre><P>
As an example of working with the implicit summation notation, we can prove that the value of a flow is the total net flow into the sink; that is,<P>
<pre>|<I>f</I>|<I> </I>= <I>f</I>(<I>V</I>, <I>t</I>) .</sub></sup></pre><P>
<h4><a name="08fb_18a7">(27.3)<a name="08fb_18a7"></sub></sup></h4><P>
This is intuitively true, since all vertices other than the source and sink have a net flow of 0 by flow conservation, and thus the sink is the only other vertex that can have a nonzero net flow to match the source's nonzero net flow. Our formal proof goes as follows:<P>
<pre>|<I>f</I>|  =  <I>f</I>(<I>s</I>, <I>V</I>)                    (by definition)</sub></sup></pre><P>
<pre>=  <I>f</I>(<I>V</I>, <I>V</I>) - <I>f</I>(<I>V</I> - <I>s</I>, <I>V</I>)      (by Lemma 27.1)</sub></sup></pre><P>
<pre>=  <I>f</I>(<I>V</I>, <I>V</I> - s)                (by Lemma 27.1)</sub></sup></pre><P>
<pre>=  <I>f</I>(<I>V</I>, <I>t</I>) + <I>f</I>(<I>V</I>, <I>V</I> - <I>s</I> - <I>t</I>)  (by Lemma 27.1 )</sub></sup></pre><P>
<pre>=  <I>f</I>(<I>V</I>, <I>t</I>)                    (by flow conservation) .</sub></sup></pre><P>
Later in this chapter, we shall generalize this result (Lemma 27.5).<P>
<P>







<h2><a name="08fc_18ae">Exercises<a name="08fc_18ae"></h2><P>
<a name="08fc_18af">27.1-1<a name="08fc_18af"><P>
Given vertices <I>u</I> and <I>v</I> in a flow network, where <I>c</I>(<I>u</I>, <I>v</I>) = 5 and <I>c</I>(<I>v</I>, <I>u</I>) = 8, suppose that 3 units of flow are shipped from <I>u</I> to <I>v</I> and 4 units are shipped from <I>v</I> to <I>u</I>. What is the net flow from <I>u</I> to <I>v</I>? Draw the situation in the style of Figure 27.2.<P>
<a name="08fc_18b0">27.1-2<a name="08fc_18b0"><P>
Verify each of the three flow properties for the flow <I>f</I> shown in Figure 27.1(b).<P>
<a name="08fc_18b1">27.1-3<a name="08fc_18b1"><P>
Extend the flow properties and definitions to the multiple-source, multiple-sink problem. Show that any flow in a multiple-source, multiple-sink flow network corresponds to a flow of identical value in the single-source, single-sink network obtained by adding a supersource and a supersink, and vice versa.<P>
<a name="08fc_18b2">27.1-4<a name="08fc_18b2"><P>
Prove Lemma 27.1.<P>
<a name="08fc_18b3">27.1-5<a name="08fc_18b3"><P>
For the flow network <I>G</I> = (<I>V</I>, <I>E</I>) and flow <I>f</I> shown in Figure 27.1(b), find a pair of subsets <I>X</I>, <I>Y</I> <img src="../images/rgtubar.gif"> <I>V </I>for which <I>f</I>(<I>X</I>, <I>Y</I>) = -<I>f</I>(<I>V</I> - <I>X</I>, <I>Y</I>). Then, find a pair of subsets <I>X</I>, <I>Y </I><img src="../images/rgtubar.gif"> V <I>for which </I>f<I>(</I>X<I>, </I>Y<I>) <img src="../images/noteq.gif"> - </I>f<I>(</I>V<I> - </I>X<I>, </I>Y<I>).</I><P>
<a name="08fc_18b4">27.1-6<a name="08fc_18b4"><P>
<a name="08fc_18a6"><a name="08fc_18a7">Given a flow network <I>G</I> = (<I>V</I>, <I>E</I>), let <I>f</I><SUB>1</SUB> and <I>f</I><SUB>2</SUB> be functions from <I>V</I> X <I>V </I>to <B>R</B>. The <I><B>flow sum</I></B> <I>f</I><SUB>1</SUB> + <I>f</I><SUB>2</SUB> is the function from <I>V</I> x <I>V </I>to <B>R</B> defined by<P>
<pre>(<I>f</I><SUB>1</SUB> + <I>f</I><SUB>2</SUB>)(<I>u</I>, <I>v</I>) = <I>f</I><SUB>1</SUB>(<I>u</I>, <I>v</I>) + <I>f</I><SUB>2</SUB>(<I>u</I>, <I>v</I>)</sub></sup></pre><P>
<h4><a name="08fc_18b5">(27.4)<a name="08fc_18b5"></sub></sup></h4><P>
for all <I>u</I>, <I>v</I> <img src="../images/memof12.gif"> <I>V</I>. If <I>f</I><SUB>1</SUB> and <I>f</I><SUB>2</SUB> are flows in <I>G</I>, which of the three flow properties must the flow sum <I>f</I><SUB>1</SUB> + <I>f</I><SUB>2</SUB> satisfy, and which might it violate?<P>