Edexcel IAL - Decision Mathematics 1- 2.1 Minimum Spanning Trees (Prim’s and Kruskal’s Algorithms)- Study notes - New syllabus
Edexcel IAL – Decision Mathematics 1- 2.1 Minimum Spanning Trees (Prim’s and Kruskal’s Algorithms) -Study notes- New syllabus
Edexcel IAL – Decision Mathematics 1- 2.1 Minimum Spanning Trees (Prim’s and Kruskal’s Algorithms) -Study notes -Edexcel A level Maths- per latest Syllabus.
Key Concepts:
- 2.1 Minimum Spanning Trees (Prim’s and Kruskal’s Algorithms)
The Minimum Spanning Tree (Minimum Connector) Problem
In network problems, the minimum spanning tree (MST), also called the minimum connector, is a subset of edges that connects all vertices in a network with the minimum possible total weight, without forming any cycles.
Typical applications include designing road systems, electrical networks, communication links, and pipelines at minimum cost.
Key Properties of a Minimum Spanning Tree
- All vertices are connected
- There are no closed loops (cycles)
- For a network with \( \mathrm{n} \) vertices, the MST contains \( \mathrm{n – 1} \) edges
- The total weight of the edges is minimal
Prim’s Algorithm
Prim’s algorithm builds the minimum spanning tree by starting from a chosen vertex and repeatedly adding the shortest edge that connects a vertex inside the tree to a vertex outside the tree.
Steps of Prim’s Algorithm
- Start from any vertex
- Select the shortest edge connecting the current tree to a new vertex
- Add the edge and vertex to the tree
- Repeat until all vertices are included
Edges that would create a cycle are ignored.
Matrix Representation for Prim’s Algorithm
In examinations, Prim’s algorithm is often applied using an adjacency matrix.
The matrix is constructed as follows:
- Rows and columns represent vertices
- Each entry gives the weight of the edge between two vertices
- A dash, zero, or ∞ indicates no direct connection
Prim’s algorithm proceeds by repeatedly identifying the smallest available entry that links a visited vertex to an unvisited one.
Kruskal’s Algorithm
Kruskal’s algorithm constructs the minimum spanning tree by considering edges in order of increasing weight, regardless of starting vertex.
Steps of Kruskal’s Algorithm
- List all edges in increasing order of weight
- Select the shortest edge that does not form a cycle
- Add it to the spanning tree
- Repeat until \( \mathrm{n – 1} \) edges are chosen
Kruskal’s algorithm is particularly efficient when the network has many edges.
Drawing a Network from a Matrix
Given an adjacency matrix:
- Each row and column represents a vertex
- A non-zero entry indicates an edge with that weight
To draw the network:
- Draw all vertices
- Join vertices according to the matrix entries
- Label each edge with its weight
Writing the Matrix from a Network
To form a matrix from a given network:
- Label all vertices clearly
- Enter edge weights in the corresponding matrix positions
- Use the same value symmetrically about the main diagonal
- Use zero or ∞ where no edge exists
Important Examination Notes
- Both Prim’s and Kruskal’s algorithms must be understood
- Matrix representation is required for Prim’s algorithm
- Students must be able to convert between networks and matrices
Example
The weighted network has vertices \( \mathrm{A, B, C, D, E} \) and is represented by the following adjacency matrix:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | – | 4 | 2 | – | 7 |
| B | 4 | – | 1 | 5 | – |
| C | 2 | 1 | – | 8 | 6 |
| D | – | 5 | 8 | – | 3 |
| E | 7 | – | 6 | 3 | – |
(a) Draw the network represented by the matrix.
(b) Find the minimum spanning tree using Prim’s algorithm, starting at vertex A.
(c) Find the minimum spanning tree using Kruskal’s algorithm.
▶️ Answers / Explanations
(a) Drawing the Network
Vertices are connected wherever a number appears in the matrix, with the number representing the edge weight.
(b) Prim’s Algorithm (starting at A)
Step 1: Start at A
Edges: AB(4), AC(2), AE(7) → choose AC(2)
Step 2: Vertices A, C
Possible edges: CB(1), AB(4), CE(6), CD(8), AE(7) → choose CB(1)
Step 3: Vertices A, B, C
Possible edges: BD(5), CE(6), AE(7), CD(8) → choose BD(5)
Step 4: Vertices A, B, C, D
Possible edges: DE(3), CE(6), AE(7) → choose DE(3)
Edges in MST: AC(2), CB(1), BD(5), DE(3)
Total weight \( \mathrm{= 11} \)
(c) Kruskal’s Algorithm
Edges in increasing order:
CB(1), AC(2), DE(3), AB(4), BD(5), CE(6), AE(7), CD(8)
Selected edges:
CB(1) ✓, AC(2) ✓, DE(3) ✓, AB(4) ✗ (cycle), BD(5) ✓
Edges in MST: CB(1), AC(2), DE(3), BD(5)
Total weight \( \mathrm{= 11} \)
Final Conclusion
The minimum spanning tree has total weight 11. Both Prim’s and Kruskal’s algorithms give the same result.
Example —
The weighted network has vertices \( \mathrm{A, B, C, D, E} \). Use Prim’s algorithm, starting at vertex A, to find the minimum spanning tree. Show your working using a matrix-style table.
Apply Prim’s algorithm starting at vertex A and determine:
(i) the edges in the minimum spanning tree
(ii) the total weight of the tree
▶️ Answer / Explanation
At each step, the smallest edge connecting a visited vertex to an unvisited vertex is selected.
| Step | Visited vertices | Available edges | Chosen edge | Total weight |
|---|---|---|---|---|
| 1 | A | AB(4), AC(2), AE(7) | AC(2) | 2 |
| 2 | A, C | CB(1), AB(4), CE(6), CD(8), AE(7) | CB(1) | 3 |
| 3 | A, B, C | BD(5), CE(6), AE(7), CD(8) | BD(5) | 8 |
| 4 | A, B, C, D | DE(3), CE(6), AE(7) | DE(3) | 11 |
Conclusion
Edges in the minimum spanning tree:
AC(2), CB(1), BD(5), DE(3)
Total weight of the minimum spanning tree:
\( \mathrm{11} \)