6. Network Flows¶
6.1. Theory¶
An elegant implementation of the max flow problem Algorithms.
6.2. Exercises¶
6.2.1. Maximum Flow: Ford-Fulkerson Algorithm¶
Given the network below:
Formulate the Maximum Flow problem as a linear program.
Transform the network in order to have only one source and one sink but the same maximum flow.
Apply the Ford-Fulkerson algorithm, using augmenting paths and residual graphs.
Give the minimum cut associated to the final maximal flow you obtained.
Illustrate the execution of the Ford-Fulkerson algorithm with scaling.
6.2.2. Maximum Flow: Variants¶
Transform the maximum flow problem with exact node demands shown below in a maximum flow problem.
Transform the maximum flow problem with minimum edge demands shown below in a maximum flow problem.