CS 163 / CS 265 Homework 5, due Friday, February 15

1. Draw the flow network representing a baseball elimination problem in which
- We wish to know whether the Angels have been eliminated from the American League West; the other teams in the division are the Astros, A's, Mariners, and Rangers.
- There are six games left for the other teams to play, one for each pair of teams.
- If they win all their remaining games, the Angels can afford to let the Astros win at most three games, the Mariners win at most two games, and the A's and Rangers win at most one game.

(You do not need to find the maximum flow for your network; just show its vertices, edges, and edge capacities.)

2. In the solution to a maximum flow problem, is it always true (for every possible network and every possible maximum flow on that network) that the subset of the edges that have nonzero flow amounts forms a directed acyclic graph? Explain why or find a counterexample.

3. A graph G with source s and destination t has two additional vertices, x and y, and the following five edges:
- s to x with capacity 10
- s to y with capacity 2
- x to y with capacity 3
- y to x with capacity 8
- y to t with capacity 6
What is the minimum s-t cut in this graph, and what is the total capacity across the cut?

4*. Prove that, in the worst case, all augmenting path algorithms for finding maximum flows (no matter how the algorithm chooses which path to augment) may be forced to use a number of paths that is proportional to the square of the number of vertices.