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

Question 21

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

The road network shows the number of vehicles per hour travelling from the airport to the town centre.

cut X Airport College Bridge Town centre Showground 200 150 50 100 120 140 80
a)

Determine the capacity of cut X.

[1 mark]
b)

Determine the maximum flow from the airport to the town centre.

[2 marks]
c)

During a weather emergency, all roads to and from the bridge are closed to vehicles. Determine the maximum flow from the airport to the town centre during this time.

[1 mark]
Watch the situation first

Count only the roads that leave the airport side

Watch cut X get counted, one road at a time. Then watch the smallest cut set the maximum flow, and the network shrink when the bridge closes.

a) Count the roads that leave the airport side b) The smallest cut sets the maximum flow c) Close every road to and from the bridge cut X airport side town side minimum cut Airport College Town centre Showground Bridge 200 120 80 150 50 100 140 170 | 200 120 | 120 80 | 80 130 | 150 50 | 50 100 | 100 80 | 140 Airport to College leaves the airport side, so count 200 College to Bridge runs back into the airport side, so leave out 50 Bridge to the town centre also leaves, so count 100 Bridge to Showground leaves too, so count 140 Capacity of cut X = 200 + 100 + 140 = 440 vehicles per hour Every vehicle uses one of the three roads into town: 120 + 100 + 80 = 300 Flow | capacity: 170 + 130 = 300 leave, 120 + 100 + 80 = 300 arrive Maximum flow = minimum cut = 300 vehicles per hour Only one route is left: Airport, College, Town centre Its narrowest road wins: min(200, 120) = 120 vehicles per hour (its arrow points from the town side back towards the airport side) (the flows from the marking guide fit every capacity, and 300 really gets through)

A cut counts only the roads leaving the airport side. Every cut caps the flow, so the smallest cut is the maximum flow.

Now for the mathematics

Make your own cuts and hunt for the smallest

The airport is always on the airport side and the town centre on the town side. Put each of the other three places on a side. Roads that leave the airport side are counted in orange. Roads that come back are shown in blue and left out. Then test yourself on the slip in each part.

Airport College Bridge Town centre Showground 200 150 50 100 120 140 80
Roads to and from the bridge
Capacity of this cut

Check an easy slip
The question asks

Pick one of the answers. Each wrong one comes from a real number on the network, used in the wrong way.

490 includes the 50 from College to Bridge. That road crosses cut X from the town side back into the airport side, so it is left out. Only roads leaving the airport side count.

That’s it. Cut X crosses three roads that leave the airport side, so its capacity is $200+100+140=440$ vehicles per hour.

300 is the maximum flow from part b). Part a) is about one particular cut, so add the roads cut X crosses in the forward direction: $200+100+140$.

440 is the capacity of cut X. A smaller cut exists: the three roads into the town centre carry only $120+100+80=300$. The maximum flow equals the smallest cut.

That’s it. Every vehicle must use one of the three roads into the town centre, which carry at most $120+100+80=300$, and the marking guide’s flows show that 300 really gets through.

350 is everything that can leave the airport, $200+150$. Further along the roads narrow, and the three roads into the town centre carry only 300 between them.

200 is the road from the airport to College. The next road, College to the town centre, carries only 120, so every vehicle is held to that.

That’s it. Only Airport, College, Town centre is left, and its narrowest road carries 120 vehicles per hour.

300 is the maximum flow with every road open. Closing the bridge removes four roads, so the flow has to drop.

QCAA marking guide · 4 marks

One cut, one minimum cut, one route left

Try each step yourself before you reveal it. Parts a) and c) are one mark each. Part b) has a mark for the method and one for the maximum flow.

Step 1 · part a)1 mark

Cut X crosses four roads. The airport and Bridge are on the airport side. Count a road only if its arrow points from the airport side to the town side.

$$\text{Capacity of cut X}=200+100+140=440\text{ vehicles per hour}$$

The 50 road points from College to Bridge, back into the airport side, so it is left out. Adding it gives 490, the slip this cut is built to catch.

Marker: correctly determines the capacity of cut X

Step 2 · part b)1 mark

Show a method on the network. The marking guide’s sample writes the flow next to each capacity, as flow | capacity, so that no road carries more than it can and every vehicle that arrives at a junction leaves it. Its notes also accept the minimum cut, drawn dashed here.

Airport College Bridge Town centre Showground minimum cut 170 | 200 130 | 150 50 | 50 100 | 100 120 | 120 80 | 140 80 | 80

Other ways of recording augmenting paths are also accepted. Whatever you use, it has to be visible on the page.

Marker: correctly identifies an appropriate method

Step 3 · part b)1 mark

Add what arrives at the town centre, or the capacity of the minimum cut. They agree.

$$\text{Maximum flow}=120+100+80=300\text{ vehicles per hour}$$

As a check, $170+130=300$ leave the airport. Follow-through applies, so a slip in your flows can still earn this mark if your total matches your own working.

Marker: identifies maximum flow

Step 4 · part c)1 mark

Cross out every road that touches Bridge: 150, 50, 100 and 140. Showground can still send 80 to the town centre, but nothing can reach Showground. The only route left is Airport, College, Town centre.

$$\min(200,\,120)=120$$

Maximum flow during the emergency = 120 vehicles per hour

A route can carry no more than its narrowest road. Give the units, as the sample response does.

Marker: correctly determines the maximum flow

Putting it all together

Each phrase of the question gave you something

“the number of vehicles per hour”
The capacities, and the unit for every answer.
“from the airport to the town centre”
The airport is the source and the town centre is the sink. The arrows show which way each road runs.
“the capacity of cut X”
Add the roads crossing cut X from the airport side to the town side. The 50 runs back, so leave it out.
“the maximum flow” [2 marks]
Show a method, flows on the network or the minimum cut, then state 300 vehicles per hour.
“all roads to and from the bridge are closed”
Delete four roads. One route survives, and its narrowest road, 120, sets the flow.
What makes this simple familiar

The network is small, the cut for part a) is drawn for you, and the minimum cut is easy to spot once you look at the roads into the town centre. With only five places there are just eight possible cuts, so you could even list them all.

If I had to guess where you might lose marks, it would be the 50 in part a). It is the only road that crosses cut X the wrong way, and it is there to see whether you check the arrows. The 2023 subject report made no specific comment on this question, so that is my reading of the paper. In part b), resist reusing 440. Cut X is just one cut and a smaller one exists, and the maximum flow needs a method shown on the page.

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 2023 QCAA General Mathematics external assessment, © State of Queensland (QCAA) 2023, 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