Circulation with Demands
What you'll learn: How to model network flow problems where nodes themselves consume or produce resources, not just the source and sink.
The Core Idea
Until now, you've worked with flow networks where only the source supplies flow and only the sink consumes it. But real-world problems often involve intermediate nodes that need resources or produce extras. Think of a supply chain: warehouses need certain inventory amounts, factories produce goods, and distribution centers both receive and ship products.
Circulation with demands extends flow networks by assigning each node a demand value:
- Positive demand (
d(v) > 0): the node needs that much flow delivered - Negative demand (
d(v) < 0): the node supplies that much flow (it's a source of resources) - Zero demand (
d(v) = 0): the node is just a transit point
The goal is to find a valid circulation—a flow that satisfies:
- Capacity constraints on all edges (as usual)
- Flow conservation with demands: for every node
v, the incoming flow minus outgoing flow must equald(v)
Converting to Standard Max Flow
You can solve circulation problems using max flow algorithms! Add a super-source s* and super-sink t*:
- Connect
s*to every node with negative demand (suppliers) with capacity equal to the supply amount - Connect every node with positive demand to
t*with capacity equal to the demand - Run max flow from
s*tot*
If the max flow value equals the total demand (sum of all positive demands), a feasible circulation exists.
Example Analogy
Imagine power stations generating electricity (negative demand) and cities consuming it (positive demand), with transmission lines (edges) having capacity limits. Circulation with demands finds whether you can satisfy all cities without overloading any line.
Key Takeaway: Circulation with demands generalizes flow networks to model real resource distribution where intermediate nodes have supply/demand requirements, solvable by reducing to standard max flow problems.