= Cut capacity
{title2=$c(S,S^c)=\sum_{u\in S,v\notin S}c_{uv}$}
The <cut capacity> of $(S,S^c)$, with $S^c=V\setminus S$ the <complement of a set>, is
$$
c(S,S^c)=\sum_{(u,v)\in E:\,u\in S,\,v\notin S}c_{uv}.
$$
Only outward <directed edges> contribute; incoming and internal <edges> contribute nothing.<Algorithms, 4th edition by Robert Sedgewick and others/FordFulkerson.java>[Algorithms, 4th edition by Robert Sedgewick and others; Sedgewick and Wayne, FordFulkerson.java, check method, lines 196–203: sum capacities only from the source side to its complement]{ref}
Here is the accounting behind the bound, using nonnegative original <edge> amounts $f_{uv}$ in a finite <flow network>. Sum the <divergence of a flow> over the <vertices> in $S$:
$$
\sum_{v\in S}\operatorname{div}f(v)
=\sum_{v\in S}\left(\sum_{w:(v,w)\in E}f_{vw}-\sum_{u:(u,v)\in E}f_{uv}\right).
$$
An <edge> with both endpoints in $S$ appears once with a plus sign at its tail and once with a minus sign at its head, so those contributions cancel. An outward <edge> appears only with a plus sign; an incoming <edge> appears only with a minus sign. Since $s\in S$, $t\notin S$ and every other <vertex> satisfies <flow conservation>, the left side is the <flow value>. Thus
$$
|f|=\sum_{(u,v)\in E:\,u\in S,\,v\notin S}f_{uv}
-\sum_{(u,v)\in E:\,u\notin S,\,v\in S}f_{uv}
\leq\sum_{(u,v)\in E:\,u\in S,\,v\notin S}c_{uv}=c(S,S^c).
$$
The inequality uses two facts separately: each forward <flow> is at most its <flow network edge capacity>, and each backward <flow> is nonnegative. This is the <weak duality> bound underlying the <max-flow min-cut theorem>. It is an accounting proof, requiring no choice of <augmenting paths>.
For $S=\{s,b\}$ in the running example, explicitly add the two <divergences of a flow>:
$$
\operatorname{div}f(s)+\operatorname{div}f(b)
=(f_{sa}+f_{sb})+(f_{bt}-f_{sb}-f_{ab})
=f_{sa}+f_{bt}-f_{ab}=3+3-1=5.
$$
The internal $s\to b$ <edge> cancels. The $a\to b$ <edge> is a genuine original <directed edge> entering $S$, so its <flow> is subtracted; this is different from a backward <edge> in a <residual network>. Its <flow network edge capacity> is neither added to nor subtracted from <cut capacity>, which remains $c_{sa}+c_{bt}=6$.
Equality in the bound holds precisely when every outward <edge> is saturated and every incoming <edge> carries zero <flow>, because
$$
c(S,S^c)-|f|
=\sum_{(u,v)\in E:\,u\in S,\,v\notin S}(c_{uv}-f_{uv})
+\sum_{(u,v)\in E:\,u\notin S,\,v\in S}f_{uv},
$$
and every term is nonnegative. For $S=\{s\}$ the two outward <edges> are saturated and there are no incoming <edges>, so the gap is zero. For $S=\{s,b\}$ all outward <edges> are still saturated, but the incoming <flow> of $1$ gives a gap of $1$. This explains exactly why the second <cut of a flow network> is not a <minimum cut>.
Back to article page
