A minimum spanning tree and a route distinction
Choose your method, connect the parts and explain your conclusions. These original questions include written reasoning and sketches as well as exact answer checks.
Suggested marks guide how much working to show. The site does not automatically award examination marks for proofs, diagrams or methods. Use scaffolded fluency practice when you need a hint first.
Decision option. Course filters use selected objective mappings; none of these tasks establishes complete paper coverage.
Before you start
Shortest paths with Dijkstra’s algorithm. Read the relevant method, then decide which parts you can solve without hints.
Check a misconception first · Try a connected problem
Read an original example question
An undirected network connects four locations. A cable must connect every location with least total length.
| Edge | Length |
|---|---|
| AB | 3 |
| BC | 6 |
| CD | 9 |
| DA | 12 |
| AC | 21 |
| BD | 24 |
Part a
Use Kruskal’s algorithm to find the minimum total cable length.
Part b
Give the selected edges and explain why AD is not also included.
Part c
Explain why this tree need not provide the shortest route between every pair of locations.
Model solution and review criteria
Part a
Choose AB, BC and CD in increasing weight order. They connect every vertex without a cycle and total 18.
- Sort edges.
- Reject cycles and stop at three edges for four vertices.
Part b
AB, BC, CD form the tree. AD would close the A–B–C–D–A cycle, adds length and is unnecessary for connectivity.
- State the tree.
- Explain the cycle condition.
Part c
The tree minimises total construction cost, not each pairwise route. Its A-to-D route is 18, while the original AD edge is 12.
- Distinguish the two optimisation objectives.
- Use an explicit counterexample.
Compare your own reasoning. No automatic examination marks are awarded.