Capacity Constraints in Flow Networks
What you'll learn: How flow networks enforce limits on how much can travel through each edge.
In a flow network (like water pipes, traffic routes, or data networks), every edge has two fundamental rules that govern how much flow can pass through it. These rules are called capacity constraints.
The Two Rules
Rule 1: Flow Cannot Exceed Capacity
Each edge has a maximum capacity it can handle. Think of a pipe that can carry at most 10 liters per second—you physically cannot push 15 liters through it. In notation, if edge (u, v) has capacity c(u, v) and current flow f(u, v), then:
f(u, v) ≤ c(u, v)
Rule 2: Flow Must Be Non-Negative
You can't have "negative flow" going through an edge in the forward direction. Water doesn't flow backwards through a pipe unless we model it as a separate reverse edge. So:
f(u, v) ≥ 0
Together: 0 ≤ f(u, v) ≤ c(u, v)
Why This Matters
These constraints ensure realistic, physical behavior in your network model. Without them, you could theoretically push infinite flow or have nonsensical negative flows. Every algorithm that finds maximum flow (like Ford-Fulkerson) must respect these constraints at every step.
Analogy
Imagine a highway system where each road has a lane capacity (cars per hour). You can't magically fit 500 cars on a 2-lane road rated for 200 cars—that's the capacity constraint. And you can't have -50 cars driving backwards unless you explicitly model a reverse lane.
Key Takeaway: Capacity constraints ensure that flow on each edge stays between zero and the edge's maximum capacity, making flow networks realistic and solvable.