= Cut of a flow network
A source-to-sink <cut of a flow network> is a <partition of a set> $(S,V\setminus S)$ of the <vertex set> of a <flow network>, with $s\in S$ and $t\notin S$. Its <cut capacity> sums the <flow network edge capacities> of <directed edges> leaving $S$.<Graph Theory by Reinhard Diestel/Flows (author-hosted chapter preview)>[Graph Theory by Reinhard Diestel; Diestel, Flows, §6.2, printed p. 158: source-side partition and cut capacity]{ref}
The side $S$ may contain any selection of the other <vertices>; its <induced subgraph> need not be a <connected graph>. For the five-<edge> <flow network> with <flow network edge capacities> $(c_{sa},c_{sb},c_{ab},c_{at},c_{bt})=(3,2,1,2,3)$, $S=\{s\}$ gives the <partition of a set> $(\{s\},\{a,b,t\})$. Only $s\to a$ and $s\to b$ leave this side, so its <cut capacity> is $3+2=5$. Choosing $S=\{s,b\}$ instead puts $a\to b$ across the boundary in the incoming direction: its <flow network edge capacity> is excluded.
\Image[/network-flow-directed-cut-certificate.png]
{title=Forward <cut capacity> bounds net <flow>, with backward <flow> subtracted}
The left panel pairs a <feasible flow> of <flow value> $5$ with a <cut of a flow network> of <cut capacity> $5$, proving that each is optimal. The right panel uses the same <feasible flow> but a different <cut of a flow network>: the outward <flow> is $3+3=6$ and the backward <flow> is $1$, giving net <flow> $6-1=5$. That <cut capacity> is $6$, so it supplies a valid but less sharp bound. The dashed boundary marks a <partition of a set>, rather than an additional <edge> or a proposed route.
Back to article page
