= Diagonal cut in a nearest-neighbour lattice flow
{title2=$c(S)=2m$}
On $\{0,\ldots,m\}^2$, give an adjacent edge capacity equal to the larger endpoint distance $|i_1-i_2|$ from the diagonal. The set $S=\{i_1<i_2\}$ has $2m$ outgoing edges: two at each interior diagonal vertex and one at each endpoint. Every such edge has capacity one. Thus any <flow> from above to below the diagonal is at most $2m$; a feasible path decomposition attaining this value certifies optimality by <weak duality>.
Back to article page
