CompSci 163/265, Spring 2016, Homework 5

The following flow network, with source at $s$ and destination at $t$, comes from the Spring 2015 midterm.

  1. Show the steps of the Ford–Fulkerson algorithm for finding a maximum flow in this network, using flow augmentations along the widest path of the residual graph. For each step, show the residual graph, its widest path, and new flow after using the path.

  2. How does the minimum cut in this network split the vertices? And what is the capacity of the cut?

  3. Suppose that, near the end of baseball season, we are trying to determine whether the Angels have been mathematically eliminated. The other teams they are competing against are the Astros, Athletics, Mariners, and Rangers. If the Angels win all their remaining games, they can afford to let the Astros and Mariners win two games each, and the Athletics and Rangers win one game each. Each pair of the four competing teams will play one more game against each other (six games total), not counting their games against the Angels. Draw a flow network that models the baseball elimination problem for these teams.

  4. Draw or describe a maximum flow for the network you set up in the previous question. You do not have to show your steps. Does this flow show that the Angels are eliminated, or do they still have a scenario for winning? Explain your answer.