Game plan 7 · Unit 4 Topics 4 and 5
Network optimisation
Four routines that each get a best value out of a network: the least cable that connects everything, the least time a project can take, the most that can flow through, and the best way to pair people with tasks.
Reach for it when the question wants something made as small or as large as possible across a whole network or a whole group. A route from one place to another, or a round trip through every vertex, belongs to Game plan 6.
Every external exam from 2020 to 2025 had a tree question, a critical path question and an assignment question, and four of the six had a flow question. Trees and critical paths (Unit 4 Topic 4) carried 50 short-response marks across the six papers. Flow and assignment (Unit 4 Topic 5) carried 45.
Part 1
Find what the question wants the best of
All four routines optimise something, and the stems use words like minimum, shortest and optimal for all of them. The routine depends on what is being made best, so look for that before you draw anything.
Ask this first
What does the question want the best of?
The least total length or cost that still connects everything
“the shortest length of cable necessary to connect all buildings” (2021), “while still allowing visitors to access every key location” (2022), “the minimum total cable length required to connect all stations” (2023).
→ Game plan 7.1, a minimum spanning tree.
The least time for a project, or which jobs cannot slip
“Determine the critical activities and minimum completion time” (2023), “Determine the shortest completion time for the project” (2021), “float time”.
→ Game plan 7.2, critical path analysis.
The most that can get through
“the maximum flow from the airport to the town centre” (2023), “the ‘maximum flow, minimum cut’ theorem” (2020), a cut drawn across the network.
→ Game plan 7.3, maximum flow and cuts.
The best pairing, one each
“if each contractor is allocated one task” (2020), “Use the Hungarian algorithm” (2021, 2022, 2023), a square table of costs, times or distances.
→ Game plan 7.4, the Hungarian algorithm.
The trap: “shortest” on its own names nothing
“The shortest length of cable necessary to connect all buildings” is a tree, because it has to reach every building. “The current shortest road route between Manon and Farra” (2022) is a shortest path between two places, and that is Game plan 6. “The shortest completion time for the project” is critical path analysis, and the answer is the longest path through the network.
A shortest path is one journey. A minimum spanning tree connects every vertex and never contains a cycle.
Underline the words that say what is being made best, and write the routine’s name in the margin before you draw anything.
Part 2
The four game plans
None of the four routines is in the formula book, and none takes long once you know it. The marking guides give a mark for most steps, so show each one.
Minimum spanning tree
Connect every vertex for the least total.
- 1Count the vertices and write down how many edges the tree needs, $v-1$.
- 2Find the tree. Take the cheapest edge first and skip any edge that would close a cycle. Write each edge down as you take it.
- 3Mark the tree on the diagram in blue or black pen with a thick or squiggly line. Check the edge count, that every vertex is in, and that there is no cycle.
- 4Add the lengths of the tree edges and give the unit.
- 5Do what the stem asks next: a cost against a budget, a saving, or a missing edge. Part 3 has all three.
- 6Compare your figure with the one in the stem and give the verdict in the question’s words.
Growing the tree outward from one vertex also works. The syllabus names no method, so use the one you trust.
Critical path analysis
Minimum time, critical activities and float.
- 1If you get a table, draw the network first: one start node, one finish node, each activity on an arc leaving the node where all its prerequisites arrive. Read it back against the table.
- 2Forward scan from 0, taking the largest where arcs meet. The finish node holds the minimum completion time.
- 3Backward scan from that time, taking the smallest where arcs split. You should arrive back at 0.
- 4Write an EST and an LST for every activity, not just the critical ones.
- 5Critical activities have EST = LST. For the rest, $\text{float}=\text{LST}-\text{EST}$, or $\text{LFT}-\text{EST}-\text{duration}$.
- 6Answer in context with units. For a claim about staff, count how many activities must run at the same time and compare.
Maximum flow
The most that can get from the source to the sink.
- 1Find the source and the sink. If the pipes come as a table, draw the network first: rows are “from”, columns are “to”.
- 2Count the middle nodes and list every source side. Three middle nodes give $2\times 2\times 2=8$ cuts.
- 3For each cut, add only the edges that run from the source side to the sink side. Leave out any edge pointing back.
- 4Name the smallest total as the minimum cut and write “maximum flow = minimum cut = …” with units.
- 5If the network changes, recalculate every cut. An upgrade helps only if the edge is on every minimum cut.
Hungarian algorithm
One each, for the smallest (or largest) total.
- 1Build the square matrix, one group as rows and the other as columns. For a maximum, subtract every entry from the largest entry first.
- 2Row reduction: subtract the smallest value in each row from every entry in that row. Write the new matrix.
- 3Column reduction: subtract the smallest value in each column from every entry in that column. Write the new matrix.
- 4Cover all the zeros with the fewest straight lines and write the count against the size, as in “2 < 3, so adjust”.
- 5If there are too few lines, subtract the smallest uncovered value from every uncovered entry, add it to every entry covered twice, and cover again.
- 6Pick one zero in each row and each column, state who does what, and add the original values for the total.
Every marking guide from 2020 to 2024 accepted the columns reduced before the rows. The assignment comes out the same either way.
Part 3
The tree is only the first step
A tree is a connected graph with no cycles. A spanning tree is a subgraph that is a tree and includes every vertex. A minimum spanning tree is a spanning tree whose total weight is as small as possible, and there may be more than one. 2020 Q7 had three, all 12 km, and every one is a correct answer.
The edge count that acts as a formula
A tree with $v$ vertices has exactly $v-1$ edges. Too many means a cycle is still in. Too few means a vertex has been cut off.
The right count does not prove you have a tree. A triangle plus a fourth vertex on its own has $3=4-1$ edges, and it has a cycle and is not connected. Check every vertex is joined and there is no cycle as well.
Three shapes in Paper 2, and what the last line says
The tree on its own has never been the final answer to a short-response question. Four of the five tree questions from 2020 to 2025 ended in a decision against a figure in the stem.
| Shape | What the stem gives | After the tree |
|---|---|---|
| Cost against a budget (2021 P2 Q2) | A cost per metre and a budget | Multiply the tree total by the rate, compare with the budget, then decide. |
| Saving (2022 P2 Q5) | A yearly cost per metre and a claimed saving | Find the total of every path and the tree total. The saving is the cost of the difference. |
| Unknown edge (2023 P2 Q3) | One edge with no length, and how the minimum total changes when it is added | Find the tree without it, apply the change the stem gives, and work back to the missing length. |
Justify a tree with the definition
2025 Paper 1 Q23a gave two marks for saying why a subgraph is not a tree. Name the defining property (a tree has no cycles), point to the evidence in this graph (these three edges form a cycle), and add the edge count as a second check. For a claim such as “less than 25 m of cables”, give the minimum total, compare it with the claimed figure, then give the verdict. Calculate, compare, conclude.
Part 4
Forward take the largest, backward take the smallest
The syllabus uses activity on arc. Each arrow is an activity, labelled with its letter and duration, and each circle is an event. After the scans, the left half of a node holds the earliest time and the right half the latest.
| Rule | What you do | Why |
|---|---|---|
| Forward scan | An activity’s EST is the largest earliest finishing time of everything before it. | It cannot start until every prerequisite is finished, so the slowest one decides. |
| At the finish node | The minimum completion time is the largest earliest finishing time of all. | The project is not done until its last activity is. |
| Backward scan | An activity’s LST is the latest time at its end node minus its duration. Where arcs split, keep the smallest. | Starting any later would delay whichever successor is tightest. |
| At the start of the backward scan | Begin from the minimum completion time you just found. | The latest acceptable finish is the earliest possible finish. |
Float, and three ways of saying critical
$$\text{float}=\text{LST}-\text{EST}=\text{LFT}-\text{EST}-\text{duration}$$
Use whichever numbers you already have. The 2024 and 2025 marking guides both used the second form, and 2025 accepted either. An activity is critical, it has zero float, and its EST equals its LST: a question that tells you one of these has told you all three. 2023 Q8 said P and Q were critical, so Q’s EST and LST were both 3 with no scan needed. Only 49.1% got it.
Building the network from a prerequisite table
- 1Draw one start node. Every activity with no prerequisite leaves it.
- 2An activity leaves the node where all of its prerequisites arrive.
- 3Activities with exactly the same prerequisite list leave the same node.
- 4Any activity that is not a prerequisite for anything arrives at the one finish node.
- 5Put an arrowhead on every arc and label it with its letter and duration, as in “A, 12”. The syllabus excludes dummy activities, so you never need one.
- 6Read the diagram back into a table and compare it with the prerequisite column before you scan.
Part 5
List every cut, then take the smallest
| Term | Meaning |
|---|---|
| Source | The node where the flow starts. Nothing flows into it. |
| Sink | The node where the flow ends. Nothing flows out of it. |
| Cut | A line across the network that completely separates the source from the sink. |
| Capacity of a cut | The total capacity of the edges it crosses, counting only edges directed from the source side to the sink side. |
| Maximum flow | The largest amount that can travel from source to sink. It equals the capacity of the minimum cut. |
Two rules for every cut
It must separate. The source is on one side and the sink on the other. If any path gets from source to sink without crossing the line, it is not a cut. That was 2021 Q23a, “Explain which dashed line … is not a valid cut.”
Only forward edges count. An edge running from the sink side back to the source side adds nothing. 2021 Q7, 2021 Q23 and 2023 Q21 each put a backward edge on a cut drawn for you.
The 2025 syllabus limits these problems to 8 possible cuts, so you can list them all. Each middle node goes on the source side or the sink side, so three middle nodes give $2\times 2\times 2=8$. Write the source sides in order and add the edges leaving each one.
| Source side | Forward edges crossed | Capacity |
|---|---|---|
| S | S→A, S→B | $16+19=35$ |
| S, A | S→B, A→C, A→T | $19+8+4=31$ |
| S, B | S→A, B→C, B→T | $16+10+4=30$ |
| S, C | S→A, S→B, C→A, C→T | $16+19+5+21=61$ |
| S, A, B | A→C, B→C, A→T, B→T | $8+10+4+4=26$ |
| S, A, C | S→B, A→T, C→T | $19+4+21=44$ |
| S, B, C | S→A, B→T, C→A, C→T | $16+4+5+21=46$ |
| S, A, B, C | A→T, B→T, C→T | $4+4+21=29$ |
The minimum cut is 26, so the maximum flow is 26. In a question, give it in the stem’s units.
Upgrades go on every minimum cut
An upgrade helps only if the pipe is on every minimum cut. In 2025 Paper 2 Q3 the maximum flow was 44 from two tied minimum cuts. Upgrading C→D or D→E, each on one of them, left the flow at 44. Only C→E sat on both, and raising it to 25 L/sec gave the target of 45.
Check for ties first. After any change, recalculate every cut, because a different cut can become the new minimum.
Part 6
Rows, columns, cover, and adjust if the lines fall short
An assignment problem is a bipartite graph: workers on one side, tasks on the other, no edge inside a group. The matrix holds the same information, with rows as one group and columns as the other. Be ready to build it yourself from a network (2021) or from coordinates (2024).
Two checkpoints inside the algorithm
After the reductions. Every row has a zero after the row reduction, and every column has one after the column reduction. If not, you subtracted the smallest value in the whole matrix instead of in that row or column.
Before you assign. You must be able to pick one zero in each row and each column at the same time. If two rows can only take the same column, as above, the algorithm is not finished.
The optimal assignment often gives someone their worst option. Both answers above do: row 3 takes 16 in one and row 1 takes 14 in the other. So picking each row’s smallest value is not a method, and when the stem says “Use the Hungarian algorithm” or “Use a matrix method”, the reductions have to be shown.
Maximum assignments and bigger matrices
The algorithm minimises. To maximise, subtract every entry from the largest entry in the matrix, run the algorithm on the new matrix, and take the totals from the original. The 2025 subject report put it this way: “the required optimum assignment could be a minimum or a maximum, and using the Hungarian algorithm is expanded to 3 x 3 up to 5 x 5 square matrices.” Every assignment question from 2020 to 2025 asked for a minimum, and every matrix was 3 × 3. If the entries are profits, points or sales, you are being asked for a maximum, so say in your working that you converted the matrix.
When an entry is unknown
2021 Paper 2 Q6 gave entries in terms of $x$ and the minimum total, 32 km. Where a whole row or column carries the same $x$ term, it cancels when that row or column is reduced. A row of $x+3$, $x+7$ and $x+5$ becomes 0, 4 and 2. In 2021 the $2x$ entries sat in one column, so row reduction left $x-3$ and $x+1$ and the column reduction removed them. Finish the algorithm, total the original entries at the chosen positions, set that equal to the given total, and solve.
Part 7
None of this is in the formula book
The only network entry in the 2025 formula book is Euler’s formula, $v+f-e=2$, which belongs to Game plan 6. There is no entry for trees, critical paths, flow or assignment. Bring these with you.
| Bring it yourself | What it says |
|---|---|
| Tree edge count | A tree on $v$ vertices has $v-1$ edges. |
| Scanning rules | Forward take the largest, backward take the smallest. The backward scan returns to 0. |
| Float | $\text{float}=\text{LST}-\text{EST}$, or $\text{LFT}-\text{EST}-\text{duration}$. |
| Flow | Capacity counts forward edges only. Maximum flow = minimum cut. |
| Hungarian algorithm | Rows, columns, cover, adjust, assign. For a maximum, subtract from the largest entry first. |
If a matrix has to be built from coordinates, as in 2024 Paper 2 Q5, the Earth geometry formulas $D=111.2\times\text{angular distance}$ and $D=111.2\cos\theta\times\text{angular distance}$ are in the book. See Game plan 4.
Part 8
Check yourself inside the question
| Routine | Checkpoint |
|---|---|
| Tree | Exactly $v-1$ edges, every vertex in (including the awkward one joined by one long edge), no cycle. |
| Tree | Total, then convert. Most Paper 2 tree questions want a cost or a saving. A saving comes from the removed length. |
| Critical path | Forward largest, backward smallest. The critical path’s total equals the minimum time, and the backward scan ends at 0. |
| Critical path | Read the diagram back into prerequisites before scanning. Look for a second critical path. |
| Critical path | Float uses LST − EST, or LFT − EST − duration. Never a start minus a finish. |
| Flow | Is every cut valid? Did you list all of them? Only forward edges count. |
| Flow | Take the smallest. After any change, recheck every cut, and put an upgrade on every minimum cut. |
| Hungarian | A zero in every row after the row reduction, and in every column after the column reduction. |
| Hungarian | Lines equal the matrix size before you assign, with one zero per row and column. Totals from the original. |
| All four | Did the stem name a method? Then show its working, even if inspection got you there. Finish with the tree, path, flow or allocation and its value, with units. |
If the answer is a drawing
- •Project networks: one start node, one finish node, an arrow on every arc, no unnecessary nodes, and every arc labelled with its letter and duration.
- •Trees: go over each tree edge in blue or black pen, thick or squiggly, and list the edges in the order you took them. Highlighter disappears on the scan.
- •Cuts: draw the line right across the network and write its capacity beside it.
- •Hungarian: a new matrix for each step, with the covering lines drawn and the count written.
Part 9
How QCAA words it
The middle column quotes the papers. The right-hand column is what to do when you see it.
| Question type | How QCAA words it | Your move |
|---|---|---|
| Affordability | “If the school has a budget of $155 000, evaluate whether they can afford this project.” (2021 P2 Q2) | Tree, then cost, then compare with the budget, then decide. |
| Saving | “believes at least $138 000 can be saved each year if some paths are removed, while still allowing visitors to access every key location using paths” (2022 P2 Q5) | You need both totals. The saving is the cost of the removed length. |
| Missing edge | “except for cable C, which is closed for maintenance. When cable C reopens, the minimum total cable length required to connect all stations will decrease by 1 km.” (2023 P2 Q3) | Find the tree without C, apply the change, work back to C. |
| Tree or not | “Identify the graph that is a spanning tree.” (2022 P1 Q9) “Justify why a subgraph … is not a tree.” (2025 P1 Q23a) | Name the defining property, point to the evidence, add the edge count. |
| Claim about a tree | “evaluate the reasonableness of 2000 km of pipeline being sufficient” (2024 P1 Q23b) | Minimum total, explicit comparison, verdict. |
| Build and scan | “Use the activity table to construct a network diagram, including earliest and latest starting times.” (2021 P1 Q19a) | Activity on arc, one start, one finish. Read it back, then scan both ways. |
| Critical path | “Determine the critical activities and minimum completion time” (2023 P1 Q24b), “Determine the shortest completion time for the project.” (2021 P1 Q19c) | The critical path is the longest path. Give the time with units. |
| Float | “Calculate the float time for activity G.” (2025 P1 Q25d) “The float time, in minutes, for the non-critical activity of this project network is” (2022 P1 Q1) | LST − EST, or LFT − EST − duration. |
| Critical by definition | “Activities P and Q are the critical activities for a project.” … “What are the earliest starting time (EST) and latest starting time (LST) for Activity Q?” (2023 P1 Q8) | Critical means zero float, so EST = LST. No scan needed. |
| Staffing | “The owner believes that this project can be completed in minimal time with only three employees. Evaluate the reasonableness of this belief.” (2020 P2 Q6) | The scans are half of it. Count the activities that must run at once and compare. |
| Minimum among drawn cuts | “Which cut (C1, C2, C3 or C4) could be used to determine the maximum flow from the source to the sink in this network?” (2021 P1 Q7) | Work out each capacity with forward edges only, and take the smallest. |
| Valid cut | “Explain which dashed line … is not a valid cut.” (2021 P1 Q23a) | Find the line that leaves a source-to-sink path uncut. |
| Maximum flow | “Use the ‘maximum flow, minimum cut’ theorem to determine the maximum amount of supplies that can reach the cyclone shelter each day.” (2020 P1 Q21a) | List every cut with its capacity, take the smallest, give units. |
| Changed network | “all roads to and from the bridge are closed to vehicles” (2023 P1 Q21c) | Set those edges to 0 and recheck every cut. |
| Upgrade | “An engineer will upgrade only one pipe to change the maximum flow from A to E to 45 L/sec.” (2025 P2 Q3) | Check for tied minimum cuts. The pipe must be on every one. |
| Named method | “Use a matrix method” (2020 P2 Q5), “Use the Hungarian algorithm” (2021, 2022, 2023) | Show every matrix. Inspection can lose the reduction marks. |
| Assignment by inspection | “Which athlete should complete each stage of a future triathlon relay to minimise the total completion time?” (2025 P1 Q10) | A 3 × 3 has six assignments. Total them, or run the algorithm. |
| Unknown entry | “The minimum total distance travelled by the three tow trucks … is 32 km. Use the Hungarian algorithm to determine the distance between Tow Truck C and Motorist P.” (2021 P2 Q6) | Reduce, finish the algorithm, total the original entries, set equal to 32, solve. |
| Maximum assignment | No past question yet. The 2025 syllabus asks you to “Determine the optimum (minimum and maximum) assignment/s”. | Subtract every entry from the largest, then run it normally. |
Sources: QCAA General Mathematics external assessment papers, marking guides and subject reports, 2020 to 2025. General Mathematics 2025 syllabus (Unit 4 Topics 4 and 5) and formula book. Topic guides 12 to 15.
Past questions are from the 2021–2025 QCAA General Mathematics external assessments, © State of Queensland (QCAA) 2021–2025, licensed under CC BY 4.0, and have been adapted. Tangent Tuition is not affiliated with the QCAA.
© 2026 Tangent Tuition. This resource is licensed to you for your own study. Please don’t share it, send it to anyone else or post it anywhere. See the Terms of Use.
Spot a mistake on this page? Report it