Cuts in Flow Networks
What you'll learn: How to define cuts that separate the source from the sink in a flow network, and what cut capacity means.
What Is a Cut?
In a flow network, an s-t cut (or simply "cut") is a partition of all vertices into two disjoint sets: one containing the source s and the other containing the sink t. Think of it like drawing a line through your network graph that separates the starting point from the ending point—vertices on one side can't directly reach the other without crossing the cut.
Formally, a cut (S, T) divides the vertex set V into two parts where:
- S contains the source s
- T contains the sink t
- S ∪ T = V and S ∩ T = ∅
Cut Capacity
The capacity of a cut is the sum of capacities of all edges going from S to T (crossing the cut in the forward direction). Notice we only count edges going forward across the cut, not backward.
Capacity(S, T) = Σ capacity(u, v) for all edges where u ∈ S and v ∈ T
Why This Matters
Cuts help us reason about maximum flow. Imagine a cut as a "bottleneck barrier"—no matter how you route flow from source to sink, it must pass through this barrier. The cut's capacity represents the maximum amount of flow that could possibly cross it. Some cuts are tighter bottlenecks than others; the one with minimum capacity tells you the theoretical limit of your entire network's flow.
Key Takeaway: An s-t cut partitions vertices into two sets separating source from sink, and its capacity is the sum of forward edge capacities crossing the partition—representing a bottleneck constraint on total flow.