Flows in networks

Maximum flow and minimum cut

Each arc has a capacity; flow is conserved at every vertex except the source $S$ and sink $T$. A cut separates $S$ from $T$; its capacity sums the arcs crossing from the $S$ side to the $T$ side. Maximum flow $=$ minimum cut: find a flow and a cut with equal value and both are optimal.