Capacity Planning With Flow Networks

From Supply Limits to a Flow Network

A supply network may have several stages: material leaves a depot, passes through intermediate facilities, and reaches a destination. Each connection has a limit on how much can pass through it. A graph model makes it possible to distinguish two questions: can a proposed delivery plan be carried out, and what is the largest delivery the network can support? The first is checked by capacities and conservation; the second can be certified by comparing a flow with a cut.

Throughout, a network is a finite directed graph with a nonnegative capacity on each arc, a designated source \(s\), and a distinct sink \(t\). For simplicity, assume there are no arcs entering \(s\), no arcs leaving \(t\), and no pair of opposite arcs. Capacities are upper limits, not required amounts. A flow can leave unused capacity. The examples use whole-number capacities; the maximum-flow algorithm proved below assumes all capacities are integers.

A directed \(s\)-\(t\) cut is specified by a set \(S\subseteq V\) with \(s\in S\) and \(t\notin S\). Its capacity is the sum of the capacities of arcs directed from \(S\) to \(V\setminus S\). Arcs directed into \(S\) are not included. A minimum cut is an \(s\)-\(t\) cut of least capacity. Its outgoing arcs indicate a collection of connections that collectively limits delivery.

Why Cuts Bound Every Delivery

Proof. Fix a feasible flow \(f\) and a cut \(S\). Sum, over all vertices in \(S\), the amount of flow leaving each vertex minus the amount entering it. For every vertex in \(S\setminus\{s\}\), this difference is zero by conservation. At \(s\), it is \(|f|\), since no arc enters \(s\). In the sum, flows on arcs whose two endpoints are both in \(S\) cancel: each is counted once as leaving and once as entering. The remaining expression is the flow on arcs directed from \(S\) to \(V\setminus S\), minus the flow on arcs directed from \(V\setminus S\) into \(S\). Thus $$ |f|=\sum_{\substack{uv:\ u\in S\\v\notin S}} f(u,v) -\sum_{\substack{uv:\ u\notin S\\v\in S}} f(u,v). $$ The second sum is nonnegative, and each term in the first sum is at most its arc's capacity. Therefore $$ |f|\le \sum_{\substack{uv:\ u\in S\\v\notin S}} c(u,v), $$ which is the cut capacity. \(\square\)

This proposition gives an upper bound, but it does not by itself show that the bound can be attained. When a feasible flow and a cut have equal value and capacity, respectively, the proposition certifies both that the flow is maximum and that the cut is minimum.

Finding a Maximum Flow by Augmenting Paths

To find a flow systematically, keep track of residual possibilities. If an arc \(uv\) has capacity \(c(u,v)\) and currently carries \(f(u,v)\), its forward residual capacity is \(c(u,v)-f(u,v)\). There is also a reverse residual move \(vu\) of capacity \(f(u,v)\): using it cancels some flow previously sent along \(uv\). A residual \(s\)-\(t\) path is a sequence of such positive-capacity moves from \(s\) to \(t\). Augmenting along it means increasing flow on forward moves and decreasing flow on reverse moves by the same amount, namely the smallest residual capacity on the path.

Proof. Start with zero flow, which satisfies every capacity bound and conservation equation. At any stage, choose a residual \(s\)-\(t\) path and let \(\Delta\) be the least residual capacity on it. Increase flow by \(\Delta\) on each forward move and decrease it by \(\Delta\) on each reverse move. Since \(\Delta\) does not exceed any residual capacity, the updated flow stays within all original capacity bounds. At each internal vertex of the path, one unit of the update enters and one leaves; therefore conservation is preserved. The flow value increases by \(\Delta\). All capacities and flows remain integers, so \(\Delta\) is a positive integer. The flow value is bounded above by the total capacity of arcs leaving \(s\); consequently, only finitely many augmentations can occur.

When the algorithm stops, let \(S\) consist of \(s\) and every vertex reachable from \(s\) by positive-capacity residual moves. There is no residual path to \(t\), so \(t\notin S\). Any original arc \(uv\) directed from \(S\) to \(V\setminus S\) must be saturated: if \(f(u,v)<c(u,v)\), its forward residual move would reach \(v\). Any original arc \(vu\) directed from \(V\setminus S\) into \(S\) must carry zero flow: if \(f(v,u)>0\), its reverse residual move from \(u\in S\) to \(v\notin S\) would reach \(v\). Apply the cut identity in the proposition. The flow on outgoing cut arcs equals their total capacity, and the incoming cut arcs carry zero flow. Hence the flow value equals the capacity of this cut. The proposition says every feasible flow is at most every cut capacity, so this flow is maximum and this cut is minimum. \(\square\)

Reading the Bottleneck in a Capacity Plan

Common Pitfall: Counting the Wrong Arcs

A cut counts only arcs directed out of \(S\), not every arc with one endpoint on each side. For the cut \(S=\{s,a\}\) in the last example, the edge \(ab\) leaves \(S\), so its capacity 3 is counted. The arc \(sa\) stays inside \(S\), so its capacity 8 is not counted. The outgoing cut arcs are \(sb,ab,at\), giving \(4+3+2=9\). A wrong calculation that adds \(sa\) as well gives \(8+4+3+2=17\); that is not the capacity of this cut. Also, a flow value is not the sum of all arc flows: internal flow can be counted repeatedly by that sum. Compute the value at the source, then check conservation at intermediate vertices.

In a practical plan, a minimum cut identifies a set of connections whose combined capacity limits end-to-end throughput. Increasing capacity elsewhere cannot raise the maximum beyond that cut's capacity. To justify a proposed maximum, however, give both pieces of evidence: a feasible flow attaining the amount and a cut with the same capacity.