QLDGeneral MathematicsSyllabus dot point

Topic 3: Networks and decision mathematics - how do we optimise connection, travel, flow and scheduling on a network?

Find minimum spanning trees using Prim's algorithm, determine shortest paths through a weighted network, calculate maximum flow using the maximum-flow minimum-cut idea, and schedule a project using critical path analysis to find the earliest completion time and float

A focused answer to the QCE General Mathematics Unit 4 dot point on networks and decision mathematics. Covers minimum spanning trees with Prim's algorithm, shortest paths, maximum flow and minimum cut, and critical path analysis with earliest and latest times and float, with arithmetic-verified worked examples for IA3 and the external assessment.

Generated by Claude Opus 4.76 min answerUpdated 2026-05-29

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

What this dot point is asking

QCAA wants you to optimise on a weighted network: connect everything as cheaply as possible (minimum spanning tree), travel between two points as cheaply as possible (shortest path), push as much through a network as possible (maximum flow), and schedule a project in the least time (critical path analysis). These four tools are Unit 4 Topic 3 and are reliably tested in IA3 and the external assessment with structured, multi-step questions.

The answer

Minimum spanning tree with Prim's algorithm

A spanning tree connects every vertex with no cycles. The minimum spanning tree (MST) is the one with the smallest total edge weight. Prim's algorithm builds it greedily:

Start at any vertex.
Repeatedly add the cheapest edge that connects a new vertex to the tree so far.
Never add an edge that would form a cycle.
Stop when all vertices are included.

An MST on $n$ vertices always has exactly $n - 1$ edges.

Shortest path

The shortest path between two vertices is the route of least total weight. In General Mathematics you find it by inspection on small networks, systematically comparing the total weight of each candidate route and keeping the smallest. Weights often represent distance, time or cost.

Maximum flow and minimum cut

A flow network has a source, a sink, and edges with capacities. The maximum flow is the greatest amount that can pass from source to sink. The maximum-flow minimum-cut result states that the maximum flow equals the capacity of the minimum cut, where a cut is a set of edges that, if removed, completely separates the source from the sink. To find the maximum flow, find the cut with the smallest total capacity.

Critical path analysis

A project is a set of activities with durations and precedence requirements, drawn as an activity network. Critical path analysis finds the shortest possible completion time.

Earliest start time (EST) of an activity is the latest of the earliest finish times of its immediate predecessors (forward pass).
Latest start time (LST) is found by working backwards from the project deadline (backward pass).
The critical path is the longest path through the network; its length is the minimum completion time.
Float (slack) for a non-critical activity is

\text{float} = \text{LST} - \text{EST}.

Critical activities have zero float; delaying any of them delays the whole project.

Worked example

Critical path and float

A project has activities with these durations and dependencies: A ( $4$ , start), B ( $3$ , after A), C ( $6$ , after A), D ( $2$ , after B and C).

Step 1: Forward pass for earliest start and finish times.

A: EST $0$ , finishes at $0 + 4 = 4$ .

B: EST $4$ (after A), finishes at $4 + 3 = 7$ .

C: EST $4$ (after A), finishes at $4 + 6 = 10$ .

D: EST is the later of B's and C's finishes, $\max(7, 10) = 10$ , finishes at $10 + 2 = 12$ .

Step 2: Minimum completion time. The project finishes at $12$ time units.

Step 3: Identify the critical path. The longest path is A then C then D: $4 + 6 + 2 = 12$ . This matches the completion time, so A, C, D are critical.

Verify: path A-B-D gives $4 + 3 + 2 = 9$ , which is shorter, so A-C-D at $12$ is indeed the longest.

Step 4: Float on activity B. B could start as late as time $10 - 3 = 7$ (so D still starts at $10$ ), but its EST is $4$ .

\text{float of B} = \text{LST} - \text{EST} = 7 - 4 = 3.

So B has $3$ units of float and can slip up to $3$ time units without delaying the project.

Common traps

Forming a cycle in Prim's algorithm: Only ever add an edge that reaches a vertex not yet in the tree. Adding an edge between two already-connected vertices creates a cycle and is not allowed.
Taking the largest cut instead of the smallest: Maximum flow equals the minimum cut, so you want the cut of smallest total capacity, not the largest.
Using the wrong rule on the forward pass: An activity's earliest start is the latest (maximum) of its predecessors' earliest finishes, not the earliest. Taking the minimum gives an impossible schedule.
Calling the shortest path the critical path: The critical path is the longest path through an activity network, because every activity on it must finish before the project can. The shortest path tool is for travel networks, not scheduling.
Forgetting float is zero on the critical path: Any activity with float can be delayed; critical activities have zero float and cannot slip at all.

Exam-style practice questions

Practice questions written in the style of QCAA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

2021 QCAA5 marksThe activity table for a project is shown. A (prereq none, 2 days); B (none, 4); C (A, 3); D (B, 6); E (D, 3); F (C and E, 4); G (D, 8); H (F and G, 4). a) Use the activity table to construct a network diagram, including earliest and latest starting times. [3 marks] b) Determine the critical path. [1 mark] c) Determine the shortest completion time for the project. [1 mark]

Show worked answer →

a) Network and scanning (3 marks). Draw each activity as an edge respecting prerequisites (1 mark): A and B from the source, C after A, D after B, E and G after D, F after both C and E, H after both F and G. Label each activity with its letter and duration (1 mark), then forward scan for earliest start times and backward scan for latest start times (1 mark).

b) Critical path (1 mark). The longest chain is B - D - G - H = 4 + 6 + 8 + 4 = 22 days (the parallel chain B - D - E - F - H = 21 days is shorter), so the critical path is BDGH.

c) Shortest completion time (1 mark): equal to the critical path length, 22 days.

Critical path analysis answers the scheduling part of decision mathematics: the longest path sets the earliest finish, and activities off it carry float (slack) before they delay the project.

2021 QCAA4 marksThe network diagram shows the flow of water from the tank (source) to the kitchen tap (sink), with dashed lines L1, L2, L3 and L4 drawn across it. a) Explain which dashed line is not a valid cut. [1 mark] b) Calculate the capacity of each dashed line that is a valid cut. [3 marks] (L1 crosses edges of capacity 20, 22, 15; L2 crosses 18, 19, 22, 15; L3 crosses 18, 8, 10.)

Show worked answer →

a) Invalid cut (1 mark). A cut must separate source from sink. L4 is not valid because the tank (source) and tap (sink) are on the same side of it, so it fails to separate them.

b) Capacities (3 marks). The capacity of a cut is the sum of the capacities of the edges crossing it from the source side to the sink side. L1 = 20 + 22 + 15 = 57 (1 mark); L2 = 18 + 19 + 22 + 15 = 74 (1 mark); L3 = 18 + 8 + 10 = 36 (1 mark).

By the maximum-flow minimum-cut theorem, the maximum flow equals the smallest cut capacity, which here is 36 (L3). This connects the cut idea to the maximum flow the pipes can actually carry.

2022 QCAA5 marksThe table shows the current road length (in km) between six towns. Connections include Manon-Veria 16, Manon-Bolint 34, Manon-Alin 33, Veria-Bolint 12, Veria-Recen 15, Bolint-Recen 10, Farra-Recen 15, Farra-Alin 23, Recen-Alin 15. The government plans to build a direct road between Manon and Farra. Use a network diagram to determine the length of the direct road if it is to be 4 km shorter than the length of the current shortest road route between Manon and Farra.

Show worked answer →

Step 1 - draw the weighted network of the six towns (1 mark).

Step 2 - label every edge with its kilometre distance (1 mark).

Step 3 - find the shortest route from Manon to Farra (1 mark). The route Manon - Veria - Bolint - Recen - Farra has length 16 + 12 + 10 + 15 = 53 km, shorter than alternatives such as Manon - Alin - Farra = 56 km.

Step 4 - state the shortest distance (1 mark): 53 km.

Step 5 - new road length (1 mark): 4 km shorter, so 53 - 4 = 49 km.

Shortest path is the route-optimising tool of decision mathematics; unlike a minimum spanning tree it only needs to join the two named towns, not connect every vertex.