How do we connect every site in a network at the lowest total cost?
Find minimum spanning trees of weighted networks using a systematic algorithm.
Trees, spanning trees and minimum spanning trees, with Prim's algorithm applied to the minimum connector problem in TCE Mathematics Applications.
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
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.
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.
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.
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.
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.
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 practice questions
Practice questions written in the style of TASC exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
2021 TASC General Mathematics6 marksAn array of garden sprinklers (S1 to S7) is to be connected by pipes to a tap. The graph shows distances (in metres) separating the elements of the network. a) Using Prim's algorithm, show on the graph how all the sprinklers and tap can be connected so that the minimum length of pipe is used. b) What is the minimum total length of pipe? c) A landscape gardener charges $22.50 per metre of pipe laid. She finds a pipe is already laid between the tap and S3. Find the amount she should charge for connecting the sprinkler array.Show worked answer →
a) (2 marks) Apply Prim's algorithm: start at any vertex (say the tap), then repeatedly add the shortest edge that connects a new vertex to the tree already built, never forming a cycle, until all 8 vertices are joined. Mark the selected edges on the graph; they form the minimum spanning tree.
b) (1 mark) Add the lengths of the edges chosen in part a). That total is the minimum length of pipe needed.
c) (3 marks) Because the tap-to-S3 pipe already exists, that length does not need to be laid. Subtract the tap-to-S3 edge length from the minimum total, then multiply the remaining length by $22.50 per metre to get the amount to charge.