Flow Conservation and Capacity Constraints
What you'll learn: The two fundamental rules that govern how flow behaves in a network.
Every flow network must obey two critical constraints that ensure the flow is both physically meaningful and respects the network's limitations.
Flow Conservation
Flow conservation states that for every intermediate node (any node except the source and sink), the total flow entering the node must equal the total flow leaving it. Think of it like water flowing through a pipe junction: whatever comes in must go out—nothing can magically appear or disappear.
For a node v (where v is neither source s nor sink t):
Sum of incoming flows = Sum of outgoing flows
This prevents flow from accumulating or vanishing at intermediate nodes. The source produces flow, the sink consumes it, but everything in between is just passing it along.
Capacity Constraints
Capacity constraints dictate that the flow on any edge cannot exceed that edge's maximum capacity. Each edge (u, v) has a capacity c(u, v), and the flow f(u, v) must satisfy:
0 ≤ f(u, v) ≤ c(u, v)
Imagine roads with weight limits: you can't send more traffic than the road can handle. The lower bound ensures non-negative flow (though some formulations allow negative flow for theoretical purposes, standard max-flow requires non-negativity).
Why Both Matter
These constraints work together: capacity limits how much can flow through individual edges, while conservation ensures the overall network behaves coherently. Without conservation, you could have "leaks" in your network. Without capacity constraints, edges could be overloaded beyond their physical limits.
Key Takeaway: Flow conservation ensures flow is balanced at intermediate nodes (in = out), while capacity constraints ensure no edge carries more flow than its maximum capacity allows—together they define what makes a flow "valid."