Flow Augmentation

• Print

An initial flow through a network can be found by inspection, and a maximum flow through the network can be found by flow augmentation once this initial flow has been found. We do this by labelling the arcs of a network with their corresponding flows and capacities as shown below.

Each arc is now labelled with an excess capacity, equal to capacity minus flow, and a back capacity, equal to the flow, as shown below.

We can find a flow augmenting path by looking at the capacities.

Along soqt we can increases the flow by 1, but no more since the excess capacity along so and qt are both 1.

Along soprt and sprt the flow cannot be increased at all, since pr has no excess capacity (it is saturated).

Along spoqt there are excess and back capacities of 1 and 4, so the flow can be increased by 1.

Proceeding in this manner, we see that the flow can be increased by 1, along soqt for example, to give the flow below.

We can cut the network as shown. There is no excess capacity across the cut, so the maximum flow is 1+3=4.