Max-flow min-cut

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.

Exercise 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'})).

Show example 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'}))

Test yourself

What is the maximum flow equal to?
```
max_flow = min_cut_capacity
```
- The minimum cut capacity
- The total number of edges
- The longest path
- The source degree
Show answer

The minimum cut capacity — Maximum flow equals the minimum cut capacity.

cut capacity

total = 0
for u, v, c in capacity:
    if u in s_set and v not in ____:
        total += c

Show answer

total = 0
for u, v, c in capacity:
    if u in s_set and v not in s_set:
        total += c

Max-flow min-cut concepts

maximum flow

Minimum cut
S set

Source side
T set

Sink side
cut edge

Fully saturated

Next lesson: Bipartite matching

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies