15-451 MINI #4: due midnight Nov 2, 2004.

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.

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

   Just to be clear: cap(s,a)=3; cap(a,b)=6; cap(s,c)=3; cap(d,a)=2;
   cap(b,t)=4; cap(c,d)=5; cap(d,t)=2.


2. One naive algorithm for solving bipartite matching is to do what's
called "chronological backtracking".  You look at the nodes on the
left-hand-side one at a time: for each node, take the first (highest)
available edge and recursively solve the rest of the problem.  If the
recursion returns failure, then try a different edge. If all edges
fail, then return failure.

Describe an n-by-n bipartite graph that has a perfect matching, but
where this algorithm would take exponential time to find it.