Let be a directed graph and each edge has a capacity . There are two special vertices referred to as the source and the sink respectively. A flow is a vector in such that for every edge . Recall that the value of the flow .
Recall that the maximum flow is always less than or equal to the capacity of the minimum cut. Let be a cut in the graph such that . Then we have:
Theorem: For every graph and capacity , the value of the maximum flow is equal to the capacity of the minimum cut.
Proof: We need the following definition.
Augmenting Path: An to path is called an augmenting path if for every forward edge we must have while for every backward edge we must have . The idea is that we can route more flow from to via by increasing the flow on the forward edges and decreasing the flow on the backward edges. Note that the amount of flow we can send is the minimum of for every forward edge and for every backward edge .
Note that if is a maximum flow then clearly there cannot be any augmenting paths in . Let us define the set . Note that for every forward edge coming out of we must have while for every backward edge coming into we must have . Thus .
Residual Graph: For every edge such that the flow we set the capacity while the capacity of . Define the residual graph to be the graph on the same set of vertices as and consisting of edges such that . Note that by definition any augmenting path in is a directed path in the residual graph . Thus finding an augmenting path reduces to finding a directed path in .
Choice of augmenting path
- One could choose the maximum (residual) capacity augmenting path from . The capacity of a path is defined as the minimum of the residual capacity of the edges in the path.
- Alternatively we could also pick the shortest (number of edges) path in .
Claim: Given a flow and optimal flow in then there exists a path in the residual graph of and such that its capacity is at least .
Proof: Observe that in every step the difference becomes at least of the initial value. Suppose the original capacities are integral then we can only halve till where is the largest capacity edge in . Thus the running time is . Note that this is polynomial in the size of the input since we need only bits to write down the capacities of all the edges. There is a strongly polynomial algorithm that depends only on and not on the capacity.