Max-flow algorithms can be applied to determine the elimination of sports teams in a group. Consider the following record for a group of five teams. Note that the number of remaining games for a team does not necessarily equal the number of remaining games against the group's rivals, as teams may play opponents outside their own group. Only the team with the highest number of wins will advance to the next round. Our goal is to determine whether team E has already been eliminated.
The intuition behind constructing the graph is to assume that team E wins all of its remaining 28 () games, and then attempt to ensure that the number of wins for each competing team does not exceed the total possible wins of team E (). The constructed graph consists of 12 nodes: in addition to the source () and sink () nodes, there are six nodes representing the head-to-head games between teams A-D and four nodes representing teams A-D. What is the maximum flow value of the constructed graph?
| Team | Wins () | Losses () | To play () | team A | team B | team C | team D | team E |
|---|---|---|---|---|---|---|---|---|
| team A | 75 | 59 | 28 | - | 5 | 7 | 4 | 3 |
| team B | 71 | 63 | 28 | 5 | - | 2 | 4 | 4 |
| team C | 69 | 65 | 28 | 7 | 2 | - | 4 | 0 |
| team D | 63 | 71 | 28 | 4 | 4 | 4 | - | 0 |
| team E | 48 | 86 | 28 | 3 | 4 | 0 | 0 | - |