15-451 MINI #4: due midnight Oct 30, 2007.

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.  (There is more than
       one legal answer)

             3         5
         s------->a-------->b
         |        ^         |
         |4       |3        |4
         |        |         |
         v   5    |    2    v
         c------->d-------->t


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, 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 9 edges.