General Mathematics · Past QCAA questions All simple familiar questions
2020 · Paper 1 · Simple familiar

Question 21

[5 marks] Scientific calculator
Topic guidesPremiumTopic guide 14 · Minimum cut, maximum flow
Game plansPremiumGame plan 7 · Network optimisation
The question

This network shows the maximum number of supplies (in tonnes) that can be transported from a warehouse to a cyclone shelter along each road each day during an emergency.

50203040204030 ABC WarehouseCyclone shelter

Note: If you make a mistake in the network, cancel it by ruling a single diagonal line through your work and use the additional network on page 18 of this question and response book.

a)

Use the ‘maximum flow, minimum cut’ theorem to determine the maximum amount of supplies that can reach the cyclone shelter each day.

[3 marks]
b)

During a cyclone, the intersection at vertex A is damaged and no longer allows for any supplies to pass through it. What is the new maximum amount of supplies each day that can reach the cyclone shelter?

[2 marks]
Watch the situation first

Eight ways to cut the warehouse off, and the smallest one is the answer

Each cut puts the warehouse on one side and the shelter on the other. Watch every cut get added up, then watch what closing A does.

Each road carries at most its capacity, in tonnes a day Try every cut, and count only roads heading to the shelter The smallest cut is the most that can get through b) Close A, then recalculate every cut Cut 1, warehouse side {W}: 50 + 30 + 40 = 120 Cut 2, warehouse side {W, C}: 50 + 30 + 20 + 30 = 130 Cut 3, warehouse side {W, B}: 50 + 40 + 40 = 130 C → B points back towards the warehouse side, so it adds 0 Cut 4, warehouse side {W, B, C}: 50 + 40 + 30 = 120 Cut 5, warehouse side {W, A}: 20 + 30 + 40 = 90 Cut 6, warehouse side {W, A, B}: 20 + 40 + 40 = 100 C → B points back towards the warehouse side, so it adds 0 Cut 7, warehouse side {W, A, B, C}: 20 + 40 + 30 = 90 Cut 8, warehouse side {W, A, C}: 20 + 30 + 20 + 30 = 100 Minimum cut 90, so the maximum flow is 90 tonnes per day blue: one flow that delivers 90, as flow / capacity on each road Cut 7 again, warehouse side {W, A, B, C}: 0 + 40 + 30 = 70 No cut is smaller than 70, so the new maximum flow is 70 tonnes per day Warehouse Cyclone shelter A B C (W) 50203040204030 20 / 5020 / 2030 / 3040 / 4010 / 2040 / 4030 / 30 003040204030 a) cut: tonnes b) cut: tonnes 1: 120 2: 130 3: 130 4: 120 5: 90 6: 100 7: 90 8: 100 5: 90 ◀ 7: 90 ◀ 1: 70 2: 80 3: 80 4: 70 5: 70 6: 80 7: 70 8: 80

Every tonne has to cross every cut, so no flow can beat the smallest cut. Closing A changes every cut, so you recalculate them all and find the new smallest one.

Now for the mathematics

Find all eight cuts yourself, then close A and find them again

The warehouse is always on its own side of the cut and the shelter always on the other. Choose which of A, B and C go with the warehouse. The network colours the roads you count, the table records each cut you find, and once you have all eight the smallest one is your answer.

On the warehouse side with W
Part b)
500 200 3040204030 ABC WarehouseCyclone shelter
warehouse side counted, heads to the shelter side crosses backwards, adds 0
CutWarehouse sidea)b)

C → B crosses this cut, but it runs from the shelter side back to the warehouse side, so it adds 0. Supplies on that road are heading away from the shelter as far as this cut is concerned. Counting it would give instead of .

That’s all eight cuts. The smallest is , from , so the maximum flow is tonnes per day. Now close intersection A for part b).

All eight cuts again, with A closed. The smallest is now , from , so the new maximum flow is tonnes per day.

With A closed, W → A and A → S carry 0. An easy slip is to take 50 off 90 and answer 40, but the 50 road was never in a minimum cut. Taking 20 off 90 lands on the right number by luck, and the mark is for recalculating the cuts, so show them.

QCAA marking guide · 5 marks

List the cuts, add them up, then do it again without A

Try each step yourself before you reveal it. Part a) has a mark for finding all the cuts, one for adding them and one for the answer. Part b) has a mark for recalculating and one for the new answer.

Step 1 · part a)1 mark

Call the warehouse W and the cyclone shelter S. A cut splits the vertices into the warehouse’s side and the shelter’s side. Each of A, B and C goes on one side or the other, so there are $2\times2\times2=8$ cuts. List them, and for each one note the roads that cross from the warehouse side to the shelter side.

CutWarehouse sideRoads counted
1WW→A, W→B, W→C
2W, CW→A, W→B, C→B, C→S
3W, BW→A, B→S, W→C (C→B points back, not counted)
4W, B, CW→A, B→S, C→S
5W, AA→S, W→B, W→C
6W, A, BA→S, B→S, W→C (C→B points back, not counted)
7W, A, B, CA→S, B→S, C→S
8W, A, CA→S, W→B, C→B, C→S

The guide draws cuts 1 to 7 as numbered curves across its diagram. Its notes accept any 7 or 8 valid cuts, so either list earns the mark. Drawing curves is fine, as long as each one separates the warehouse from the shelter completely.

Marker: correctly identifies all the possible cuts

Step 2 · part a)1 mark

Add the capacities of the counted roads for every cut.

CutCapacity (tonnes per day)
150 + 30 + 40 = 120
250 + 30 + 20 + 30 = 130
350 + 40 + 40 = 130
450 + 40 + 30 = 120
520 + 30 + 40 = 90
620 + 40 + 40 = 100
720 + 40 + 30 = 90
820 + 30 + 20 + 30 = 100

In cuts 3 and 6 the road C → B crosses the cut backwards, from the shelter side to the warehouse side. It adds nothing. Counting its 20 would make cut 3 into 150 and cut 6 into 120.

Marker: correctly calculates the flow across all the cuts

Step 3 · part a)1 mark

The theorem says the maximum flow equals the capacity of the minimum cut.

The capacity of the minimum cut is 90, so the maximum flow of this network is 90 tonnes per day.

As a check, 90 really can get through: send 20 along W → A → S, 30 from W to B, 40 from W to C, then 10 of that along C → B and 30 along C → S. B then passes its 40 on to S, and the shelter receives $20+40+30=90$. Follow-through applies if an earlier cut total had a slip.

Marker: states maximum flow across minimum cut

Step 4 · part b)1 mark

Nothing can pass through A, so the roads W → A and A → S now have capacity 0. Recalculate the same cuts.

CutCapacity with A closed
10 + 30 + 40 = 70
20 + 30 + 20 + 30 = 80
30 + 40 + 40 = 80
40 + 40 + 30 = 70
50 + 30 + 40 = 70
60 + 40 + 40 = 80
70 + 40 + 30 = 70
80 + 30 + 20 + 30 = 80

The guide writes this in one line: cuts 1 to 7 change to 70, 80, 80, 70, 70, 80 and 70. Showing at least the minimum cut recalculated is what earns this mark. Writing $90-20=70$ gets the right number without recalculating anything.

Marker: recalculates flow across minimum cut

Step 5 · part b)1 mark

The smallest recalculated cut is 70, so that is the new maximum flow.

a) 90 tonnes per day · b) 70 tonnes per day

A flow of 70 still gets through without A: 30 along W → B, 40 along W → C, then 10 of that on to B along C → B and 30 along C → S, and B sends its 40 to the shelter. If your part a) cuts had a slip, a consistent recalculation here may still earn credit.

Marker: states new maximum flow

Putting it all together

Each phrase of the question gave you something

“the maximum number of supplies (in tonnes) … along each road each day”
The numbers are capacities, and the answer is in tonnes per day.
“from a warehouse to a cyclone shelter”
The warehouse is the source and the shelter is the sink. Every cut separates them.
The arrows on the network
Only roads crossing towards the shelter side count. C → B is the one that sometimes crosses backwards.
“Use the ‘maximum flow, minimum cut’ theorem”
List all the cuts and total each one. The smallest total, 90, is the maximum flow.
“no longer allows for any supplies to pass through it”
Both roads at A drop to 0. Recalculate the cuts with those zeros.
“What is the new maximum amount … each day”
State the new minimum cut as a flow with units: 70 tonnes per day.
What makes this simple familiar

The question names the theorem for you, and the network is small: three middle vertices, so eight cuts at most. There is no flow to route and no decision to justify, only a list to make and add up, then the same list again with two roads set to 0.

If I had to guess where you might lose marks, it would be the first mark. The 2020 subject report said the theorem “requires the correct identification of all the possible cuts for a small-scale network flow problem”, and it listed the difference between minimum cut and maximum flow as a practice to strengthen. Miss a cut and you can’t be sure your smallest is the smallest. The other easy slip is the road C → B: in two of the cuts it points back towards the warehouse side, and it adds nothing there.

Only mark this done when you could do it without help. Reading the solution does not count.

Back to the index

Question wording and marking-guide steps are from the 2020 QCAA General Mathematics external assessment, © State of Queensland (QCAA) 2020, licensed under CC BY 4.0, and have been adapted. Tangent Tuition is not affiliated with the QCAA.

Spot a mistake on this page? Report it