Maximum Flow and Minimum Cut Problem

Problem: Given a network that contains a single source and a single sink, find the maximum (aggregated) flow from the source to the sink. This is Maximum Flow problem.

Solution: The solution is as follow:

1. find a flow in which each edge has strictly positive capacity. Then find the bottleneck edge in the flow. Subtract each edge's capacity with the bottleneck edge's capacity. 
2. try to find another flow in which each edge has strictly positive capacity. Repeat step 1.
3. if such flow cannot be found, terminate. The maximum flow is the sum of all the capacity of the bottleneck edge of the flow processed. 

Minimum Cut problem is from Maximum Flow problem. Basically, first run maximum flow algorithm to find those bottleneck edges. Then the minimum cut is from those edges.

More: Maximum flow (minimum cut) is frequently used in the problem related to flow network. Some other problem which can be solved by (or converted to) maximum flow problem are maximum matching in bipartie graph, minimum path cover, etc.

See Also: Maximum Flow and Minimum Cut