Course contentsShow
← Computer Science
Lesson 1024 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Capacity Constraints

Understand how flow on each edge cannot exceed its capacity and must be non-negative.

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.