Separating the Source from the Sink
In a flow network, a cut describes a way to separate the source from the sink by dividing the vertices into two groups. Its capacity measures the total capacity of the arcs directed from the source side to the sink side. This is a property of the network and the chosen partition; it does not depend on how much flow is currently using those arcs.
For clarity, take a finite directed network with distinct source \(s\) and sink \(t\). Each arc \(e\) has a nonnegative capacity \(c(e)\). A feasible flow \(f\) assigns a nonnegative value \(f(e)\) to each arc, with \(f(e)\le c(e)\), and satisfies conservation at every vertex other than \(s\) and \(t\): total flow into that vertex equals total flow out. Arcs are directed; if arcs in both directions occur between two vertices, they are counted separately.
The two sums have different meanings. Capacity adds the limits on forward-crossing arcs. Net flow uses the actual flow values on crossing arcs and subtracts the actual flow in the reverse direction. In particular, an incoming arc can affect net flow but is not included in \(c(S,\overline S)\). The cut capacity is defined even when no feasible flow has been specified.
What the Capacity Counts
To compute a cut capacity, first list the vertices in \(S\) and in \(\overline S\). Then inspect each directed arc. Include its capacity exactly when its tail is in \(S\) and its head is in \(\overline S\). Do not include arcs that stay within either side, or arcs directed from \(\overline S\) into \(S\).
This direction matters. Unlike an undirected edge boundary, the capacity of a directed cut is generally different from the capacity of the same partition with the two sides reversed. The reversed partition also reverses which arcs count. The source side must still contain \(s\), so the reversed partition is not itself an \(s\)-\(t\) cut with the same source and sink.
Proof. The network specifies a capacity \(c(e)\) for each arc \(e\), and the partition specifies whether the tail of \(e\) is in \(S\) and its head is in \(\overline S\). Thus the set of terms in the defining sum is determined by the network and partition alone. No flow value \(f(e)\) appears in that sum. Changing the flow while keeping the network and partition fixed therefore leaves the cut capacity unchanged. \(\square\)
Proof. Feasibility gives \(f(e)\le c(e)\) for every arc. Apply this inequality to each arc directed from \(S\) to \(\overline S\), then add the inequalities over exactly those arcs. The left-hand sum is the forward flow; the right-hand sum is the definition of \(c(S,\overline S)\). If there are no forward-crossing arcs, both sums are empty and equal to zero, so the inequality still holds. \(\square\)
This bound concerns forward flow, not net flow. Net flow subtracts flow in the reverse direction, so it is a different quantity. The cut-capacity definition itself makes no subtraction.
Computing a Cut and Its Net Flow
Worked Example: Forward Capacity, Incoming Flow, and Net Flow
Let the directed network have vertex set \(V=\{s,a,b,t\}\) and arc set \(\{s\to a,s\to b,a\to t,b\to t,a\to b,b\to a\}\). Assign capacities \(c(s\to a)=4\), \(c(s\to b)=3\), \(c(a\to t)=4\), \(c(b\to t)=3\), \(c(a\to b)=2\), and \(c(b\to a)=2\). Consider the cut with \(S=\{s,a\}\) and \(\overline S=\{b,t\}\).
The forward-crossing arcs are \(s\to b\), \(a\to t\), and \(a\to b\). Their capacities are \(3\), \(4\), and \(2\), respectively. Therefore \(c(S,\overline S)=3+4+2=9\). The arc \(b\to a\) crosses in the opposite direction, so its capacity is not added. The arcs \(s\to a\) and \(b\to t\) stay on one side of the partition and are not added.
Now assign flow values \(f(s\to a)=4\), \(f(s\to b)=3\), \(f(a\to t)=4\), \(f(b\to t)=3\), \(f(a\to b)=1\), and \(f(b\to a)=1\). Every value is nonnegative and within its capacity: the six checks are \(4\le4\), \(3\le3\), \(4\le4\), \(3\le3\), \(1\le2\), and \(1\le2\). At \(a\), inflow is \(4+1=5\) and outflow is \(4+1=5\). At \(b\), inflow is \(3+1=4\) and outflow is \(3+1=4\). Thus conservation holds at both intermediate vertices.
Forward flow across the cut is \(f(s\to b)+f(a\to t)+f(a\to b)=3+4+1=8\). Reverse flow is \(f(b\to a)=1\). Hence net flow from \(S\) toward \(\overline S\) is \(8-1=7\). Check: the forward flow \(8\) is at most the capacity \(9\), while net flow \(7\) is smaller than forward flow because one unit crosses in the reverse direction. The capacity remains \(9\); it is not the net flow \(7\).
Worked Example: Reversing Which Arcs Count
Let the directed network have vertex set \(V=\{s,a,t\}\) and arc set \(\{s\to a,a\to t,s\to t,t\to a\}\), with capacities \(c(s\to a)=4\), \(c(a\to t)=3\), \(c(s\to t)=2\), and \(c(t\to a)=7\). For \(S=\{s,a\}\), the forward-crossing arcs are \(a\to t\) and \(s\to t\). Thus \(c(S,\overline S)=3+2=5\), where \(\overline S=\{t\}\). The arc \(t\to a\) points into \(S\), so it is excluded.
Consider instead the same division of the vertices with the sides reversed: \(\{t\}\) and \(\{s,a\}\). The only arc directed from \(\{t\}\) to \(\{s,a\}\) is \(t\to a\), so the capacity in that direction is \(7\). The two directional sums are \(5\) and \(7\), not one shared undirected boundary capacity.
For a feasible-flow check, set \(f(s\to a)=2\), \(f(a\to t)=2\), \(f(s\to t)=1\), and \(f(t\to a)=0\). Each value is within its capacity: \(2\le4\), \(2\le3\), \(1\le2\), and \(0\le7\). At \(a\), inflow is \(2+0=2\), equal to outflow \(2\). The source sends \(2+1=3\) units, and the sink receives \(2+1=3\) units. Across the cut \(S=\{s,a\}\), forward flow is \(2+1=3\), reverse flow is \(0\), and net flow is \(3-0=3\). Check: its capacity is still \(5\), computed from \(3+2=5\); the flow values do not replace the capacity values.
Worked Example: One Cut Capacity with Two Feasible Flows
Let \(V=\{s,a,t\}\), with directed arcs \(s\to a\), \(a\to t\), and \(s\to t\), and capacities \(c(s\to a)=5\), \(c(a\to t)=5\), and \(c(s\to t)=3\). Take \(S=\{s\}\) and \(\overline S=\{a,t\}\). Both arcs leaving \(s\) cross forward, so \(c(S,\overline S)=5+3=8\).
For the first feasible flow, set \(f(s\to a)=2\), \(f(a\to t)=2\), and \(f(s\to t)=1\). The capacity checks are \(2\le5\), \(2\le5\), and \(1\le3\); at \(a\), inflow \(2\) equals outflow \(2\). Forward flow across the cut is \(2+1=3\), and there is no reverse-crossing arc, so net flow is \(3-0=3\).
For a second feasible flow, set \(f(s\to a)=4\), \(f(a\to t)=4\), and \(f(s\to t)=2\). The checks are \(4\le5\), \(4\le5\), and \(2\le3\); at \(a\), inflow \(4\) equals outflow \(4\). Forward flow is \(4+2=6\), and net flow is \(6-0=6\). Check: the cut has capacity \(8\) in both cases because the network and partition have not changed. The actual forward flows, \(3\) and \(6\), differ, and both are at most \(8\).
Common Pitfalls and a Careful Checklist
Wrong calculation: In the first example, one might add the capacities of all arcs crossing the partition in either direction and report \(3+4+2+2=11\). That is not the capacity of the directed cut from \(S\) to \(\overline S\): the final \(2\) is the capacity of \(b\to a\), which points from \(\overline S\) into \(S\). The correct cut capacity is \(3+4+2=9\). The incoming arc does matter when computing net flow, but there its flow value is subtracted: \(8-1=7\).
When you are given a cut and a flow, keep three questions separate:
- Which arcs point from \(S\) to \(\overline S\)? Their capacities sum to \(c(S,\overline S)\).
- How much actual flow uses those forward arcs? Add their \(f(e)\) values.
- How much actual flow returns from \(\overline S\) to \(S\)? Subtract that sum from the forward flow to obtain net flow.
These distinctions prevent two frequent errors: including reverse-directed capacities in the cut capacity, and treating the flow currently sent across a cut as though it were the cut’s capacity. The capacity is fixed once the network and partition are fixed; forward flow and net flow depend on the chosen feasible flow.
Check Your Understanding
For each question, identify the direction of every crossing arc before doing any arithmetic.
- Suppose an \(s\)-\(t\) cut has forward-crossing capacities \(4\) and \(6\), and a reverse-crossing arc of capacity \(5\). What is the cut capacity, and why is the \(5\) excluded?
- For a cut, forward flow is \(7\) and reverse flow is \(2\). What is the net flow in the direction from \(S\) to \(\overline S\)?
- Explain why changing a feasible flow cannot change the capacity of a fixed cut in a fixed network.
- A cut has capacity \(9\). A feasible flow sends \(5\) units forward and \(3\) units backward. Find the net flow and the forward flow, and state which one is bounded by the cut capacity using the proposition proved above.
- Can reversing the sides of a directed partition change the capacity counted in that direction? Give the condition on the crossing arcs that determines the answer.