Lesson 4

The Ford–Fulkerson algorithm at each step finds an augmenting path in the residual network and increases the flow along it. As we just proved, this algorithm constructs a maximum flow: if there are no paths from \(s\) to \(t\) in the residual network, the current flow is optimal.

In many applications the edge capacities are integers. Even in such a case, an optimal flow may exist in which some edge flows are not integers. An example is shown below. It’s easy to see that the flow of size one is optimal. Vertex \(c\) receives one unit of flow in total via two paths (\(s \to a \to c\) and \(s \to b \to c\)).

Nevertheless, there exists an integer optimal flow in this network.

It turns out this is always true:

In a network with integer capacities there exists an integer maximum flow.