Including a cycle in a spanning tree
A tree has no cycles. If an edge joins two vertices that are already connected in your tree, it would make a cycle — skip it, however light it is.
General Mathematics · Unit 4 · Topic 4
Connect every vertex of a network for the least total weight with minimum spanning trees, then plan projects with activity-on-arc networks, forward and backward scans, critical paths and float times.
Recognise trees and spanning trees, explain why a tree with vertices has edges, and find the spanning trees of a small graph.
Find a minimum spanning tree and its weight by inspection, with Kruskal's method and with Prim's method, and recognise when there is more than one.
Model practical cable, pipe and path problems as minimum spanning trees, cost them, and adapt the method when a link must be used or cannot be used.
Read a precedence table, and draw a project as an activity-on-arc network with each activity as a labelled arrow and each event as a numbered circle.
Scan a project network from start to finish to find the earliest starting time of every activity and the minimum time in which the project can be completed.
Scan a project network from the finish back to the start to find the latest starting time of every activity, then calculate each activity's float.
Use ESTs and LSTs to locate the critical path or paths of a project, and explain why their length is the minimum completion time.
Use critical path analysis to decide what a delay does to a project, how far a project can be shortened, and how to justify scheduling decisions in context.
Ten questions across the topic, from foundation to complex unfamiliar. Your results feed your mastery.
In Graphs and networks you used networks to describe connections. Now you use them to make decisions.
The first question is how to connect every town to a power station, or every paddock to a bore, using the least cable or pipe. The answer is always a tree — a network with no cycles — and the cheapest one is a minimum spanning tree. You will find one by inspection, with Kruskal's method and with Prim's method.
The second question is how quickly a project can be finished when some jobs must wait for others. You will draw the project as a network of activities, scan it forwards and backwards to find when each activity can start, find the critical path that sets the finish date, and work out how much each other activity can slip without making the project late.
Both halves reward careful, systematic working: list each edge as you choose it, write the times at every event, and state your answer in the context of the problem.
Builds on Graphs and networks.
Subject matter from the General Mathematics General senior syllabus 2025 v1.3 (opens in a new tab), CC BY 4.0 © State of Queensland (QCAA).
The focus areas you can practise on their own. Each one maps to dot points above.
Trees and spanning trees
Recognise trees and spanning trees, and use the fact that a tree with n vertices has n − 1 edges.
Finding minimum spanning trees
Find a minimum spanning tree and its weight by inspection, Kruskal's method or Prim's method, and decide whether it is unique.
Minimum connector problems
Model a cable, pipe or path problem as a minimum spanning tree, including edges that must be used or cannot be used, and costs.
Project networks
Read and write precedence tables, and draw a project as an activity-on-arc network.
Earliest starting times
Scan a project network forwards to find each activity's EST and the minimum completion time.
Latest starting times
Scan a project network backwards to find each activity's LST.
Critical paths
Use ESTs and LSTs to locate the critical path or paths, and use them to give the minimum completion time.
Float times
Calculate float = LST − EST for non-critical activities and say what it means for the schedule.
Scheduling problems
Use critical path analysis to judge delays, shorten a project, add an activity, and justify scheduling decisions.
A tree has no cycles. If an edge joins two vertices that are already connected in your tree, it would make a cycle — skip it, however light it is.
A spanning tree of a graph with vertices has exactly edges. Count them before you add the weights.
An activity can only start when all of its predecessors are finished, so at an event with several incoming activities the earliest time is the largest of the values.
An event must happen early enough for every activity leaving it to start on time, so in the backward scan take the smallest of the values.
The latest time written at an activity's start event is the LST of the most urgent activity leaving it, not necessarily of this one. Always use LST = (latest time at the end event) − duration.
Activities on different branches can run at the same time. The minimum completion time is the length of the longest path, not the total of every duration.
A non-critical activity can slip only by its float. A delay of beyond its float makes the whole project longer.
Once one path is shortened below another, the other path becomes critical. Recheck every path after you change a duration.
Name your method. "Using Kruskal's method, choose edges in order of weight: (3), (4), …" earns method marks even if you slip on an addition.
List the edges of a minimum spanning tree and count them: edges is a quick check that you have not missed or added one.
Write both times at every event as you scan, and state the minimum completion time with units: "The minimum completion time is 16 days."
Give a critical path as a sequence of activities, such as A–C–E–F, and check that its durations add to the minimum completion time.
If there is more than one critical path, give them all. The syllabus says "critical path/s" for a reason.
For "effect of a delay" questions, compare the delay with the activity's float and say what happens to the finish time.
Show a table of EST, LST and float when a question asks about several activities. It is quicker to mark and to check.
Minimum spanning tree and critical path questions can be done without a calculator. Paper 2 contexts may add costs, so set out the multiplication.
Energy companies plan transmission lines and gas pipelines between towns using minimum connector methods.
Farmers plan irrigation pipes and water points across paddocks with the least length of pipe.
Telecommunications companies lay fibre-optic cable between exchanges to join every site for the least cost.
Builders, event organisers and engineers use critical path analysis to schedule trades and set realistic finish dates.
Project managers watch the critical activities most closely, and use float to move non-critical work when people or equipment are busy.
Large projects, such as a new hospital or a festival stage, are shortened ("crashed") by spending money on the critical activities that are cheapest to speed up.