Maximum flow and minimum cut problem, Ford–Fulkerson algorithm
algorithmMaximum flow problem
Maximum flow promlem is a problem that maximizes the flow from the source to the sink in the network consisting of paths with capacity. It is necessary not to exceed the capacity and to equal input and output amount for each node. Besides, all of the data emitted from the source must be sent to the sink.
Minimum cut problem
Minimum cut problem is a problem that minimizes capacity of cut that divides the source and the sink. Cut (S,V\S) is a set of outgoing paths of the nodes’ subset S⊆V and cut capacity is the total capacity of the edges.
Ford–Fulkerson algorithm
if there are paths from the source to the sink, it increases the flow as much as possible and adds inverse paths with capacity same as the value having increased. Repeat this until there are no more paths. The graph of paths with remaining capacity is called a residual graph.
If maximum flow is F, time complexity is O(F|E|) but it is unlikely that the maximum flow can be updated only one by one, so it is not so slow.
Proof
Let S be a subset of the nodes reachable from the source and V be a residual graph that the algorithm is completed. (S,V\S) is a cut dividing the source and the sink. V doesn’t contain paths from the source to the sink so capacity of the paths from S to V\S is used completely and paths from V\S to S is not used. Flow can’t be bigger than the cut capacity so this is the maximum flow.
And a match between the maximum flow and the minimum cut is also derived. This is Max-flow min-cut theorem and it can be said that minimum cut is the bottleneck.
