Question 2. The final games of the Ivy League Baseball season are approaching and you want to know if your favorite team is going to be eliminated. These are the current standings:

Figure 1: The current standings in the Ivy League Baseball season. The ”left” column is the number of games remaining for each team in the season. g[i][j] corresponds to the number of games remaining betweem team i and team j.

For a team not to be eliminated, it must have the most wins or tied for the most wins. It appears that Columbia can still catch up with Harvard, if they win all their remaining games and Harvard loses all of theirs. But that would also influence the number of games that Cornell, Dartmouth and Princeton would win. The goal of this question is to formulate the problem of figuring out if it still possible for Columbia to not be eliminated as a maximum flow problem. We are going to use this directed graph, based on the Columbia point of view:

a) Copy the graph above in your write-up.

b) Add capacities to the edges from the source s to the games nodes. Give a one sentence interpreation of these capacities.

c) Add capacities to the edges from the games nodes to the teams nodes. Give a one sentence interpreation of these capacities.

d) Add capacities to the edges from the teams nodes to the sink t. Give a one sentence interpreation of these capacities.

e) How can you tell if it is still possible for Columbia to not be eliminated based on the value of the maximum flow for this graph?