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 · L1 of 3 ~40 min MST-12-S2-06 ⚡ +85 XP available

Network Flow, Terminology and Directed Diagrams

A network flow diagram is a directed map showing how something, water, traffic, data, goods, moves through a system from a single entry point to a single exit point. Before you can solve flow problems, you need to read and draw these diagrams fluently.

Today's hook, Water flows from a reservoir through a series of pipes to a town. The pipes have different widths, some can carry more water per minute than others. Think about: what limits how much water can reach the town per minute? What happens if one pipe gets blocked? What does it mean for the network to be "at capacity"?
0/5QUESTS
1

Orient to network flow

Connect the reservoir problem to the lesson goals and essential vocabulary.

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

Water flows from a reservoir through a series of pipes to a town. The pipes have different widths, some can carry more water per minute than others. Write your gut answers to these, no calculating yet:

  • What limits how much water can reach the town per minute?
  • If one pipe along the way gets blocked, what happens to the rest?
  • What would it mean for the network to be "at capacity"?
auto-saved
02
The key relationships you need to own
+5 XP to read

Every directed edge is a one-way pipe with a capacity limit. At every internal node, what flows in must flow out no accumulation allowed. The source is the tap; the sink is the drain; cuts are the chokepoints.

Source ($S$): outflow only, where flow enters the network. Sink ($T$): inflow only, where flow exits. Edge capacity: maximum flow an edge can carry. Cut: a set of edges whose removal disconnects $S$ from $T$.

$\text{inflow} = \text{outflow}$ at each intermediate node  |  $\text{cut capacity} = \sum \text{capacities of edges in cut}$
Directed vs undirected
A directed edge (arrow) means flow can only go in the direction of the arrow, never backwards. In flow networks, all edges are directed from source toward sink.
One source, one sink
HSC Standard exam flow networks always have exactly one source (label it $S$) and one sink (label it $T$). All other nodes are intermediate, their inflow equals their outflow.
Capacity ≠ actual flow
An edge with capacity 8 can carry 0 to 8 units of flow, the capacity is the maximum, not the amount currently flowing. The actual flow is what you assign when solving.
03
What you'll master
Know

Key facts

  • Definitions: source ($S$), sink ($T$), directed edge, capacity, inflow, outflow, cut
  • Flow conservation rule: inflow = outflow at each intermediate node
  • How to identify $S$, $T$, and cuts in a network diagram
Understand

Concepts

  • Why edges are directed (flow is one-way) and why this matters for capacity
  • What "cut capacity" represents, it's a measure of the narrowest chokepoint
  • How a table of edge information translates to a weighted directed diagram
Can do

Skills

  • Draw a weighted directed network diagram from a table of edges and capacities
  • Label $S$, $T$, and all intermediate nodes
  • Identify a cut and calculate its capacity
  • Verify flow conservation at a given node
04
Key terms
Source ($S$)The node with outflow only, the entry point where flow enters the network. No edges lead into $S$.
Sink ($T$)The node with inflow only, the exit point where flow leaves the network. No edges lead out of $T$.
Directed edge (arc)An arrow connecting two nodes that allows flow in one direction only. Drawn as a line with an arrowhead.
Capacity (weight)The maximum amount of flow that can pass through an edge. Written as a number on the edge.
InflowThe total amount entering a node, sum of flows along all edges directed into that node.
OutflowThe total amount leaving a node, sum of flows along all edges directed out of that node.
Flow conservationAt every intermediate node, inflow = outflow. Nothing is created or destroyed inside the network.
CutA set of directed edges whose removal disconnects $S$ from $T$. Every flow path crosses at least one cut edge.
Cut capacitySum of the capacities of all edges in a cut (forward-crossing edges only, from $S$-side to $T$-side).
2

Read flow terminology

Identify sources, sinks, directed edges, capacities and conservation.

05
Network Flow Terminology
core concept

A network flow diagram is a directed graph where each edge has a capacity, the maximum amount that can pass through it. Flow enters at the source and leaves at the sink, obeying conservation at every intermediate node.

Components of a flow network:

  • Nodes (vertices): Every point in the network. $S$ = source (outflow only), $T$ = sink (inflow only). All others are intermediate.
  • Directed edges (arcs): Arrows showing the direction of flow. Each has a capacity, written as a weight: $S \xrightarrow{8} A$ means up to 8 units can flow from $S$ to $A$.
  • Inflow at a node: Sum of capacities (or flows) of all edges entering the node.
  • Outflow at a node: Sum of capacities (or flows) of all edges leaving the node.
  • Flow conservation: At every intermediate node, total inflow = total outflow. (Nothing is created or destroyed inside the network.)
Why directed edges matter: In an undirected network (like the MST-11-07 Networks topic), you can travel along any edge in either direction. In a flow network, the direction is fixed, you cannot send flow backwards along an edge. This is what makes flow problems distinct from earlier network problems.
Real contexts for network flow: Water supply networks (pipes from reservoir to suburb), internet data routing (data from server to client), traffic systems (cars from entry ramps to exit), supply chains (goods from warehouse to retail). In each case: one origin point, one destination point, and edges with capacity limits.

Network flow terminology: source (origin node), sink (destination node), directed edges with capacities (maximum flow allowed), and flow (actual amount passing along an edge, must not exceed capacity).

Pause, copy the four key network flow terms: source (origin node S), sink (destination node T), capacity (maximum flow on an edge, its label), and flow (actual amount on an edge, must not exceed capacity) into your book.

Quick check: In a network flow diagram, a node receives flow from two edges with capacities 5 and 3, and sends flow along one edge with capacity 10. What is the maximum flow that can pass through this node without violating flow conservation?

3

Identify network cuts

Separate source and sink, then total only the edges crossing the cut.

06
Identifying Cuts
core concept

A network has a source (origin node), a sink (destination), directed edges with capacities (maximum flow per edge), and actual flows that cannot exceed those capacities. To find the maximum possible flow from source to sink, identify a cut, a set of edges whose removal disconnects every path from source to sink. The minimum-capacity cut equals the maximum flow by the max-flow min-cut theorem.

A cut is a set of edges you remove to completely block all flow from $S$ to $T$. Every flow path from $S$ to $T$ must cross at least one edge in the cut. The cut capacity is the sum of the capacities of those edges.

How to find and calculate a cut:

  • Identifying a cut: Draw an imaginary line through the network that separates all nodes into two groups: those on the $S$-side and those on the $T$-side. Every directed edge crossing from the $S$-side to the $T$-side is in the cut.
  • Cut capacity: Add the capacities of all edges in the cut (edges going FROM the $S$-side TO the $T$-side only, edges going the other way are not in the cut).
  • Why cuts matter: The minimum cut capacity equals the maximum flow that can pass through the network (this is proven in Lesson 3). Finding small cuts quickly identifies bottlenecks.
Cut capacity worked example: Network: $S \xrightarrow{8} A \xrightarrow{5} T$ and $S \xrightarrow{6} B \xrightarrow{7} T$.
Cut 1: {$S$-side: $\{S\}$, $T$-side: $\{A, B, T\}$}. Edges crossing: $S \to A$ (cap 8) and $S \to B$ (cap 6). Cut capacity = 8 + 6 = 14.
Cut 2: {$S$-side: $\{S, A, B\}$, $T$-side: $\{T\}$}. Edges: $A \to T$ (cap 5) and $B \to T$ (cap 7). Cut capacity = 5 + 7 = 12.
Only forward-crossing edges count: A cut is defined as edges going FROM the $S$-side TO the $T$-side. If any edge goes the other way (from $T$-side back to $S$-side), it is NOT included in the cut capacity. This is important in networks with cross-edges.

A cut is a set of edges whose removal disconnects all paths from source to sink. The capacity of a cut is the sum of the capacities of its directed edges (source→sink direction only). Minimum cut = maximum flow.

Pause, copy the cut definition (set of edges disconnecting all S-to-T paths), the cut capacity formula (sum of capacities of those edges, S-to-T direction only), and the max-flow min-cut theorem: maximum flow = minimum cut capacity into your book.

True or false: When calculating the capacity of a cut, you include ALL edges crossing the cut line, including edges directed from the $T$-side back toward the $S$-side.

4

Convert tables to diagrams

Turn each table row into a correctly weighted directed edge.

07
Converting a Table to a Network Diagram
core concept

A cut is a set of edges whose removal disconnects all source-to-sink paths; its capacity is the sum of the capacities of those edges (counting only source-to-sink direction). The minimum cut gives the maximum flow directly. HSC questions often present the network as a table of edges rather than a diagram, each row of the table is one directed edge, labelled with its capacity.

HSC exam questions often give network information as a table of edges with their capacities and directions. You need to convert this into a drawn diagram accurately.

Drawing steps from a table:

  • Reading a table: Each row is one directed edge. Columns typically: From node | To node | Capacity.
  • Step 1: Place all nodes on your page, source $S$ on the left, sink $T$ on the right, intermediate nodes in the middle.
  • Step 2: For each row, draw a directed arrow from the "From" node to the "To" node.
  • Step 3: Label each edge with its capacity.
  • Step 4: Verify, $S$ has no incoming edges; $T$ has no outgoing edges.
  • Check: Identify all paths from $S$ to $T$ in your diagram to ensure all edges are accounted for.
Example table → diagram: Table: S→A (cap 10), S→B (cap 7), A→C (cap 6), B→C (cap 5), B→T (cap 4), C→T (cap 9). Draw: $S$ on left, $T$ on right, $A$, $B$, $C$ in middle. Draw 6 arrows with weights. $S$ has no incoming; $T$ has no outgoing. Paths: $S \to A \to C \to T$ and $S \to B \to C \to T$ and $S \to B \to T$.

To convert a precedence/flow table into a network diagram: each row becomes a directed edge; the edge label is the capacity; respect source and sink positions; arrows point from lower to higher node numbers by convention.

Pause, copy the table-to-diagram conversion rules: each row becomes one directed arrow, the capacity is the edge label, arrows point from source toward sink, and node names must match exactly between table and diagram into your book.

Fill the blanks: A table has edges: S→A (cap 9), S→B (cap 5), A→T (cap 7), B→T (cap 6). The total capacity leaving $S$ is 9 + 5 = . The total capacity entering $T$ is 7 + 6 = . The cut {$S$-side: $S$, $T$-side: $A$,$B$,$T$} contains edges $S \to A$ and $S \to B$; its cut capacity is .

5

Work through network examples

Apply the terminology, diagram and cut method to complete examples.

Worked examples · 3 problems

PROBLEM 1 · IDENTIFYING NODES AND EDGES

A network flow diagram has nodes $S$, $A$, $B$, $C$, $T$ with edges: $S \to A$ (cap 12), $S \to B$ (cap 8), $A \to C$ (cap 6), $B \to C$ (cap 7), $A \to T$ (cap 5), $C \to T$ (cap 10). (a) Identify the source and sink. (b) List all directed edges entering node $C$. (c) Check flow conservation at node $C$ if actual flows are: into $C$ from $A$ = 6, into $C$ from $B$ = 7, out of $C$ to $T$ = 10. Is conservation satisfied?

1
Part (a), source and sink
Source = $S$ (outgoing edges only: $S \to A$, $S \to B$)
Sink = $T$ (incoming edges only: $A \to T$, $C \to T$)
The source has no incoming edges; the sink has no outgoing edges. Check every node against this rule.
1 of 3
PROBLEM 2 · CONVERTING A TABLE AND IDENTIFYING CUTS

A supply network has the following edges: S→A (cap 15), S→B (cap 10), A→B (cap 4), A→T (cap 8), B→T (cap 12). (a) Draw the directed network diagram. (b) Identify the cut separating $\{S, A\}$ from $\{B, T\}$ and calculate its capacity. (c) Identify the cut separating $\{S\}$ from $\{A, B, T\}$ and calculate its capacity.

1
Part (a), draw the diagram
$S$ on left, $T$ on right, $A$ and $B$ in middle
5 directed arrows: $S \xrightarrow{15} A$, $S \xrightarrow{10} B$, $A \xrightarrow{4} B$, $A \xrightarrow{8} T$, $B \xrightarrow{12} T$
$S$ has no incoming edges; $T$ has no outgoing edges. Both intermediate nodes ($A$ and $B$) have both incoming and outgoing edges.
1 of 3
PROBLEM 3 · FULL TABLE CONVERSION WITH CUT ANALYSIS

A water pipeline network has these flow pipes: Pipe 1 S→A (20 ML/day), Pipe 2 S→B (15 ML/day), Pipe 3 A→C (12 ML/day), Pipe 4 A→B (8 ML/day), Pipe 5 B→C (10 ML/day), Pipe 6 B→T (9 ML/day), Pipe 7 C→T (18 ML/day). (a) Draw the diagram. (b) Find all paths from $S$ to $T$. (c) Calculate the cut capacity of the cut $\{S, A, B, C\} \mid \{T\}$.

1
Part (a), draw the diagram
$S$ left, $T$ right. Intermediate nodes $A$, $B$, $C$ in middle.
7 arrows: $S \xrightarrow{20} A$, $S \xrightarrow{15} B$, $A \xrightarrow{12} C$, $A \xrightarrow{8} B$, $B \xrightarrow{10} C$, $B \xrightarrow{9} T$, $C \xrightarrow{18} T$
Check: $S$ has no incoming edges. $T$ has no outgoing edges. $A$, $B$, $C$ all have at least one incoming and one outgoing edge.
1 of 3

Match each network flow term with its correct description:

  • Source
  • Cut
  • Flow conservation
  • Sink
  • At every intermediate node: inflow = outflow
  • The node with inflow only, where flow exits the network
  • The node with outflow only, where flow enters the network
  • A set of edges whose removal disconnects S from T
6

Consolidate and revisit

Retrieve the key terms, connect them to real systems and revisit your opening thinking.

Top 3 list: List THREE real-world systems that could be modelled as a network flow problem.

09
Revisit your thinking

Water from reservoir to town: the limiting factor is the total capacity across the narrowest cut, which may contain more than one pipe. A blocked pipe reduces the outflow from one node and can reduce the flow through any path it served. "At capacity" means no additional flow can be sent from $S$ to $T$ without exceeding at least one edge on every remaining route.

auto-saved
7

Apply network diagrams and cuts

Draw directed networks, identify inflow and outflow, and calculate cut capacities.

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

SA 1. A network has source $S$, sink $T$, and intermediate nodes $A$ and $B$. Edges: $S \to A$ (cap 9), $S \to B$ (cap 6), $A \to T$ (cap 7), $B \to T$ (cap 8), $A \to B$ (cap 3). (a) Draw the directed network diagram. (b) Identify all edges entering node $A$ and all edges leaving node $A$. (c) Calculate the capacity of the cut separating $\{S\}$ from $\{A, B, T\}$. (3 marks)

auto-saved
ApplyBand 3–43 marks

SA 2. The table below describes a network flow:

FromToCapacity
SA14
SB11
AC8
BC9
CT16

(a) Draw the directed network. (b) What is the total capacity of edges leaving $S$? (c) Calculate the cut capacity of the cut $\{S, A, B\} \mid \{C, T\}$ and describe what this cut represents physically. (3 marks)

auto-saved
AnalyseBand 44 marks

SA 3. A data network has 6 nodes: $S$, $A$, $B$, $C$, $D$, $T$. Edges: $S \to A$ (10), $S \to B$ (8), $A \to C$ (6), $A \to D$ (5), $B \to D$ (7), $C \to T$ (9), $D \to T$ (8). (a) Draw the directed network. (b) List all paths from $S$ to $T$. (c) Calculate the capacity of the cut $\{S, A, B\} \mid \{C, D, T\}$. (d) Is there another cut with a lower capacity? Find it and describe which edges form it. (4 marks)

auto-saved
📖 Comprehensive answers (click to reveal)

SA 1 (3 marks): (a) Directed arrows: $S \to A$ (9), $S \to B$ (6), $A \to T$ (7), $B \to T$ (8), $A \to B$ (3). $S$ on left, $T$ on right [1]. (b) Entering $A$: $S \to A$ (cap 9). Leaving $A$: $A \to T$ (cap 7), $A \to B$ (cap 3) [1]. (c) Cut $\{S\} \mid \{A, B, T\}$: edges $S \to A$ (9) + $S \to B$ (6) = 15 [1].

SA 2 (3 marks): (a) $S$ left, $T$ right; 5 directed arrows with weights as in the table [1]. (b) $14 + 11 = 25$ [1]. (c) Cut $\{S,A,B\} \mid \{C,T\}$: edges $A \to C$ (8) + $B \to C$ (9) = 17. Physically: these two pipes are the only routes from the source side to node $C$, removing both blocks all flow to $T$ [2].

SA 3 (4 marks): (a) 7 arrows as given [1]. (b) $S \to A \to C \to T$; $S \to A \to D \to T$; $S \to B \to D \to T$ [1]. (c) Edges from $\{S,A,B\}$ to $\{C,D,T\}$: $A \to C$ (6) + $A \to D$ (5) + $B \to D$ (7) = 18 [1]. (d) Yes, and it pays to look for the smallest rather than the first. The sink-side cut $\{S,A,B,C,D\} \mid \{T\}$ gives $C \to T$ (9) + $D \to T$ (8) = 17, which is already lower than 18. But $\{S,A,B,D\} \mid \{C,T\}$ is lower still: its forward edges are $A \to C$ (6) and $D \to T$ (8), capacity 14 [1]. That is the bottleneck, and the maximum flow is 14 — so 17 answers the question as worded but is not the constraint that actually limits this network.