Residual Networks
You'll learn how residual graphs track the remaining capacity for flow adjustments in a network, using forward and backward edges to represent flow potential.
What Is a Residual Network?
A residual network is a transformed version of your original flow network that shows how much more flow you can push along each edge. Think of it like a map showing available "room" for traffic on every road after some cars are already driving.
For every edge in your flow network, the residual network creates:
- Forward edges: Show remaining capacity (original capacity minus current flow)
- Backward edges: Allow you to "undo" flow by redirecting it elsewhere
Why Backward Edges?
Imagine you've sent 5 units of flow from A to B (capacity 10). Later, you realize it would be better to route some through C instead. The backward edge from B to A (with capacity 5) lets you conceptually "cancel" that flow and reroute it—even though real flow only moves forward.
Residual Capacity
The residual capacity c_f(u,v) tells you how much additional flow can traverse an edge:
- If original edge (u→v) has capacity 10 and current flow 7: forward residual = 3
- Simultaneously, backward edge (v→u) gets residual capacity = 7 (the flow you could redirect)
Together, these edges represent all possible flow adjustments: increasing flow forward or decreasing it (via the backward path).
Why It Matters
Residual networks are the foundation of flow algorithms like Ford-Fulkerson. By finding paths with available residual capacity (augmenting paths), you iteratively increase flow until no more improvements are possible.
Key Takeaway: Residual networks use forward edges (remaining capacity) and backward edges (reversible flow) to represent all possible ways to modify flow, forming the basis for maximum flow algorithms.