Max-flow min-cut theorem
As a consequence of this theorem, every max flow algorithm may be employed to solve the minimum s-t cut problem, and vice versa.
Statement of the theorem
To every weighted s-t graph we can associate a corresponding flow network in which if , and otherwise. That is, the edges of the flow network are the same as the edges of the weighted s-t graph, with weights replaced by capacities.
Let be a maximum flow in a flow network . Consider the set consisting of vertices reachable from in the residual network corresponding to . A minimum s-t cut of the corresponding weighted s-t graph is then given by . Furthermore, , that is, the max flow and the cut thus obtained are equal in value.
We will first state and prove two Lemmas.
Let be a flow in a flow network . Suppose we have a set such that and . Then the value of the flow equals the total flow leaving , .
- (by skew symmetry)
- (by flow conservation)
Lemma 1 tells us that we can compute the value of a flow by arbitrarily partitioning the flow network into two sets and , where and , and adding only the flows along edges from to . Intuitively, the conservation of flow implies that the total flow out of must equal the total flow emanating from the source; that flow has to get from to somehow.
Let be a flow in a flow network . Let be an s-t cut in the corresponding weighted s-t graph . Then the value of , , is less than or equal to the total weight of , .
Proof: Since is an s-t cut, in the weighted s-t graph , there is no path from to . We can therefore consider the set of all vertices reachable from in this graph. Note that . Applying Lemma 1, we find that .
The idea behind Lemma 2 is simple. The value of a flow, which by Lemma 1 equals the total flow along edges out of , cannot exceed the total capacity of such edges, but this is precisely the total weight of those edges in the corresponding weighted s-t graph. Lemma 2 is a useful result in its own right, telling us that every flow's value is less than or equal to every cut's weight.
It suffices to show that . The fact that the cut is minimal then follows immediately from Lemma 2.
Since the flow is maximal, there is no augmenting path in the residual network . Therefore, . Now, for all and , by definition of . Therefore, for all such edges. By Lemma 1, .
In other words, we can solve the minimum s-t cut problem simply by converting all the edge weights to capacities and then finding a maximum flow in the resulting flow network. If we only want the weight of the min cut, we can simply find the value of the max flow, and be done with it. If we want to find the cut explicitly, then it is still straightforward to do so using the residual graph corresponding to the max flow. The "s part" of the s-t cut will consist of vertices reachable from in the residual graph, with the remainder the "t part". The edges we want to cut are the ones from the "s part" to the "t part".