Introduction to Algorithms, Third Edition

Exercises
26.2-1
Prove that the summations in equation (26.6) equal the summations in equa-
tion (26.7).
26.2-2
In Figure 26.1(b), what is the flow across the cut
.
f
s; 
2
; 
4
g
;
f
1
; 
3
; t
g
/
? What is
the capacity of this cut?
26.2-3
Show the execution of the Edmonds-Karp algorithm on the flow network of Fig-
ure 26.1(a).
26.2-4
In the example of Figure 26.6, what is the minimum cut corresponding to the max-
imum flow shown? Of the augmenting paths appearing in the example, which one
cancels flow?
26.2-5
Recall that the construction in Section 26.1 that converts a flow network with mul-
tiple sources and sinks into a single-source, single-sink network adds edges with
infinite capacity. Prove that any flow in the resulting network has a finite value
if the edges of the original network with multiple sources and sinks have finite
capacity.
26.2-6
Suppose that each source
s
i
in a flow network with multiple sources and sinks
produces exactly
p
i
units of flow, so that
P
2
V
f .s
i
; /
D
p
i
. Suppose also
that each sink
t
j
consumes exactly
q
j
units, so that
P
2
V
f .; t
j
/
D
q
j
, where
P
i
p
i
D
P
j
q
j
. Show how to convert the problem of finding a flow
f
that obeys

---

26.2
The Ford-Fulkerson method
731
these additional constraints into the problem of finding a maximum flow in a single-
source, single-sink flow network.