The Maximum Flow Minimum Cut Theorem

• Print

Given a network, as shown below, with each number on an arc indicating a capacity, we can cut the network into two in so many different ways.

Each cut will return a maximum flow through the network, equal to the sum of the capacities on the arcs passing from left to right, but not all of these will be possible, because of constraints elsewhere in the network. In fact the maximum flow through the network will be the minimum of the flows return by all the possible cuts.

The cut returns a maximum flow of 3+2=5.

The cut returns a maximum flow of 3-1+3=5.

The cut returns a maximum flow of 2+1+1=4.

he cut returns a flow of 2+1+2+3=-8.

This cut returns a maximum flow of 1+3=4.

This cut returns a maximum flow of 1-2+2=1

This cut returns a maximum flow of 3+2=5

The minimum flow of all these cuts is 1, so this is the maximum flow through the network.