M
hscscienceMaths Std · Y12
0/100daily goal
0
0
L1 · 0 XP
KJ
Your weak spots
Insights load after your first practice round.
Network Flow · L2 of 3 ~50 min MST-12-S2-06 ⚡ +90 XP available

Flow Capacity and the Saturated Edges Method

Finding the maximum flow through a network means pushing as much as possible through every path, then checking which edges have reached their limit. The saturated edges method gives you a systematic way to find the maximum flow, and to identify which edges are the bottleneck.

Today's hook, A network has source $S$, two middle nodes $A$ and $B$, and sink $T$. Edges: $S \to A$ (cap 8), $S \to B$ (cap 5), $A \to T$ (cap 6), $B \to T$ (cap 7). Before calculating, what is the maximum possible flow from $S$ to $T$, and which edge limits the total flow?
0/5QUESTS
1

Orient to flow capacity

Connect the opening network to the lesson facts, goals and vocabulary.

01
Recall, your gut answer first
+5 XP warm-up

A network has source $S$, two middle nodes $A$ and $B$, and sink $T$. Edges: $S \to A$ (cap 8), $S \to B$ (cap 5), $A \to T$ (cap 6), $B \to T$ (cap 7). Before calculating, write your gut answers to these:

  • What is the maximum possible flow from $S$ to $T$?
  • Which edge do you think limits the total flow, and why?
auto-saved
02
The key facts you need to own
+5 XP to read

In a flow network, every edge carries an actual flow ≤ capacity. We write this as flow/capacity on each edge, e.g. $6/8$ means 6 units flowing on a capacity-8 edge. An edge where flow = capacity is saturated it cannot carry any more.

Maximising flow means routing as many units as possible from $S$ to $T$ without exceeding any edge's capacity. The saturated edges method is systematic: find a path, push as much flow as possible (limited by the smallest capacity on the path), mark saturated edges, repeat until no unsaturated path remains.

$\text{flow on edge} \leq \text{capacity}$  |  $\text{max flow} = \sum \text{flows out of } S$  |  saturated: $\text{flow} = \text{capacity}$
Bottleneck of a path
When pushing flow along a path, the maximum you can push is the smallest capacity (bottleneck) on that path. E.g. path $S \to A \to T$ with capacities 8 and 6: bottleneck = 6.
Order of paths doesn't change the answer
HSC exam networks are small enough that you can try paths in any order and still reach the same maximum flow. Work systematically to avoid missing paths.
Saturated ≠ whole network saturated
One saturated edge on every path from $S$ to $T$ is what blocks further flow, not every edge needs to be saturated. A single bottleneck edge can halt the entire network.
03
What you'll master
Know

Key facts

  • Meaning of "saturated edge": flow = capacity
  • Saturated edges method: push flow along paths, saturate as you go, stop when all paths blocked
  • Maximum flow = total flow out of $S$ = total flow into $T$
Understand

Concepts

  • Why the minimum-capacity edge on a path is the bottleneck
  • Why total flow out of $S$ must equal total flow into $T$ (flow conservation on whole network)
  • How to systematically try all paths to maximise flow
Can do

Skills

  • Assign flows to edges using the saturated edges method
  • Identify which edges are saturated in the final solution
  • Calculate the total maximum flow through the network
  • Write each edge's flow as flow/capacity notation
04
Key terms
Actual flowThe number of units currently travelling along an edge. Must be ≤ the edge's capacity at all times.
Saturated edgeAn edge where actual flow = capacity. Written as e.g. $8/8$. No additional flow can pass through a saturated edge.
Unsaturated edgeAn edge where actual flow < capacity. It still has spare capacity for more flow.
BottleneckThe edge with the minimum capacity along a path. It determines the maximum flow that can be pushed along that path in one step.
Flow value (of network)The total flow leaving $S$ (= total flow entering $T$). This is the quantity we want to maximise.
Saturated edges methodA step-by-step algorithm: select a path $S \to T$, push as much flow as possible (bottleneck), repeat until all paths are blocked by at least one saturated edge.
Path flowThe amount of flow pushed along a single path in one step of the saturated edges method. Equal to the bottleneck of that path.
Residual capacityThe remaining capacity of an edge after flow has been assigned: residual = capacity − actual flow. Used when two paths share an edge.
2

Read flow and saturated edges

Interpret flow/capacity labels and recognise residual capacity.

05
Flow on Edges and Saturated Edges
core concept

In a solved flow network, every edge shows two numbers: the actual flow and its capacity. An edge is saturated when it carries its full capacity, no more flow can pass through it.

Notation and feasibility:

  • Notation: Write actual flow / capacity on each edge. E.g. $5/8$ means 5 units flowing on a capacity-8 edge; $8/8$ is saturated.
  • Feasibility condition 1: Flow ≤ capacity on every edge. If any edge has flow > capacity, the assignment is invalid.
  • Feasibility condition 2: Flow conservation at every intermediate node, inflow = outflow at each node that is neither $S$ nor $T$.
  • Saturated edge: An edge where flow = capacity. Such an edge cannot carry any additional flow.
  • How saturation blocks paths: A path from $S$ to $T$ is blocked when at least one of its edges is saturated. If every path from $S$ to $T$ has at least one saturated edge, no more flow can be added.
Reading a flow assignment: Network with flows: $S \xrightarrow{3/5} A$, $A \xrightarrow{3/4} T$, $S \xrightarrow{2/7} B$, $B \xrightarrow{2/6} T$. Check: Flow out of $S$: $3 + 2 = 5$. Flow into $T$: $3 + 2 = 5$. Equal ✓. Conservation at $A$: in = 3, out = 3 ✓. Conservation at $B$: in = 2, out = 2 ✓. No edge is saturated ($3 < 5$, $3 < 4$, $2 < 7$, $2 < 6$).
When IS the assignment invalid? If you see a node where inflow ≠ outflow (other than $S$ or $T$), or where flow > capacity on any edge, the assignment is wrong. Check these before stating your answer.

Flow on an edge must satisfy two rules: (1) flow ≤ capacity of that edge, and (2) flow conservation at every intermediate node (total flow in = total flow out). A saturated edge is one where flow equals capacity.

Pause, copy the two flow rules: (1) flow on any edge ≤ its capacity; (2) flow in = flow out at every intermediate node (conservation), and the saturated edge definition: an edge where flow = capacity into your book.

Quick check: A path from $S$ to $T$ has edge capacities 9, 4, and 11. The maximum flow that can be pushed along this path in one step is:

3

Use the saturated edges method

Push flow along paths, update residual capacity and identify blocked routes.

06
The Saturated Edges Method
core concept

Every edge must satisfy two rules: flow ≤ capacity (capacity constraint), and total flow in = total flow out at every intermediate node (conservation). An edge where flow equals capacity is saturated. A set of saturated edges that together form a cut, disconnecting every source-to-sink path, has a total capacity equal to the maximum flow through the network.

The saturated edges method is a step-by-step procedure for finding the maximum flow of a network. You push flow along one path at a time, saturating at least one edge per step, until no path from $S$ to $T$ remains unsaturated.

Steps of the saturated edges method:

  1. Identify all paths from $S$ to $T$ in the network.
  2. Choose any unsaturated path. Find its bottleneck (minimum capacity along the path).
  3. Assign that amount of flow to every edge on the path. Mark any edge that is now saturated.
  4. Reduce remaining capacities accordingly (residual capacity = capacity − flow).
  5. Repeat from step 2 until every path from $S$ to $T$ contains at least one saturated edge.
  6. Confirm it is the maximum. Find a cut whose capacity equals the total flow out of $S$. A feasible flow can never beat a cut, so when the two agree the value is the maximum and you are finished. If no cut matches your total, a different ORDER of paths will do better: go back, re-allocate, and try again. "No unsaturated path is left" only means you cannot add more without changing what you have already assigned.
  7. Maximum flow = total flow out of $S$.
Worked mini-example: Network: $S \to A$ (cap 8), $S \to B$ (cap 6), $A \to T$ (cap 5), $B \to T$ (cap 7).
Step 1: Paths: $S \to A \to T$ and $S \to B \to T$.
Step 2: Take path $S \to A \to T$: bottleneck = min(8, 5) = 5. Push 5 units. $A \to T$ is now saturated (5/5). $S \to A$ has 5/8.
Step 3: Take path $S \to B \to T$: bottleneck = min(6, 7) = 6. Push 6 units. $S \to B$ is saturated (6/6). $B \to T$ has 6/7.
Step 4: No more unsaturated paths. $S \to A$ still has residual 3, but $A \to T$ is saturated, path 1 is blocked. Path 2 is blocked by $S \to B$ saturated. Done.
Maximum flow = 5 + 6 = 11.
When paths share edges: If two paths share an edge, the second path can only use the residual capacity (capacity − flow already assigned). Plan the order carefully, or update residual capacities after each step.

Saturated edges method: find the maximum flow by identifying all saturated edges that form a cut. Add the capacities of these edges, their sum equals the maximum flow through the network.

Pause, copy the saturated-edges method: find all edges where flow = capacity, identify which of these form a cut (together they disconnect every S-to-T path), then sum those edge capacities, that sum equals the maximum flow into your book.

True or false: In the saturated edges method, you must always choose the path with the highest bottleneck capacity first in order to get the maximum flow.

4

Solve a complete flow problem

Apply conservation and capacity constraints across a whole network.

07
Solving a Complete Flow Problem
core concept

Finding saturated edges that form a cut gives the maximum flow directly, because max-flow = min-cut. To earn all marks in an HSC network flow question, use the four-step structure: draw the network (or confirm the given one), assign feasible flows to each edge respecting capacity and conservation, identify the minimum cut as the set of saturated edges that disconnects S from T, then state max flow = sum of cut capacities.

Putting it all together: read the network, list all paths, apply the saturated edges method step by step, and state the maximum flow with all edge flows written in flow/capacity notation.

Full solution structure:

  1. Draw or reproduce the network.
  2. List all paths $S \to T$.
  3. Apply saturated edges method, showing each step.
  4. Write the final flows on each edge.
  5. State: "Maximum flow = X units."

Verify your answer: Check that total outflow from $S$ = total inflow to $T$; check conservation at every intermediate node; check no edge exceeds capacity.

What to write in the exam: Label each edge with flow/capacity. State the maximum flow clearly. If asked to identify saturated edges, list them explicitly.

Full example (5-node network): Edges: $S \to A$ (10), $S \to B$ (8), $A \to C$ (6), $A \to T$ (5), $B \to C$ (7), $C \to T$ (9). Paths: $S \to A \to C \to T$; $S \to A \to T$; $S \to B \to C \to T$.
Path 1 ($S \to A \to T$): bottleneck = min(10, 5) = 5. Push 5. $A \to T$ saturated (5/5). $S \to A$ has 5/10.
Path 2 ($S \to B \to C \to T$): bottleneck = min(8, 7, 9) = 7. Push 7. $B \to C$ saturated (7/7). $S \to B$ has 7/8, $C \to T$ has 7/9.
Path 3 ($S \to A \to C \to T$): residual $S \to A$ = 5, $A \to C$ = 6, $C \to T$ = 9 − 7 = 2; bottleneck = min(5, 6, 2) = 2. Push 2. $C \to T$ now 9/9 (saturated). $S \to A$ has 7/10, $A \to C$ has 2/6.
No remaining paths ($A \to T$ and $C \to T$ are both saturated, and every route to $T$ ends on one of them). Maximum flow = 5 + 7 + 2 = 14.
Final: $S \to A$ (7/10), $S \to B$ (7/8), $A \to C$ (2/6), $A \to T$ (5/5 ✓ sat), $B \to C$ (7/7 ✓ sat), $C \to T$ (9/9 ✓ sat).
Check it against the cut. The saturated edges that block every route to $T$ are $A \to T$ and $C \to T$, which form the cut $\{S,A,B,C\} \mid \{T\}$ with capacity $5 + 9 = 14$. That equals the flow found, so 14 really is the maximum. Do this check every time: a different path ORDER can leave you stranded below the maximum, and comparing against a cut is what catches it.

A complete network flow solution: (1) draw the network, (2) assign flow to each edge respecting capacity and conservation, (3) identify a minimum cut (set of saturated edges disconnecting source from sink), (4) state max flow = min cut capacity.

Pause, copy the four-step solution: (1) draw or confirm the network; (2) assign flows satisfying capacity and conservation; (3) identify the minimum cut (saturated edges disconnecting S from T); (4) state maximum flow = minimum cut capacity into your book.

Fill the blanks: Network: $S \to A$ (cap 7), $S \to B$ (cap 5), $A \to T$ (cap 4), $B \to T$ (cap 6).
Path $S \to A \to T$: bottleneck = min(7, 4) = . Push 4 units. $A \to T$ becomes .
Path $S \to B \to T$: bottleneck = min(5, 6) = . Push 5 units.
Maximum flow = 4 + 5 = units.

5

Work through capacity examples

Follow complete path calculations and verify the resulting maximum flow.

Worked examples · 3 problems

PROBLEM 1 · SIMPLE 4-NODE NETWORK

Network: $S \to A$ (cap 9), $S \to B$ (cap 7), $A \to T$ (cap 6), $B \to T$ (cap 8). (a) List all paths from $S$ to $T$. (b) Apply the saturated edges method. (c) State the maximum flow and identify all saturated edges.

1
Part (a), list all paths
Path 1: $S \to A \to T$
Path 2: $S \to B \to T$
This network has two distinct paths from $S$ to $T$. Always list paths systematically before starting the method.
1 of 4
PROBLEM 2 · PATHS THAT SHARE AN EDGE

Network: $S \to A$ (12), $S \to B$ (8), $A \to C$ (7), $B \to C$ (6), $C \to T$ (11). (a) List paths. (b) Apply the saturated edges method. (c) What is the maximum flow? Which edge is the bottleneck for the whole network?

1
Part (a), list all paths
Path 1: $S \to A \to C \to T$
Path 2: $S \to B \to C \to T$
Note: $C \to T$ is shared by both paths.
Both paths pass through node $C$ and then use the single $C \to T$ edge. This shared edge means we must track residual capacity on it.
1 of 4
PROBLEM 3 · COMPLETE 6-EDGE NETWORK

Supply chain network: $S \to A$ (15), $S \to B$ (10), $A \to B$ (3), $A \to T$ (8), $B \to T$ (11). (a) Draw and label the network. (b) List all paths. (c) Apply the saturated edges method to find maximum flow. (d) Write the final flow assignment on all edges.

1
Parts (a) & (b), network and paths
4 nodes: $S$, $A$, $B$, $T$. 5 edges.
Path 1: $S \to A \to T$
Path 2: $S \to A \to B \to T$
Path 3: $S \to B \to T$
The $A \to B$ cross-edge creates a third path. Always check for cross-edges, they add paths that are easy to miss.
1 of 5

Match each flow/capacity label with what it tells you:

  • 0/6
  • 5/5
  • 3/8
  • 8/8
  • Edge carrying 3 units with 5 units of spare capacity
  • Saturated at capacity 8, so it caps any path running through it
  • Edge with capacity 6, currently carrying no flow
  • Saturated at capacity 5, cannot carry any more flow
6

Consolidate and revisit

Check valid flow assignments and revisit the bottlenecks in the opening network.

Top 3 list: List THREE things you must check to verify a flow assignment is valid and represents the maximum flow.

09
Revisit your thinking

Original network: $S \to A$ (8), $S \to B$ (5), $A \to T$ (6), $B \to T$ (7). Actual maximum flow: Path $S \to A \to T$: bottleneck = min(8, 6) = 6. Path $S \to B \to T$: bottleneck = min(5, 7) = 5. Max flow = 6 + 5 = 11. The limiting edge was $A \to T$ (capacity 6) for path 1, it saturates first, and $S \to B$ (capacity 5) for path 2. The network total is 11, which is less than the sum of capacities leaving $S$ (8 + 5 = 13) because the $A \to T$ edge caps path 1 at 6.

auto-saved
7

Apply the saturated edges method

Calculate maximum flow, record edge assignments and justify saturated bottlenecks.

01
Short answer, exam-style questions
show all working
ApplyBand 33 marks

SA 1. A network has edges: $S \to A$ (cap 10), $S \to B$ (cap 8), $A \to T$ (cap 7), $B \to T$ (cap 6). Use the saturated edges method to find the maximum flow. Show all steps. (3 marks)

auto-saved
ApplyBand 3–43 marks

SA 2. Network: $S \to A$ (9), $S \to B$ (6), $A \to C$ (8), $B \to C$ (5), $C \to T$ (10). Apply the saturated edges method. What is the maximum flow? Which edge acts as the overall bottleneck for the whole network? (3 marks)

auto-saved
AnalyseBand 4–54 marks

SA 3. A supply chain network has edges: $S \to A$ (14), $S \to B$ (9), $A \to B$ (4), $A \to T$ (7), $B \to T$ (12). (a) Apply the saturated edges method in full. (b) Write the final flow assignment on every edge using flow/capacity notation. (c) State the maximum flow. (d) Identify all saturated edges. (4 marks)

auto-saved
📖 Comprehensive answers (click to reveal)

SA 1 (3 marks): Paths: $S \to A \to T$ and $S \to B \to T$ [1]. Path 1: bottleneck = min(10, 7) = 7; push 7. $A \to T$ saturated (7/7). Path 2: bottleneck = min(8, 6) = 6; push 6. $S \to B$ carries 6/8 and has 2 units of residual capacity; $B \to T$ is saturated (6/6) [1]. Maximum flow = 7 + 6 = 13. Saturated edges: $A \to T$ and $B \to T$ [1].

SA 2 (3 marks): Paths: $S \to A \to C \to T$ and $S \to B \to C \to T$. Path 1: min(9, 8, 10) = 8; push 8. $A \to C$ saturated (8/8); $C \to T$ has 8/10 [1]. Path 2: residual $C \to T$ = 2; min(6, 5, 2) = 2; push 2. $C \to T$ now 10/10 saturated [1]. Maximum flow = 8 + 2 = 10. Bottleneck = $C \to T$ (capacity 10 = maximum flow, every unit of flow must pass through it) [1].

SA 3 (4 marks): (a) Paths: $S\to A\to T$; $S\to A\to B\to T$; $S\to B\to T$. Path 1: min(14,7)=7; push 7. $A\to T$ sat (7/7); $S\to A$ has 7/14. Path 2: residual $S\to A$=7; min(7,4,12)=4; push 4. $A\to B$ sat (4/4); $S\to A$=11/14; $B\to T$=4/12. Path 3: residual $B\to T$=8; min(9,8)=8; push 8. $B\to T$=12/12 sat; $S\to B$=8/9. No more paths ($A\to T$ and $A\to B$ saturated; $B\to T$ saturated) [2]. (b) $S\to A$: 11/14; $S\to B$: 8/9; $A\to B$: 4/4; $A\to T$: 7/7; $B\to T$: 12/12 [1]. (c) Maximum flow = 7 + 4 + 8 = 19. (d) Saturated: $A\to B$ (4/4), $A\to T$ (7/7), $B\to T$ (12/12) [1].