15-451 MINI #4: due 11:59pm Oct 27, 2009.
1. (a) What is the maximum s-t flow in the graph G below?
(b) Draw the residual graph you get at the very end of running the
Ford-Fulkerson algorithm on this graph. Remember to include
the back-edges.
3 7
S------->a-------->T
| ^ ^
| | |
|7 |3 |4
| | |
v 6 | 2 |
b------->c-------->d
2. Suppose we use the Ford-Fulkerson algorithm to solve a Maximum
Bipartite Matching problem. The very first path P found will
necessarily have only 3 edges in it (from S to some node on the
left, to some node on the right, to T). But, it is possible for later
iterations to find paths of more than 3 edges. E.g., in the
example in class on Tuesday, the last path found had 5 edges. Give
an example of a bipartite graph where it is possible for one of the
paths found to use 7 edges.