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 has flow arriving and none leaving
C lies on the minimum cut
D has the largest capacity of any vertex
A, has flow leaving the network. The source is where flow begins.
2 The sink is the vertex that: L1
A sends flow out into the network
B has equal inflow and outflow
C receives flow from the network
D can be any intermediate vertex
C, receives flow from the network. The sink is the destination.
3 A directed edge is shown with: L1
A a dashed line
B an arrow
C a double line
D a line with no label
B, an arrow. Directed edges use arrows.
4 The capacity on an edge tells us: L1
A the actual flow currently on that edge
B the physical length of that edge
C the number of paths using that edge
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 visit every vertex in the network
B use only the largest-capacity edges
C follow the direction of arrows
D avoid every saturated edge
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 unused
C over capacity
D certain to lie on the minimum cut
A, saturated. Flow equals capacity.
7 An edge with capacity 12 and flow 8 has spare capacity: L2
A $8$
B $12$
C $20$
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 $9$
B $5$
C $14$
D $4$
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 increase the remaining capacities on used edges
C delete every vertex on that path
D reset all other paths to zero flow
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 $6$
B $8$
C $14$
D $48$
C, $14$. $6 + 8 = 14$.
11 A flow cannot exceed: L2
A the number of vertices in the network
B the capacity of the largest single edge
C the number of paths from source to sink
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 maximum flow equals the largest cut capacity
B maximum flow equals minimum cut capacity
C minimum flow equals the minimum cut capacity
D maximum flow equals the sum of all cut capacities
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 $6$
B $7$
C $17$
D $11$
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 $9$
C $19$
D $36$
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 The maximum flow must be more than 18
B The maximum flow is 18
C The cut cannot be a minimum cut
D Nothing, the two numbers are unrelated
B, The maximum flow is 18. The flow reaches the upper bound.
16 A demand of 20 can be met only if: L3
A the network has at least 20 edges
B every edge has capacity at least 20
C the minimum cut is at most 20
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 \to S$ labelled 10
C an undirected edge $S$–$A$ labelled 10
D $S \to A$ labelled with its flow instead of 10
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 The source
B Every intermediate vertex
C The sink
D The vertex with the largest capacity
C, The sink. The sink is the final destination.
19 A valid flow at an intermediate vertex should conserve flow, meaning: L2
A inflow exceeds outflow
B inflow equals outflow
C outflow exceeds inflow
D inflow and outflow both equal the capacity
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 No, the inflow is too large
B No, the outflow is too large
C Cannot tell without the edge capacities
D Yes
D, Yes. Outgoing total is $11$.
21 If minimum cut capacity is 23 and demand is 25, the demand is: L3
A possible, because 25 is close to 23
B possible if an extra path is drawn without changing any capacity
C impossible, because the maximum flow is only 23
D possible only if the flow is split evenly between routes
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
B from the sink side to the source side
C crossing the cut in either direction
D that are already saturated
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 $15$
B $11$
C $35$
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 is already the maximum
B is not maximum yet
C must be reduced to 9
D has exceeded the minimum cut
B, is not maximum yet. An augmenting path means more flow can be added.
25 Network flow models are useful for: L1
A putting a list of numbers into order
B finding the shortest single route between two towns
C moving limited resources through connected routes
D scheduling tasks that must follow one another
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.