Flows and Connectivity · Flows

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

How to find the maximum flow? Let's at least try something to start with: begin with zero flow and, as long as possible, find a path from \(s\) to \(t\) and increase the flow along the edges of this path as much as possible. It turns out that even this simple approach finds the optimal flow in networks with integer capacities (though in practice it may run slowly if the capacities are large).

Consider the following toy network as an example.

The maximum flow in it is two: you can send one unit of liquid along the upper and lower paths. But what if our algorithm chooses the path \(s \to a \to b \to t\) on the very first step? Along it we send one unit of flow and at the same time both the upper and lower paths get blocked.

However, note that new paths can go against the existing flow, thus reducing it. For example, the path \(s\to b \to a \to t\) goes from \(b\) to \(a\), which actually means stopping the flow from \(a\) to \(b\).

In the general case, our algorithm looks for a path from \(s\) to \(t\), composed of edges \((u,v)\) of two types:

  1. Edge \((u,v)\) exists in the original network but not all its capacity is used.
  2. The reverse edge \((v,u)\) exists in the original network, and there is nonzero flow along it.
In the first case, we can additionally send \(c(u,v) - f(u,v)\) units along edge \((u,v)\) (where \(f\) is the current flow), and in the second case \(f(v,u)\) units (reducing fully or partially the existing flow along edge \((v,u)\)). We can say that we have a residual network \(G^{f} = (V,E^{f})\). For all \(u \neq v \in V\) define the residual capacity: \[c^{f}(u,v)=(c(u,v)-f(u,v))+f(v,u) \ .\] We assume that only those edges enter the residual network whose residual capacity is positive: \[E^{f}=\{(u,v) \colon c^{f}(u,v) > 0\} \ .\]