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

Flow Conservation Constraint

Learn how flow must be conserved at every vertex except source and sink, where incoming equals outgoing flow.

Flow Conservation Constraint

What you'll learn: How flow networks maintain balance at intermediate nodes by ensuring incoming flow equals outgoing flow.


The Core Idea

In a flow network, imagine water flowing through pipes from a source (where water enters) to a sink (where it exits). At every junction or vertex in between, the amount of water flowing in must equal the amount flowing out—nothing magically appears or disappears.

This is the flow conservation constraint: for every vertex except the source and sink, the sum of all incoming flows must equal the sum of all outgoing flows.

Why This Matters

Without flow conservation, you'd have nodes that create or destroy flow out of nowhere. In real applications—like network routing, traffic systems, or supply chains—this would violate physical reality. Resources can't vanish at a router or spontaneously multiply at a warehouse.

The Mathematical Expression

For any vertex v (where v is neither source nor sink):

Σ (flow into v) = Σ (flow out of v)

An Analogy

Think of a busy intersection during rush hour. The number of cars entering the intersection must equal the number leaving it (assuming no parking or crashes). Cars don't pile up forever or disappear—they flow through while conserving quantity.

The source is like a factory producing cars, and the sink is like a parking lot absorbing them. Only at these two special points can the balance tip.

Key Takeaway: Flow conservation ensures that at every intermediate vertex in a flow network, total incoming flow equals total outgoing flow, maintaining balance throughout the network except at the source and sink.