Skip to main content
ExamExplained
NSW · Maths Standard 2
Maths Standard 2 study scene
§-Quick questions
NSWMaths Standard 2Year 12: Networks

Quick questions on Minimum spanning trees and Prim's algorithm for HSC Maths Standard 2

8short Q&A pairs drawn directly from our worked dot-point answer. For full context and worked exam questions, read the parent dot-point page.

What is spanning tree?
Show answer
A spanning tree of a connected graph is a subgraph that:
What is minimum spanning tree (MST)?
Show answer
A minimum spanning tree is a spanning tree with the smallest total edge weight among all possible spanning trees of the graph.
What is watch Prim's build the tree, stage by stage?
Show answer
The diagram above shows the finished minimum spanning tree. Here is the same graph with Prim's algorithm run one edge at a time. This lets you watch the tree grow and follow the reasoning at each step. Tree edges are heavy and in colour, and vertices already in the tree are ringed.
What is kruskal's algorithm?
Show answer
Kruskal's algorithm sorts all edges and adds them in order, skipping any that create a cycle:
What is cycle check (Kruskal's)?
Show answer
An edge creates a cycle if both of its endpoints are already linked, either directly or through edges you have already chosen. For small graphs you can usually see this by eye. For larger graphs, keep track of which vertices sit in which connected piece (called a component) as you add edges.
What are not checking for cycles in Kruskal's?
Show answer
The cheapest unused edge sometimes creates a cycle. Skip those.
What is wrong total weight?
Show answer
Sum all the chosen edge weights at the end.
What is disconnected MST?
Show answer
A spanning tree must connect every vertex. If your n1n - 1 edges form a forest (disconnected components), you have made a mistake.
ExamExplained