Edexcel IAL - Decision Mathematics 1- 3.3 Upper and Lower Bounds Using Minimum Spanning Trees- Study notes - New syllabus
Edexcel IAL – Decision Mathematics 1- 3.3 Upper and Lower Bounds Using Minimum Spanning Trees -Study notes- New syllabus
Edexcel IAL – Decision Mathematics 1- 3.3 Upper and Lower Bounds Using Minimum Spanning Trees -Study notes -Edexcel A level Maths- per latest Syllabus.
Key Concepts:
- 3.3 Upper and Lower Bounds Using Minimum Spanning Trees
Upper and Lower Bounds using Minimum Spanning Tree Methods
In problems related to the Travelling Salesman Problem (TSP), it is often difficult to find the exact shortest tour. Instead, we determine lower bounds and upper bounds for the length of the shortest possible tour.
One important method for finding these bounds uses the concept of a minimum spanning tree (MST).
Lower Bound using a Minimum Spanning Tree
A minimum spanning tree is a set of edges that:
- connects all vertices
- has the minimum possible total edge weight
- contains no cycles
Any travelling salesman tour must connect all vertices, so its total length must be at least as large as the weight of an MST.
Therefore:
$\text{Lower bound = weight of the minimum spanning tree}$
This bound may be improved by adding the smallest extra edges required to make all vertex degrees at least 2, but the basic MST weight already provides a valid lower bound.
Upper Bound
An upper bound is obtained by finding any valid travelling salesman tour. 
Typical ways to find an upper bound include:
- nearest neighbour method
- trial routes by inspection
- improving a route using shortcuts
The length of any such tour gives an upper bound, since the shortest possible tour cannot be longer than this.
Conversion to a Complete Network of Shortest Distances
In some problems, the given network is not complete, meaning not all pairs of vertices are directly connected.
To apply TSP and MST methods, the network is first converted into a complete network as follows:
- Find the shortest distance between every pair of vertices in the original network
- Replace each pair of vertices by a single edge with this shortest distance
The resulting complete network represents the shortest possible distances between all vertices.
Minimum spanning trees and travelling salesman bounds are then found using this complete network.
Summary of the Method
- Convert the network into a complete network of shortest distances if required
- Find the minimum spanning tree of the complete network
- Use the MST weight as a lower bound
- Find a valid tour to obtain an upper bound
The true travelling salesman distance lies between these two bounds.
Example
A complete network has vertices A, B, C and D with edge weights:
AB = 4, AC = 6, AD = 5, BC = 3, BD = 7, CD = 4
Find a lower bound for the length of the travelling salesman tour using a minimum spanning tree.
▶️ Answer / Explanation
List edges in increasing order:
BC(3), AB(4), CD(4), AD(5), AC(6), BD(7)
Form the minimum spanning tree:
BC(3), AB(4), CD(4)
Total weight of MST:
\( \mathrm{3 + 4 + 4 = 11} \)
Conclusion:
The lower bound for the travelling salesman tour is \( \mathrm{11} \).
Example
The following network is not complete:
AB = 5, BC = 4, CD = 6, DA = 7, AC = 10
Convert this network into a complete network of shortest distances.
▶️ Answer / Explanation
Find shortest distances between all pairs:
A to C: min(AC = 10, A → B → C = \( \mathrm{5 + 4 = 9} \)) → 9
B to D: B → C → D = \( \mathrm{4 + 6 = 10} \)
A to D: AD = 7 (already shortest)
Complete network distances:
AB = 5, AC = 9, AD = 7, BC = 4, BD = 10, CD = 6
Conclusion:
The network is now complete and can be used for MST and TSP bounds.
Example
A complete network of five vertices has:
Total weight of its minimum spanning tree = 18
A travelling salesman tour of length 26 has been found by inspection.
State suitable upper and lower bounds and explain what they mean.
▶️ Answer / Explanation
Lower bound:
The weight of the minimum spanning tree gives a lower bound:
\( \mathrm{18} \)
Upper bound:
The length of a valid tour gives an upper bound:
\( \mathrm{26} \)
Conclusion:
The true shortest travelling salesman tour lies between \( \mathrm{18} \) and \( \mathrm{26} \).