Network-flow linear programs

Assign each directed arc a column with minus one at its tail and plus one at its head. Then $Af=b$ means inflow minus outflow equals $b_v$ at each vertex. A positive $b_v$ is demand and a negative one is supply. For a connected graph the incidence rows sum to zero, so total demand must equal total supply; one row is redundant. This necessary balance is not sufficient for feasibility, since arc directions and capacities may prevent delivery. Include bounds $0\le f_e\le u_e$ and a linear transportation objective $c^Tf$.

The incidence matrix is TU, and adding upper-bound and nonnegativity rows preserves that property. Integral supplies, demands, and finite capacities therefore produce integral vertices of the feasible flow polytope. With finite capacities, the region is bounded; if it is nonempty, a minimum-cost integral vertex exists for any real linear costs. This is an existence statement and does not require every feasible flow to be integral. If capacities are real and nonintegral, the LP remains meaningful but the integer-flow guarantee cannot be asserted from TU alone.

For maximum source-to-sink flow, conserve flow at every other vertex and maximize net flow leaving the source. For a cut $S$ containing the source and excluding the sink, sum conservation over its vertices. Internal arc contributions cancel; the flow value equals flow leaving the cut minus flow entering it. Outgoing flows are at most their capacities and incoming flows are nonnegative, so the cut's outgoing capacity is an upper bound. A feasible flow matching that bound proves optimality immediately, without requiring a description of every augmenting path used to find it.

The max-flow min-cut theorem states that a feasible finite-capacity network has a maximum flow whose value equals the capacity of a minimum source-sink cut. In a residual-network proof, when no augmenting path exists, take the set reachable from the source by positive residual-capacity arcs. Every original arc leaving that set is saturated, and every arc entering it carries zero flow. These conditions make the cut bound tight. Integral capacities allow augmentation in integer amounts, while particular path-selection rules determine the algorithm's complexity; arbitrary augmentations with irrational capacities require extra care and need not terminate.

For a fixed-balance min-cost flow, residual arcs represent feasible marginal adjustments: a forward residual arc has original cost $c_e$, while a backward residual arc has cost $-c_e$ and permits canceling existing flow. A negative-cost residual cycle allows a cost-reducing circulation. For a feasible flow with finite capacities, absence of such cycles characterizes minimum cost. Potentials provide a checkable sufficient certificate: if every residual arc from $v$ to $w$ has reduced cost $c_{vw}+\pi_v-\pi_w\ge0$, every cycle has nonnegative original cost because potential differences telescope.

These potentials resemble shortest-path labels, but their sign must match the chosen reduced-cost convention. Parallel arcs, negative original costs, and saturated arcs all fit the residual formulation. Shared side constraints can break the simple network structure: a bound on the sum of selected unrelated arc flows is not necessarily another ordinary capacity row preserving TU. Multi-commodity flow also couples several conservation systems through shared capacity and generally loses the elementary integral guarantee. A network-shaped picture is therefore not enough; inspect the actual variables and coupling restrictions before choosing a specialized algorithm.