Editing Maximum flow problem (section)

===Baseball elimination===
[[File:Baseball Elimination Problem.png|thumb|Construction of network flow for baseball elimination problem]]
In the [[baseball]] elimination problem there are ''n'' teams competing in a league. At a specific stage of the league season, ''w''<sub>''i''</sub> is the number of wins and ''r''<sub>''i''</sub> is the number of games left to play for team ''i'' and ''r''<sub>ij</sub> is the number of games left against team ''j''. A team is eliminated if it has no chance to finish the season in the first place. The task of the baseball elimination problem is to determine which teams are eliminated at each point during the season. Schwartz<ref>{{Cite journal | last1 = Schwartz | first1 = B. L. | title = Possible Winners in Partially Completed Tournaments | doi = 10.1137/1008062 | journal = [[SIAM Review]]| jstor = 2028206| volume = 8 | issue = 3 | pages = 302–308 | year = 1966 | bibcode = 1966SIAMR...8..302S }}</ref> proposed a method which reduces this problem to maximum network flow. In this method a network is created to determine whether team ''k'' is eliminated.

Let ''G'' = (''V'', ''E'') be a network with {{math|''s'',''t'' ∈ ''V''}} being the source and the sink respectively. One adds a game node<sub>''ij''</sub> – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node {{math|{{mset|''i'', ''j''}}}} with ''i'' < ''j'' to ''V'', and connects each of them from ''s'' by an edge with capacity ''r''<sub>''ij''</sub> – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node {{math|{{mset|''i'', ''j''}}}} with two team nodes ''i'' and ''j'' to ensure one of them wins. One does not need to restrict the flow value on these edges. Finally, edges are made from team node ''i'' to the sink node ''t'' and the capacity of {{math|''w''<sub>''k''</sub> + ''r''<sub>''k''</sub> – ''w''<sub>''i''</sub>}} is set to prevent team ''i'' from winning more than {{math|''w''<sub>''k''</sub> + ''r''<sub>''k''</sub>}}.
Let ''S'' be the set of all teams participating in the league and let 
:<math>r(S - \{k\}) = \sum_{i,j \in \{S-\{k\}\} \atop i < j} r_{ij}</math>. 
In this method it is claimed team ''k'' is not eliminated if and only if a flow value of size ''r''(''S'' − {''k''}) exists in network ''G''. In the mentioned article it is proved that this flow value is the maximum flow value from ''s'' to ''t''.