Tutorial 10, Design and Analysis of Algorithms, 2025
1. Suppose you are given a directed graph G = (V ; E ), with a positive integer capacity
ce on each edge e, a designated source s 2 V , and a designated sink t 2 V . You are
also given an integer maximum s t ow in G, de ned by a ow value fe on each
edge e. Now suppose we pick a speci c edge e 2 E and increase its capacity by
one unit. Show how to nd a maximum ow in the resulting capacitated graph
in time O(m + n), where m is the number of edges in G and n is the number of
nodes.
2. Using the Ford-Fulkerson Algorithm, solve the Bipartite Matching Problem
for the instance of the graph given by the following adjacency matrix:
2 3
6
0 0 0 1 1 17
6
6 0 0 0 1 1 177
6
6 7
6 0 0 0 1 1 177
6
6 1 1 1 0 0 0777
6
6
41 1 1 0 0 075
1 1 1 0 0 0
3. Figure 1 shows a ow network on which an s t ow has been computed. The
capacity of each edge appears as a label next to the edge, and the numbers
in boxes give the amount of ow sent on each edge. (Edges without boxed
numbers speci cally, the four edges of capacity 3 have no ow being sent on
them.) What is the value of this ow? Is this a maximum (s; t) ow in this graph?
If not, nd the maximum ow and also its value for the ow network in Figure 1
using the Ford-Fulkerson Algorithm.
Figure 1: Flow graph for question 3. What is the value of the depicted ow? Is it a maximum ow?
1
4. Decide whether you think the following statement is true or false. If it is true,
give a short explanation. If it is false, give a counterexample.
Let G be an arbitrary ow network, with a source s, a sink t, and a positive
integer capacity ce on every edge e. If f is a maximum s t ow in G, then
f saturates every edge out of s with ow (i.e., for all edges e out of s, we
have f (e) = ce ).
5. Decide whether you think the following statement is true or false. If it is true,
give a short explanation. If it is false, give a counterexample.
Let G be an arbitrary ow network, with a source s, a sink t, and a positive
integer capacity ce on every edge e; and let (A; B ) be a mimimum s t cut
with respect to these capacities ce : e 2 E . Now suppose we add 1 to every
capacity; then (A; B ) is still a minimum s t cut with respect to these new
capacities 1 + ce : e 2 E .
6. For the following directed graph (Figure 2), nd the maximum number of edge
disjoint s t paths using the Ford-Fulkerson Algorithm.
Figure 2: Graph for question 6.
7. Given the transport network as
f( S; a; 4; 3); (S; b; 7; 2); (a; c; 5; 2); (a; D; 3; 1); (b; d; 2; 1); (b; D; 1; 1); (c; D; 2; 2); (d; D; 1; 1) g
where S = Source node, D = Sink (Destination) node, and a; b; c, and d are four
nodes, and the ordered-tuple (x; y; m; f ) denotes that for the directed edge (x; y )
the maximum capacity is m but ow is f . Find two di erent maximal ows and
value of each of these ows.
8. Using the Ford-Fulkerson Algorithm, solve the Bipartite Matching Problem
for the instance of the graph given in Figure 3.
2
Figure 3: Figure for question 8.
Figure 4: Figure for question 9.
9. For the following directed graph (Figure 4), nd the maximum number of edge
disjoint s t paths using the Ford-Fulkerson's algorithm.
10. For the following network (Figure 5), with edge capacities as shown, nd the
maximum ow from S to T, along with a matching cut.
3
Figure 5: Flow network for question 10.
