Network Flow Topic Test

Network flow · MST-12-S2-06

Maths Standard Year 12 · All 3 lessons · MC checkpoint plus separate short-answer practice

L1, Terminology and Directed Diagrams L2, Flow Capacity and Saturated Edges L3, Max-Flow Min-Cut and Meeting Demand
25 MC 8 SA ~55 min
0/25
MC Checkpoint
Answer questions to see your score.
Recommended next step after MC checkpoint

Complete the 25 multiple choice questions to unlock a sharper next move. The short-answer section below is separate practice.

Why this won

Back to module overview Start mixed review
Part A, Multiple Choice (1 mark each, 25 marks total)
1 In a network flow diagram, the source is the vertex that: L1
A, has flow leaving the network. The source is where flow begins.
2 The sink is the vertex that: L1
C, receives flow from the network. The sink is the destination.
3 A directed edge is shown with: L1
B, an arrow. Directed edges use arrows.
4 The capacity on an edge tells us: L1
D, the maximum flow allowed on that edge. Capacity is an upper limit.
5 A path from S to T must: L1
C, follow the direction of arrows. Valid directed paths follow arrows.
6 An edge with capacity 12 and flow 12 is: L2
A, saturated. Flow equals capacity.
7 An edge with capacity 12 and flow 8 has spare capacity: L2
D, $4$. $12 - 8 = 4$.
8 If path S-A-T has capacities 9 and 5, the most that can be sent is: L2
B, $5$. The bottleneck is the smallest capacity.
9 After sending flow along a path, you usually: L2
A, reduce remaining capacities on used edges. Used capacity is no longer available.
10 If two independent routes can carry 6 and 8 units, their total possible flow is: L2
C, $14$. $6 + 8 = 14$.
11 A flow cannot exceed: L2
D, any cut capacity separating source and sink. Every cut is an upper bound.
12 The max-flow min-cut theorem says: L3
B, maximum flow equals minimum cut capacity. The theorem links max flow to min cut.
13 A cut with outgoing capacities 7, 4 and 6 has capacity: L3
C, $17$. Add crossing capacities.
14 If a network has a cut capacity of 18, then maximum flow is at most: L3
A, $18$. A cut gives an upper bound.
15 If you find a feasible flow of 18 and a cut of capacity 18, what can you conclude? L3
B, The maximum flow is 18. The flow reaches the upper bound.
16 A demand of 20 can be met only if: L3
D, maximum flow is at least 20. Capacity must meet or exceed demand.
17 A table row S to A, capacity 10, should be drawn as: L1
A, $S \to A$ labelled 10. The arrow follows the row direction.
18 Which vertex has no outgoing edges in a completed flow network? L1
C, The sink. The sink is the final destination.
19 A valid flow at an intermediate vertex should conserve flow, meaning: L2
B, inflow equals outflow. Flow conservation balances intermediate vertices.
20 At vertex A, inflow is 11 and outgoing flows are 6 and 5. Is flow conserved? L2
D, Yes. Outgoing total is $11$.
21 If minimum cut capacity is 23 and demand is 25, the demand is: L3
C, impossible. Max flow cannot exceed 23.
22 A cut separates $S,A$ from $B,T$. Count only edges: L3
A, from the source side to the sink side. Directed cut capacity counts forward crossing edges.
23 The bottleneck on capacities 15, 9, 11 is: L2
D, $9$. The smallest capacity controls the path.
24 If a flow value is 12 but there is still an augmenting path with spare capacity 3, the flow: L3
B, is not maximum yet. An augmenting path means more flow can be added.
25 Network flow models are useful for: L1
C, moving limited resources through connected routes. They model capacity-limited movement.
Part B, Short Answer (separate practice)
0 L1
A table lists S to A capacity 10, S to B capacity 8, A to T capacity 7, B to T capacity 6.
(a) List all directed edges.
(b) Identify the source and sink.
(a) $S \to A$, $S \to B$, $A \to T$, $B \to T$.
(b) Source $S$, sink $T$.
1 L2
A path S-A-T has capacities 12 and 9.
(a) Find the bottleneck capacity.
(b) State remaining capacities if 9 units are sent.
(a) Bottleneck is 9.
(b) Remaining capacities are 3 and 0.
2 L2
At vertex C, incoming flows are 5 and 7. Outgoing flows are 4 and 8.
(a) Find total inflow and outflow.
(b) Decide whether flow is conserved.
(a) Both totals are 12.
(b) Yes, flow is conserved.
3 L3
A cut has forward crossing capacities 6, 10 and 5.
(a) Find the cut capacity.
(b) What does this say about maximum flow?
(a) Cut capacity is 21.
(b) Maximum flow is at most 21.
4 L3
A feasible flow of 16 is found. A cut of capacity 16 is also found.
(a) State the maximum flow.
(b) Explain why.
(a) Maximum flow is 16.
(b) Flow equals the cut upper bound.
5 L3
A network has maximum flow 28 and demand 30.
(a) Can demand be met?
(b) How much extra capacity is needed at minimum?
(a) No.
(b) At least 2 units.
6 L2
Two independent paths from S to T have bottlenecks 8 and 11.
(a) Find total flow through both paths.
(b) Name one condition needed.
(a) Total flow is 19.
(b) The paths must not compete for the same saturated edge.
7 L1 & L3
Explain the difference between a path and a cut.
(a) Define a path.
(b) Define a cut.
(a) A path is a directed route from source to sink.
(b) A cut separates source from sink and limits flow.
Network Flow Complete

You've worked through all 3 lessons and the full topic test for Network Flow. Mark as complete to record your progress.