This problem is solved on a graph consisting of game and team nodes to determine which teams can still make the playoffs for a given sport.
Finding the largest number of rooks on an m-by-n chessboard with k squares removed such that none of the rooks attack each other can be solved by reducing to this problem. This problem is solved on a graph consisting of game and team nodes to determine which teams can still make the playoffs for a given sport. Algorithms for this problem often use a residual graph with augmenting paths. Edmonds and Karp developed an algorithm for solving this problem that specifies the search order for augmenting paths, thus building on the Ford–Fulkerson method. For 10 points, name this problem on capacitated networks, or graphs whose edges have capacities like pipes, that tries to optimize a source-to-sink quantity that, by a namesake theorem, equals the minimum cut.
Finding the largest number of rooks on an m-by-n chessboard with k squares removed such that none of the rooks attack each other can be solved by reducing to this problem.
maximum flow problem [or minimum cut; accept max-flow min-cut theorem] &lt;Overman&gt;