15-451 MINI #4: due 11:59pm Nov 1, 2011. 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 5 S------->a-------->T | ^ ^ | | | |7 |3 |6 | | | v 6 | 4 | 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.