Max-flow min-cut
- Algorithms course
- Expert
- Lesson 28/41
- 4 min
Max-flow min-cut theorem.
Max-flow min-cut
The max-flow min-cut theorem states that in a flow network, the maximum flow equals the minimum capacity of any cut that partitions the nodes.
A cut partitions the nodes into S and T, with the source in S and the sink in T. The cut capacity is the sum of capacities of edges going from S to T.
This theorem links flow problems to cut problems; it has many practical applications.
Finding the cut
After computing the maximum flow, the minimum cut is easy to find. All nodes reachable from the source in the residual graph form the set S; the rest form T.
The original edges going from S to T give the minimum cut. These edges are fully saturated in the maximum flow.
This construction also provides a constructive proof of the theorem.
Practice cut_capacity function
Write cut_capacity(capacity, s_set). capacity is an edge list (u, v, c); return the total capacity of edges going from set S to set T. Print 5 with print(cut_capacity([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3)], {'s'})).
Starter code
def cut_capacity(capacity, s_set):
# Cut capacity from S to TSample solution
def cut_capacity(capacity, s_set):
# Cut capacity from S to T
total = 0
for u, v, c in capacity:
if u in s_set and v not in s_set:
total += c
return total
print(cut_capacity([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3)], {'s'}))Expected output
5
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is the maximum flow equal to?
max_flow = min_cut_capacity- The minimum cut capacity Correct answer
- The total number of edges
- The longest path
- The source degree
Explanation: Maximum flow equals the minimum cut capacity.
2 cut capacity
total = 0
for u, v, c in capacity:
if u in s_set and v not in ____:
total += ctotal = 0
for u, v, c in capacity:
if u in s_set and v not in s_set:
total += cExplanation: Edges going from S to T are summed.
3 Max-flow min-cut concepts
| Term | Meaning |
|---|---|
maximum flow |
Minimum cut |
S set |
Source side |
T set |
Sink side |
cut edge |
Fully saturated |