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.
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"?
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$.
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
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
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
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.)
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?
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 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.
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.
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.
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 .
Worked examples · 3 problems
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?
Source = $S$ (outgoing edges only: $S \to A$, $S \to B$)
Sink = $T$ (incoming edges only: $A \to T$, $C \to T$)
$A \to C$ (cap 6) and $B \to C$ (cap 7)
Total capacity into $C$ = 6 + 7 = 13
Flow in: 6 + 7 = 13
Flow out: 10
$13 \neq 10$ — conservation is violated
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.
$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$
Edges from $S/A$-side to $B/T$-side:
$S \to B$ (cap 10) + $A \to B$ (cap 4) + $A \to T$ (cap 8)
Cut capacity = 10 + 4 + 8 = 22
Edges from $S$-side:
$S \to A$ (cap 15) + $S \to B$ (cap 10)
Cut capacity = 15 + 10 = 25
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\}$.
$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$
$S \to A \to C \to T$
$S \to A \to B \to T$
$S \to A \to B \to C \to T$
$S \to B \to T$
$S \to B \to C \to T$
Edges from $\{S,A,B,C\}$-side to $\{T\}$-side:
$B \to T$ (cap 9) + $C \to T$ (cap 18)
Cut capacity = 9 + 18 = 27 ML/day
Match each network flow term with its correct description:
Top 3 list: List THREE real-world systems that could be modelled as a network flow problem.
Water from reservoir to town: the limiting factor is the narrowest pipe anywhere along any route — that's the "cut". A blocked pipe reduces the outflow from one node, which by conservation must reduce flow through the whole path it served. "At capacity" means every edge along at least one path from $S$ to $T$ is carrying its maximum flow — no additional flow can be pushed through without exceeding some edge's capacity.
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)
SA 2. The table below describes a network flow:
| From | To | Capacity |
|---|---|---|
| S | A | 14 |
| S | B | 11 |
| A | C | 8 |
| B | C | 9 |
| C | T | 16 |
(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)
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)
📖 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) Cut $\{S,A,B,C,D\} \mid \{T\}$: $C \to T$ (9) + $D \to T$ (8) = 17. This is lower than 18 — it is the bottleneck at the sink side, formed by the only two edges directly entering $T$ [1].
Five timed network flow terminology questions. Gold tier: 90% + speed.
⚔ Enter the arenaMark lesson as complete
Tick when finished.