Flow Capacity & Saturated Edges
Learn flow capacity and saturated edges for NSW Year 12 Mathematics Standard 2. You will find the maximum flow of a network by the saturated-edges method — pushing flow along paths until every route from the source to the sink contains a full (saturated) edge where flow equals capacity.
Along the way you will use spare capacity, apply inflow = outflow at each vertex, spot the bottleneck edges, work out the effect of increasing or reducing an edge capacity, and decide whether the flow capacity meets a required demand — a core Standard 2 network skill for water mains, drains, roads, evacuation routes and data links.
Theory
Flow capacity is the greatest flow a network can carry from source to sink. This Year 12 Standard 2 (NSW) guide finds it by the saturated-edges method — filling paths until every route holds a full edge — and shows how to read saturated edges (flow = capacity), spare capacity, conservation of flow, the bottleneck, and whether the flow capacity meets a required demand.
In a flow network each directed edge has a capacity (the most it can carry) and a flow (what it actually carries). Flow travels from the source to the sink, and on every edge \(0\le\text{flow}\le\text{capacity}\).
An edge is saturated when its flow equals its capacity — it is full and can take no more. Its spare capacity is \(\text{capacity}-\text{flow}\), so a saturated edge has zero spare. At every intermediate vertex, flow is conserved: the inflow equals the outflow.
The flow capacity (or maximum flow) is the greatest flow the whole network can carry. This Year 12 Standard 2 (NSW) topic finds it by inspection — the saturated-edges method — pushing flow along paths until every source-to-sink path contains a saturated edge. Those edges are the bottleneck.
Spare capacity of an edge:
An edge is saturated exactly when it is full:
At every intermediate vertex, flow is conserved:
Finding the flow capacity by saturating edges
- Read each edge's capacity (and its flow, if a flow is already shown).
- Push flow along a path from the source \(S\) to the sink \(T\), increasing it until one edge on the path becomes saturated (flow = capacity).
- Repeat on other \(S\)–\(T\) paths, keeping inflow = outflow at each vertex, until every path contains a saturated edge.
- Read off the flow capacity as the total flow leaving \(S\); note the bottleneck (saturated) edges and check the total against any stated demand.
A saturated edge has flow \(=\) capacity; spare \(=\) capacity \(-\) flow.
| \(SA:\ 9\) | \(=\) | \(9\ \text{(saturated)}\) |
| \(BT:\ 8\) | \(=\) | \(8\ \text{(saturated)}\) |
| \(\text{spare } AT\) | \(=\) | \(10-6 = 4\) |
| \(\text{into } T\) | \(=\) | \(6+8 = 14\) |
\(SA\) and \(BT\) are saturated; spare of \(AT\) is \(4\) L/s; total into \(T\) is \(14\) L/s.
At an intermediate vertex the inflow equals the outflow.
| \(\text{inflow to } A\) | \(=\) | \(13\) |
| \(\text{outflow from } A\) | \(=\) | \(5 + AT\) |
| \(13\) | \(=\) | \(5 + AT\) |
| \(AT\) | \(=\) | \(8\) |
The flow along \(AT\) is \(8\) kL/h.
Saturate paths until every route is blocked by a full edge.
| \(\text{into } C:\ AC+BC\) | \(=\) | \(300+250 = 550\) |
| \(\text{out of } S:\ SA+SB\) | \(=\) | \(700\ (\ge 550)\) |
| \(CT\) | \(=\) | \(800\ (\ge 550)\) |
| \(\therefore\ \text{flow capacity}\) | \(=\) | \(550\) |
The flow capacity is \(550\) people/min; \(AC\) and \(BC\) are the saturated bottleneck edges.
Each route carries at most its smallest capacity; add the routes.
| \(S\text{-}A\text{-}T\) | \(=\) | \(\min(30,18) = 18\) |
| \(S\text{-}B\text{-}T\) | \(=\) | \(\min(24,20) = 20\) |
| \(\text{flow capacity}\) | \(=\) | \(18+20 = 38\) |
| \(\text{after } AT\to 30\) | \(=\) | \(\min(30,30)+20 = 50\) |
Flow capacity is \(38\) ML/day, so \(45\) is not met (short by \(7\)). Upgrading \(AT\) raises it to \(50\) ML/day, which meets the demand.
Common pitfalls
Frequently asked questions
What is a saturated edge in a flow network?
A saturated edge is one whose flow equals its capacity, so it is completely full and cannot carry any more. Its spare capacity is zero. Saturated edges are usually the ones that limit, or bottleneck, the flow through the network.
What does the flow capacity of a network mean?
The flow capacity, also called the maximum flow, is the greatest amount that can travel from the source to the sink at once. You find it by pushing flow along paths until every source-to-sink path contains a saturated edge; the flow capacity is then the total flow leaving the source, which equals the total reaching the sink.
How do you find the flow capacity by inspection?
Send flow along a path from the source to the sink and increase it until one edge fills up (saturates). Repeat on the other paths, keeping inflow equal to outflow at each vertex, until every path from source to sink has a full edge on it. Add up the flow leaving the source to get the flow capacity.
What is spare capacity?
Spare capacity is capacity minus flow: how much extra an edge could still carry. A saturated edge has zero spare capacity, while an edge carrying 3 out of a capacity of 7 has 4 units of spare capacity.
Why isn't the flow capacity just the total of all the pipe capacities?
Because flow has to travel along connected paths from the source to the sink, and it is held back by the tightest point on the way. A single bottleneck edge, or a small set of saturated edges, can cap the whole network well below the sum of every capacity.
What does inflow equals outflow mean?
At any intermediate vertex (not the source or the sink) the flow is conserved: everything that flows in must flow out. This lets you find a missing edge flow, since the flows entering a vertex must add up to the flows leaving it.