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
B a GST-inclusive price
C a time-zone conversion
D a latitude coordinate
A, has flow leaving the network. The source is where flow begins.
2 The sink is the vertex that: L1
A a GST-inclusive price
B a time-zone conversion
C receives flow from the network
D a latitude coordinate
C, receives flow from the network. The sink is the destination.
3 A directed edge is shown with: L1
A a GST-inclusive price
B an arrow
C a time-zone conversion
D a latitude coordinate
B, an arrow. Directed edges use arrows.
4 The capacity on an edge tells us: L1
A a GST-inclusive price
B a time-zone conversion
C a latitude coordinate
D the maximum flow allowed on that edge
D, the maximum flow allowed on that edge. Capacity is an upper limit.
5 A path from S to T must: L1
A a GST-inclusive price
B a time-zone conversion
C follow the direction of arrows
D a latitude coordinate
C, follow the direction of arrows. Valid directed paths follow arrows.
6 An edge with capacity 12 and flow 12 is: L2
A saturated
B a GST-inclusive price
C a time-zone conversion
D a latitude coordinate
A, saturated. Flow equals capacity.
7 An edge with capacity 12 and flow 8 has spare capacity: L2
A a GST-inclusive price
B a time-zone conversion
C a latitude coordinate
D $4$
D, $4$. $12 - 8 = 4$.
8 If path S-A-T has capacities 9 and 5, the most that can be sent is: L2
A a GST-inclusive price
B $5$
C a time-zone conversion
D a latitude coordinate
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
B a GST-inclusive price
C a time-zone conversion
D a latitude coordinate
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
A a GST-inclusive price
B a time-zone conversion
C $14$
D a latitude coordinate
C, $14$. $6 + 8 = 14$.
11 A flow cannot exceed: L2
A a GST-inclusive price
B a time-zone conversion
C a latitude coordinate
D any cut capacity separating source and sink
D, any cut capacity separating source and sink. Every cut is an upper bound.
12 The max-flow min-cut theorem says: L3
A a GST-inclusive price
B maximum flow equals minimum cut capacity
C a time-zone conversion
D a latitude coordinate
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
A a GST-inclusive price
B a time-zone conversion
C $17$
D a latitude coordinate
C, $17$. Add crossing capacities.
14 If a network has a cut capacity of 18, then maximum flow is at most: L3
A $18$
B a GST-inclusive price
C a time-zone conversion
D a latitude coordinate
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
A a GST-inclusive price
B The maximum flow is 18
C a time-zone conversion
D a latitude coordinate
B, The maximum flow is 18. The flow reaches the upper bound.
16 A demand of 20 can be met only if: L3
A a GST-inclusive price
B a time-zone conversion
C a latitude coordinate
D maximum flow is at least 20
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
B a GST-inclusive price
C a time-zone conversion
D a latitude coordinate
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
A a GST-inclusive price
B a time-zone conversion
C The sink
D a latitude coordinate
C, The sink. The sink is the final destination.
19 A valid flow at an intermediate vertex should conserve flow, meaning: L2
A a GST-inclusive price
B inflow equals outflow
C a time-zone conversion
D a latitude coordinate
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
A a GST-inclusive price
B a time-zone conversion
C a latitude coordinate
D Yes
D, Yes. Outgoing total is $11$.
21 If minimum cut capacity is 23 and demand is 25, the demand is: L3
A a GST-inclusive price
B a time-zone conversion
C not guaranteed possible
D a latitude coordinate
C, not guaranteed possible. 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
B a GST-inclusive price
C a time-zone conversion
D a latitude coordinate
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
A a GST-inclusive price
B a time-zone conversion
C a latitude coordinate
D $9$
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
A a GST-inclusive price
B is not maximum yet
C a time-zone conversion
D a latitude coordinate
B, is not maximum yet. An augmenting path means more flow can be added.
25 Network flow models are useful for: L1
A a GST-inclusive price
B a time-zone conversion
C moving limited resources through connected routes
D a latitude coordinate
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.