Coaching Centre
Flow networks and maximum flow
The language of flow networks (source, sink, capacity, flow), drawing a network from a table, the rules every flow must obey, and finding the maximum flow by sending flow along paths.
Picture Sydney's water supply: water starts at a dam, travels through pipes of different sizes, and ends up at a reservoir that feeds the suburbs. Each pipe can carry only so much per day. How much can reach the reservoir in total? That is a maximum flow problem, and the same idea works for traffic on roads, passengers through train lines, or data through a network.
The language of flow
- The source is where everything starts. Flow only leaves it.
- The sink is where everything ends. Flow only enters it.
- The capacity of an edge is the most it can carry, such as $9$ megalitres per day. It is the weight on the edge.
- The flow along an edge is how much is actually being sent. Diagrams often show both as flow/capacity, like $6/9$.
Edges are directed: a pipe or a one-way street only carries flow in the direction of its arrow. Every flow must obey two rules:
- Capacity rule: the flow along an edge can't exceed its capacity.
- Conservation rule: at every vertex except the source and sink, flow in $=$ flow out. Water doesn't appear or vanish at a junction.
Together these mean the total flow leaving the source equals the total flow entering the sink.
At junction $A$, pipes bring in $4$ and $3$ ML/day. Two pipes leave: one carries $5$ ML/day. How much does the other carry?
From a table to a network
Capacities are often given in a table, read as "from the row, to the column". A dash means there is no pipe in that direction.
| From / To | A | B | T |
|---|---|---|---|
| S | $5$ | $4$ | – |
| A | – | $2$ | $3$ |
| B | – | – | $6$ |
Draw a vertex for S, A, B and T, then one arrow for each number: S→A $5$, S→B $4$, A→B $2$, A→T $3$, B→T $6$. Check the count: $5$ numbers in the table, $5$ arrows.
Finding the maximum flow
For a small network, build the flow up one path at a time:
- Pick a path from source to sink that still has spare capacity on every edge.
- The most you can send along it is its smallest spare capacity (the bottleneck).
- Send that much, update the spare capacities, and repeat until no path has spare capacity left.
Find the maximum flow from S to T in the network drawn from the table above.
This is a water network in megalitres per day. Click a path to send as much water along it as its narrowest pipe allows. Red pipes are full. Try S→A→C→T, then S→B→D→T, then S→A→B→D→T. What total do you reach?
Reset and start with the long path S→A→C→B→D→T instead. Why do you get stuck lower? Section 9E shows how to prove what the true maximum is.
Your turn
A network has S→A $8$, S→B $5$, A→B $3$, A→T $6$, B→T $7$. Find the maximum flow.
Show the working
S–A–T: $6$ (spare S→A $2$). S–B–T: $5$ (spare B→T $2$). S–A–B–T: bottleneck $\min(2, 3, 2) = 2$. Total $6 + 5 + 2 = 13$. Both edges out of S are now full ($8 + 5 = 13$), so $13$ is the maximum.
In a flow network, the sink is:
Flow starts at the source and finishes at the sink.
The capacity of an edge is:
Capacity is the maximum the edge can carry. The flow is what it is actually carrying, which can't be more.
Flows of $7$ and $5$ enter a junction. Two pipes leave it, and one carries $8$. How much does the other carry?
Flow in $= 7 + 5 = 12$. Flow out must also be $12$, so the other pipe carries $12 - 8 = 4$.
A path S→A→C→T has capacities $9$, $6$ and $7$. What is the most that can be sent along this path on its own?
The smallest capacity on the path limits it: $\min(9, 6, 7) = 6$.
A network has S→A $8$, S→B $5$, A→B $3$, A→T $6$, B→T $7$. Find the maximum flow from S to T.
S–A–T: $6$. S–B–T: $5$. S–A–B–T: $\min(8 - 6, 3, 7 - 5) = 2$. Total $13$. The edges out of S total $8 + 5 = 13$ and are both full, so this is the maximum.
A flow of $10$ is shown on an edge with capacity $8$. This is:
The capacity rule says the flow along every edge is at most its capacity, with no exceptions.
In a valid flow, the edges leaving the source carry $6$, $5$ and $3$. What is the total flow entering the sink?
Flow is conserved at every other vertex, so everything that leaves the source arrives at the sink: $6 + 5 + 3 = 14$.
Exam style: Traffic (cars per minute) flows from S to T along one-way streets: S→A $10$, S→B $8$, A→C $4$, A→D $7$, B→D $5$, C→T $9$, D→T $9$. Find the maximum flow.
S–A–C–T: $\min(10, 4, 9) = 4$. S–A–D–T: $\min(6, 7, 9) = 6$. S–B–D–T: $\min(8, 5, 3) = 3$, since D→T has only $3$ spare. Total $4 + 6 + 3 = 13$. Check: A→C ($4$) and D→T ($9$) are both full and together cut every route to T, so $13$ is the maximum.
Exam style: In the previous network, D→T is widened to carry $12$ cars per minute. Find the new maximum flow.
S–A–C–T: $4$. S–A–D–T: $6$. S–B–D–T: $\min(8, 5, 6) = 5$. Total $15$. Now S→A ($10$, full) and B→D ($5$, full) block every route, with capacity $10 + 5 = 15$, so $15$ is the maximum.