Network terminology and minimum spanning trees (Prim's and Kruskal's): HSC Maths Standard 1 Year 12
“N1.1 Networks: identify and use network terminology (vertex, edge, degree, weighted edge, path, connected, tree), construct network diagrams from real-life situations, and find a minimum spanning tree using Prim's or Kruskal's algorithm”
Networks are made of vertices and edges, which can be weighted. A tree is connected with no cycles, and a spanning tree connects every vertex with edges. Find the minimum spanning tree with Kruskal's algorithm (add the smallest edges that do not form cycles) or Prim's algorithm (grow from a starting vertex by the smallest connecting edge).
Jump to a section
What this dot point is asking
You need to use network language, draw networks for real situations (rail lines, cable networks, roads), and find the cheapest or shortest way to connect every vertex, the minimum spanning tree, using Prim's or Kruskal's algorithm.
The answer
Network terminology
| Term | Meaning |
|---|---|
| Vertex (node) | A point, such as a town or a computer |
| Edge | A connection between two vertices |
| Degree | Number of edges at a vertex |
| Weighted network | Edges have values (distance, time, cost) |
| Path | A sequence of edges from one vertex to another without repeating vertices |
| Connected | Every vertex can be reached from every other |
| Cycle | A path that starts and ends at the same vertex |
| Tree | A connected network with no cycles |
| Spanning tree | A tree that includes every vertex |
A spanning tree of a connected network with vertices always has exactly edges.
Minimum spanning trees
Kruskal's algorithm
- List edges from smallest to largest weight.
- Add the smallest edge that does not create a cycle.
- Repeat until you have edges.
Prim's algorithm
- Start at any vertex.
- Add the smallest edge joining a connected vertex to an unconnected vertex.
- Repeat until every vertex is connected.
Both give a minimum spanning tree (the same total weight, even if the edges differ when there are ties). Both are "greedy": they choose the best edge at each step without looking ahead.
Connect four classrooms A, B, C, D with network cable. Distances (m): AB 12, AC 18, AD 25, BC 10, BD 22, CD 15.
Kruskal's: BC 10, AB 12, CD 15 (next would be AC 18, which makes a cycle; not needed). Three edges for four vertices.
Minimum cable m.
- Creating a cycle
- Check whether both ends of an edge are already connected.
- Stopping too early or too late
- You need exactly edges.
- Confusing a minimum spanning tree with a shortest path
- A spanning tree connects all vertices; a shortest path joins two vertices.
Practice questions
Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.
foundation3 marksA network has vertices A, B, C, D and edges AB, AC, BC, CD. Find the degree of each vertex and state whether the network is a tree.Show worked solution →
Degrees: A = 2, B = 2, C = 3, D = 1.
It is not a tree because A, B and C form a cycle (A to B to C to A).
Marking guide: 1 mark for degrees, 1 mark for identifying the cycle, 1 mark for the conclusion.
core4 marksFive farm sheds P, Q, R, S, T are to be connected by water pipes. Possible pipe lengths (m): PQ 40, PR 25, QR 30, QS 45, RS 35, RT 50, ST 20. Use Kruskal's algorithm to find the minimum length of pipe.Show worked solution →
Sort edges: ST 20, PR 25, QR 30, RS 35, PQ 40, QS 45, RT 50.
- Choose ST (20).
- Choose PR (25).
- Choose QR (30).
- Choose RS (35): connects {P, Q, R} to {S, T}, no cycle.
- Stop: 4 edges for 5 vertices.
Minimum spanning tree: ST, PR, QR, RS. Total m.
Marking guide: 1 mark for ordering edges, 2 marks for correct selections without cycles, 1 mark for the total.
exam4 marksUse Prim's algorithm starting at P on the network from the previous question, showing the order edges are added, and confirm the total.Show worked solution →
Start at P. Edges from P: PQ 40, PR 25. Choose PR (25).
From {P, R}: PQ 40, QR 30, RS 35, RT 50. Choose QR (30).
From {P, Q, R}: QS 45, RS 35, RT 50. Choose RS (35).
From {P, Q, R, S}: RT 50, ST 20. Choose ST (20).
All 5 vertices connected. Total m, matching Kruskal's algorithm.
Marking guide: 1 mark per correct step (up to 3), 1 mark for the total.