Why Residual Capacity Is Useful
A capacity-constrained network records how much flow can travel along each directed arc. Once a feasible flow has been assigned, the original capacities alone do not describe every permitted change: an arc may have unused capacity, and flow already sent along an arc may also be reduced. Residual capacities record both possibilities. The residual network is the directed network of these locally available changes.
Throughout, a network is a finite directed graph with a nonnegative capacity \(c(e)\) on every arc \(e\), together with distinct source \(s\) and sink \(t\). A flow \(f\) is feasible if \(0\le f(e)\le c(e)\) for every arc, and if each vertex other than \(s\) and \(t\) has total inflow equal to total outflow. The value of the flow is its net outflow from \(s\). These are the capacity and conservation conditions used in the earlier material on feasible flows.
The labels identify which original arc gives rise to each residual arc. A reverse residual arc is not necessarily an original arc: it records the possibility of decreasing flow on its associated original arc. If the original network has arcs in both directions between a pair of vertices, residual arcs may also have multiple contributions in one direction. They can be displayed separately with labels, or combined by adding their capacities, provided the labels are retained when interpreting a change.
Why the Two Formulas Are the Right Ones
Proof. Write \(x=f(e)\) and \(c=c(e)\), so feasibility gives \(0\le x\le c\). If the flow on \(e\) is increased by an amount \(a\ge0\), its new value is \(x+a\). The capacity bounds on this arc hold exactly when \(x+a\le c\), or equivalently \(a\le c-x\). Thus the largest permitted increase is \(c-x=c(e)-f(e)\). If the flow is decreased by an amount \(b\ge0\), its new value is \(x-b\). The capacity bounds hold exactly when \(x-b\ge0\), or equivalently \(b\le x\). Thus the largest permitted decrease is \(x=f(e)\). These are local capacity bounds on one arc; changing a single arc alone need not preserve conservation at its endpoints. \(\square\)
Proof. By definition, the forward residual capacity is \(c(e)-f(e)\), which is positive exactly when \(f(e)<c(e)\). The reverse residual capacity is \(f(e)\), which is positive exactly when \(f(e)>0\). The definition of the residual network includes precisely the residual arcs with positive capacity. \(\square\)
Consequently, an arc carrying no flow has no reverse residual arc, while a saturated arc has no forward residual arc. An arc that is neither empty nor saturated gives rise to both. The residual network records available local changes; by itself, it does not assert that any arbitrary collection of such changes preserves flow conservation.
Constructing a Residual Network
Worked Example: A Feasible Flow with Several Residual Arcs
Let the network have \(V=\{s,a,b,t\}\) and original arcs \(s\to a\), \(s\to b\), \(a\to b\), \(a\to t\), and \(b\to t\). Their capacities and flow values are shown below. First check feasibility, then construct the residual network.
| Original arc \(e\) | \(c(e)\) | \(f(e)\) | Forward residual \(c(e)-f(e)\) | Reverse residual \(f(e)\) |
|---|---|---|---|---|
| \(s\to a\) | 5 | 3 | \(5-3=2\) | 3 |
| \(s\to b\) | 4 | 1 | \(4-1=3\) | 1 |
| \(a\to b\) | 2 | 1 | \(2-1=1\) | 1 |
| \(a\to t\) | 2 | 2 | \(2-2=0\) | 2 |
| \(b\to t\) | 5 | 2 | \(5-2=3\) | 2 |
Every flow value is between zero and its capacity: \(0\le3\le5\), \(0\le1\le4\), \(0\le1\le2\), \(0\le2\le2\), and \(0\le2\le5\). At \(a\), the inflow is \(3\) and the outflow is \(1+2=3\). At \(b\), the inflow is \(1+1=2\) and the outflow is \(2\). Thus conservation holds at both intermediate vertices. The source has net outflow \(3+1=4\), and the sink has inflow \(2+2=4\), so the flow value is \(4\).
The residual network contains \(s\to a\) with capacity \(2\) and \(a\to s\) with capacity \(3\); \(s\to b\) with capacity \(3\) and \(b\to s\) with capacity \(1\); \(a\to b\) with capacity \(1\) and \(b\to a\) with capacity \(1\); \(a\to t\) with capacity \(2\); and \(b\to t\) with capacity \(3\) and \(t\to b\) with capacity \(2\). There is no forward residual arc \(a\to t\), because its forward residual capacity is \(2-2=0\).
Check: For each original arc, the two displayed residual capacities add to its original capacity: \(2+3=5\), \(3+1=4\), \(1+1=2\), \(0+2=2\), and \(3+2=5\). This checks every row against the formulas.
The row-by-row construction is systematic: for each original arc, subtract its flow from its capacity to obtain the forward residual capacity, and use its flow itself as the reverse residual capacity. Include only positive results. The residual network may therefore have fewer arcs than the list of all forward and reverse possibilities.
Worked Example: Saturated Arcs and Missing Forward Arcs
Let \(V=\{s,p,q,t\}\), with original arcs \(s\to p\), \(p\to t\), \(p\to q\), \(s\to q\), and \(q\to t\). Assign capacities and flows as follows:
| Arc | Capacity | Flow | Forward residual calculation | Reverse residual |
|---|---|---|---|---|
| \(s\to p\) | 4 | 4 | \(4-4=0\) | 4 |
| \(p\to t\) | 3 | 2 | \(3-2=1\) | 2 |
| \(p\to q\) | 2 | 2 | \(2-2=0\) | 2 |
| \(s\to q\) | 2 | 1 | \(2-1=1\) | 1 |
| \(q\to t\) | 4 | 3 | \(4-3=1\) | 3 |
To check feasibility, each flow lies in its capacity interval: \(0\le4\le4\), \(0\le2\le3\), \(0\le2\le2\), \(0\le1\le2\), and \(0\le3\le4\). Vertex \(p\) receives \(4\) and sends \(2+2=4\). Vertex \(q\) receives \(1+2=3\) and sends \(3\). The source sends \(4+1=5\), and the sink receives \(2+3=5\), so the flow value is \(5\).
The positive residual arcs are \(p\to s\) with capacity \(4\); \(p\to t\) with capacity \(1\) and \(t\to p\) with capacity \(2\); \(q\to p\) with capacity \(2\); \(s\to q\) with capacity \(1\) and \(q\to s\) with capacity \(1\); and \(q\to t\) with capacity \(1\) and \(t\to q\) with capacity \(3\). The original arcs \(s\to p\) and \(p\to q\) are saturated, so their forward residual capacities are both zero and they do not appear as forward residual arcs.
Check: The residual capacities for \(s\to p\) add to \(0+4=4\), and those for \(p\to q\) add to \(0+2=2\), matching their original capacities. For the other arcs the checks are \(1+2=3\), \(1+1=2\), and \(1+3=4\), also matching their capacities.
Opposite Arcs in the Original Network
When the original network already has an arc from \(v\) to \(u\) as well as one from \(u\) to \(v\), labels matter. The forward residual contribution from the first original arc and the reverse residual contribution from the second both point from \(u\) to \(v\), but they come from different original arcs. Adding their capacities gives the total capacity in that direction if a combined display is desired.
Worked Example: Original Arcs in Both Directions
Let \(V=\{s,u,t\}\) and let the original arcs be \(s\to u\), \(u\to s\), \(u\to t\), and \(s\to t\). Give them capacities and flows respectively \(4,2\); \(3,1\); \(2,1\); and \(1,0\).
Check the capacity bounds: \(0\le2\le4\), \(0\le1\le3\), \(0\le1\le2\), and \(0\le0\le1\). At \(u\), inflow is \(2\) from \(s\), while outflow is \(1\) to \(s\) plus \(1\) to \(t\), also \(2\). The source has net outflow \((2+0)-1=1\), because one unit enters \(s\) on \(u\to s\). The sink receives \(1\), so the source and sink balances agree and the flow value is \(1\).
For the original arc \(s\to u\), the forward residual capacity is \(4-2=2\), giving a labelled residual arc \(s\to u\) of capacity \(2\); its reverse residual capacity is \(2\), giving a labelled residual arc \(u\to s\) of capacity \(2\). For the original arc \(u\to s\), the forward residual capacity is \(3-1=2\), giving a second labelled residual arc \(u\to s\) of capacity \(2\); its reverse residual capacity is \(1\), giving a second labelled residual arc \(s\to u\) of capacity \(1\). Thus, when combined, the residual capacity from \(s\) to \(u\) is \(2+1=3\), and from \(u\) to \(s\) it is \(2+2=4\).
For \(u\to t\), the forward residual capacity is \(2-1=1\) and the reverse residual capacity is \(1\), so the residual arcs are \(u\to t\) and \(t\to u\), each of capacity \(1\). For \(s\to t\), the forward residual capacity is \(1-0=1\) and the reverse residual capacity is \(0\), so only \(s\to t\) appears, with capacity \(1\).
Check: The combined residual capacities on the pair are \(3\) from \(s\) to \(u\) and \(4\) from \(u\) to \(s\). These are the sums \(2+1\) and \(2+2\) of the labelled contributions just calculated. Keeping the labels explains which original flow each contribution can change.
Common Mistakes and Why the Residual Network Matters
Mistake: using \(c(e)-f(e)\) for both directions. For an arc of capacity \(5\) carrying flow \(3\), the forward residual capacity is \(5-3=2\), but the reverse residual capacity is \(3\), not \(5-3=2\). The forward direction measures unused capacity; the reverse direction measures how much existing flow can be reduced. Confusing the two can give an incorrect residual network.
Mistake: keeping zero-capacity arcs. If an original arc of capacity \(2\) carries flow \(2\), its forward residual capacity is \(2-2=0\). It is therefore omitted from the residual network, even though the original arc remains in the original network.
Mistake: treating a reverse residual arc as an original arc. The residual arc \(v\to u\) associated with an original arc \(u\to v\) represents a permitted decrease of flow on \(u\to v\). It need not be a separately specified arc in the original network. In a network with opposite original arcs, it is especially important to retain the labels or combine contributions carefully.
Residual networks make the available local changes visible in one directed network. Their construction is a bookkeeping step: check the original flow and capacities, calculate both residual values for every original arc, and include exactly the positive contributions. Later flow methods use this representation to coordinate changes while maintaining conservation; the local bounds defined here are the capacity information those methods require.
Check Your Understanding
For each question, distinguish the original network from its residual network and apply the formulas to the stated arc or flow.
- An original arc has capacity \(7\) and carries flow \(4\). What are its forward and reverse residual capacities, and which labelled residual arcs are included?
- An arc has capacity \(6\) and flow \(0\). Explain why it has a forward residual arc but no reverse residual arc.
- An arc has capacity \(3\) and flow \(3\). Which residual direction is omitted, and why?
- Explain why changing the flow on just one arc by an amount within its residual capacity may still violate flow conservation.
- Suppose original arcs \(u\to v\) and \(v\to u\) both exist. Why should their residual contributions be kept labelled or combined by addition?