Minimum Spanning Trees - TCE Mathematics Applications (Tasmania)
“Find minimum spanning trees of weighted networks using a systematic algorithm.”
You must find the minimum spanning tree of a weighted network: the set of edges that connects every vertex with no cycles and the smallest possible total weight, found by repeatedly adding the cheapest edge that keeps the structure a tree.
What this dot point is asking
The minimum connector problem asks how to link every site, such as towns to be joined by cable or pipe, using the least total length or cost. The answer is a special subgraph called a minimum spanning tree.
A tree is a connected graph with no cycles. A spanning tree of a network includes every vertex of the network and just enough edges to keep it connected with no cycles. A network with vertices always has a spanning tree of exactly edges.
Minimum spanning tree
A network usually has many spanning trees. The minimum spanning tree (MST) is the one with the smallest total edge weight. It is the cheapest way to connect everything while never forming a loop, because a loop would add cost without connecting any new vertex.
An MST of a network with vertices has exactly edges, contains no cycles, and reaches every vertex. Its total weight is the smallest achievable while keeping all vertices connected.
Building it with Prim's algorithm
A reliable systematic method is to grow the tree one vertex at a time. Start anywhere, then repeatedly add the cheapest edge that joins a new vertex to the part already built, never closing a loop.
Towns A, B, C, D have connections with weights: A-B 4, A-C 3, B-C 2, B-D 5, C-D 6.
Grow the tree from A
Start at A. Cheapest edge from A is A-C (3). Tree so far: A, C.
Cheapest edge joining a new vertex to {A, C} is C-B (2). Tree: A, C, B.
Cheapest edge joining a new vertex to {A, C, B} is B-D (5). Tree: A, C, B, D.
Total weight
All four vertices are connected using 3 edges (which is ): A-C, C-B, B-D. Total weight . This is the minimum spanning tree.
Notice the edges A-B (4) and C-D (6) were never used; adding either would create a cycle or cost more than the edge already chosen for that connection.
A spanning tree of a -vertex network always has exactly edges. Count as you go: once you have added edges and reached every vertex, the tree is complete and you stop.
Reading the answer
The exam usually wants both the set of edges in the MST and its total weight. State the edges clearly and add their weights for the total, which is the minimum cost to connect the network.
The MST above totals 10. In context, if the weights are kilometres of cable between towns, the cheapest cabling that links all four towns uses the routes A-C, C-B and B-D and needs 10 km of cable.
Why not the direct route
Connecting A-B directly (4 km) would cost more than reaching B through C (3 + 2 = 5 to reach both C and B), and the chosen tree avoids any redundant loop.
Greedily grabbing the smallest weights can accidentally form a loop, which is not allowed in a tree. Every edge you add must connect a new vertex to the growing tree. If the cheapest remaining edge would close a cycle, skip it and take the next cheapest valid edge.
Kruskal's algorithm as an alternative
Prim's algorithm grows one connected tree from a starting vertex, but Kruskal's algorithm offers a different route to the same minimum spanning tree. Instead of growing from one point, Kruskal's sorts all the edges from cheapest to dearest and adds them one at a time, skipping any edge that would close a cycle, until edges have been chosen. The two methods always reach the same total weight on a network with distinct edge weights, so you can use whichever the question suggests or use one to check the other.
Towns A, B, C, D with weights A-B 4, A-C 3, B-C 2, B-D 5, C-D 6.
Sort and add edges, skipping cycles
Sorted: B-C (2), A-C (3), A-B (4), B-D (5), C-D (6).
Add B-C (2). Add A-C (3); now A, B, C joined. Skip A-B (4) as it would close the triangle A-B-C. Add B-D (5); all four vertices joined with edges.
Total weight
, matching the Prim result. Kruskal's reaches the same minimum spanning tree by a different order of choices.
When edge weights repeat
If two edges share the same weight, a network can have more than one minimum spanning tree, all with the same total weight. The exam accepts any valid MST in that case, provided it connects every vertex, contains no cycle, and uses exactly edges. State your tree clearly so the marker can verify it.
A complete answer lists the edges of the minimum spanning tree, confirms it uses exactly edges and contains no cycle, and states the minimum total weight interpreted in the units of the problem.
Exam-style questions
Questions in the style of TASC exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.
Practice4 marksSix towns A to F are to be linked by fibre cable. The connection lengths (km) are A-B 5, A-C 7, B-C 4, B-D 6, C-E 8, D-E 3, D-F 9, E-F 2. a) Use Prim's algorithm starting at A to find the minimum spanning tree. b) State its total length and how many edges it uses.Show worked answer →
a) (3 marks) Start at A. Cheapest from A is A-B (5); tree {A, B}. Cheapest joining a new vertex is B-C (4); tree {A, B, C}. Next is B-D (6); tree {A, B, C, D}. Next is D-E (3); tree {A, B, C, D, E}. Next is E-F (2); tree {A, B, C, D, E, F}. Skip A-C, C-E, D-F as they would add cost or a cycle.
b) (1 mark) Edges A-B, B-C, B-D, D-E, E-F. Total km, using edges for vertices. Markers reward never closing a cycle and stopping at edges.