Lesson 1 of 7 · 14 min
Flow networks: sources, sinks and capacities
Read a flow network — its source, sink and edge capacities — find the most that can flow along a single path, and use the rule that flow in equals flow out at every junction.
What you will be able to do
- Identify the source, the sink and the capacity of each edge of a flow network.
- Find the largest flow that can travel along one path (its smallest capacity).
- Use conservation of flow: at every vertex other than the source and sink, flow in = flow out.
- Build up a flow through a network path by path without exceeding any capacity.
A farm on the Darling Downs pumps water from a dam to its storage tank through a system of pipes. Each pipe can carry only so much: a wide main might take 9 kilolitres per hour, a narrow branch only 3. The farmer wants to know the most water that can reach the tank each hour.
Adding up the pipes leaving the dam won't do — some of that water could be held up further along. To answer the question properly you need a flow network.
Definition
Flow networks
A flow network is a directed, weighted graph in which each weight is a capacity: the most that can travel along that edge per unit of time.
- The source is the vertex where the flow starts. Edges only leave it.
- The sink is the vertex where the flow ends. Edges only arrive at it.
- The flow along an edge is how much actually travels along it: anything from 0 up to its capacity, in the direction of the arrow.
The farm's pipes. Capacities are in kilolitres per hour (kL/h). is the dam (the source) and is the tank (the sink).
Follow one route, ––. The pipe could deliver 9 kL/h to , but can only take 6 kL/h onwards. Water can't pile up at a junction, so this route carries at most 6 kL/h.
The weakest link sets the limit. The edge of smallest capacity on a path is its bottleneck.
Key idea
Flow along one path
The largest flow that can travel along a single path is the smallest capacity on that path — not the sum of the capacities.
What is the largest flow, in kL/h, that can travel along the path –– on its own?
Key idea
Conservation of flow
Two rules hold for every flow through a network:
- The flow along each edge is between 0 and its capacity.
- At every vertex other than the source and the sink, total flow in = total flow out. Nothing is stored or lost at a junction.
So the total flow leaving the source equals the total flow arriving at the sink. That amount is the value of the flow.
Worked example
Building a flow path by path
The farm network in the figure carries water from the dam to the tank . Capacities are in kilolitres per hour (kL/h).
(a) What is the largest flow that the path –– can carry?
(b) Send as much as possible along ––, then along ––, then along –––. What total flow do you reach?
(c) Check that flow in equals flow out at and at .
Step 1: Find the bottleneck of S–A–T
The capacities along –– are 9 and 6. The smaller one limits the path, so it carries at most 6 kL/h.
Every kilolitre on this path passes through both pipes, so it can't carry more than the narrower one.
Step 2: Send 6 along S–A–T
Spare capacity left: has ; is full.
Step 3: Send 5 along S–B–T
The bottleneck is (as ). Spare capacity left: is full; has .
Step 4: Send 2 along S–A–B–T
Spare capacities on this path are : 3, : 3, : 2. The smallest is 2, so send 2. Now is full too.
Step 5: Add up the flows
kL/h. The edges now carry : 8, : 5, : 2, : 6, : 7.
Step 6: Check conservation
At : in , out ✓. At : in , out ✓.
Try it yourself first, then check the working one step at a time.
Answer
(a) 6 kL/h. (b) A total flow of 13 kL/h, with , , , and . (c) Flow in = flow out = 8 at and 7 at .
Method
The most a path can carry is its smallest (spare) capacity.
Send that much, reduce the spare capacities, and look for another path with spare capacity.
Check flow in = flow out at every middle vertex.
Watch out for
Adding the capacities along a path () instead of taking the smaller.
Forgetting that flow already sent uses up capacity: after step 2, has only 3 left, not 9.
A flow of 13 kL/h, written flow / capacity on each edge. Check : in 8, out . Check : in , out 7.
In a different network, 11 units per minute flow into junction along two edges, and has two edges leaving it. One of them carries 4 units per minute. How much flows along the other?
Common mistake
Adding along a path
Capacities along a path are not added. Every unit that travels –– passes through both pipes, so the path can carry only as much as its narrowest pipe.
Building a flow path by path, as in the example, always gives a valid flow. But is 13 kL/h really the most this farm can get? The pipes leaving the dam could carry . Is the 14th kilolitre just hard to find, or impossible? The next lesson gives a way to be certain: cuts.
Summary
A flow network is a digraph whose weights are capacities. Flow starts at the source and ends at the sink.
The flow along an edge can be anything from 0 up to its capacity.
The most a single path can carry is its smallest capacity, the bottleneck.
At every other vertex, flow in = flow out; so flow out of the source = flow into the sink.
You can build a flow path by path, reducing the spare capacity each time — but that alone does not prove the flow is the largest possible.
Finished the lesson?
Try the 2 quick checks above and the lesson completes itself, or mark it complete now.