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:

  1. Formulate the Maximum Flow problem as a linear program.

  2. Transform the network in order to have only one source and one sink but the same maximum flow.

  3. Apply the Ford-Fulkerson algorithm, using augmenting paths and residual graphs.

  4. Give the minimum cut associated to the final maximal flow you obtained.

  5. Illustrate the execution of the Ford-Fulkerson algorithm with scaling.

../_images/network1.png

A network with multiple sources and sinks.

6.2.2. Maximum Flow: Variants

  1. Transform the maximum flow problem with exact node demands shown below in a maximum flow problem.

../_images/network2.png

A network with node demands.

  1. Transform the maximum flow problem with minimum edge demands shown below in a maximum flow problem.

../_images/network3.png

A network with minimum edge demands.