Algorithms on graphs II
Edexcel International A-Level MathematicsΒ· D1 Β§3.1 to Β§3.4 2018 Issue 3Β· 25 min read
1. Route Inspection (Chinese Postman) Problemβ β ββββ± 8 min
β Calculator OK
Route Inspection Problem
Finds the shortest closed route that traverses every edge of a connected network at least once, returning to the start vertex.
Example:
Used to plan delivery routes, gritting routes, or postal rounds that cover every street in an area.
The problem relies on Euler's theorem for traversable networks: a network has a closed Eulerian trail (traverses every edge exactly once) if and only if it has 0 odd-degree vertices. If there are odd-degree vertices, you must repeat edges to eliminate odd vertices, pairing up odd vertices and repeating the shortest path between each pair to minimize total extra distance. For Edexcel D1, networks will have at most 4 odd vertices: for 2 odd vertices, repeat the shortest path between them; for 4 odd vertices, list all 3 possible pairings, calculate the total extra distance for each pairing, and choose the minimum. The total route length is the sum of all edge weights plus the minimum extra distance.
A connected network has total edge weight 128, and four odd vertices: A, B, C, D. The shortest paths between pairs of odd vertices are: AB=7, AC=12, AD=9, BC=5, BD=10, CD=8. Find the minimum length of a route that traverses every edge at least once and returns to the start.
- 1
List all 3 valid pairings of the 4 odd vertices:
- 2
Pairing 1: (A,B) and (C,D): total extra = 7 + 8 = 15
- 3
Pairing 2: (A,C) and (B,D): total extra = 12 + 10 = 22
- 4
Pairing 3: (A,D) and (B,C): total extra = 9 + 5 = 14
- 5
Select the minimum extra distance: 14
- 6
Total route length = 128 + 14 = 142
Exam tip:
Always explicitly list all 3 pairings for 4 odd nodes to gain full method marks, even if you spot the minimum pairing immediately.
2. Travelling Salesman Problem (TSP) Variantsβ β β βββ± 6 min
β Calculator OK
Travelling Salesman Problem
Finds the shortest closed route that visits every vertex in a network exactly once, returning to the start vertex.
Edexcel D1 distinguishes two variants: Classical TSP: applies to complete graphs that satisfy the triangle inequality (the shortest path between any two vertices is the direct edge between them). Practical TSP: applies to non-complete graphs, or graphs that do not satisfy the triangle inequality. For practical TSP, first convert the original network to a complete network of shortest distances between all pairs of vertices, then solve the classical TSP on this new network. You can improve an upper bound for TSP by using short cuts: if a route visits a vertex more than once, replace the repeated segment with a direct path to the next unvisited vertex to reduce the total length.
A TSP route on a 5-vertex network is: A β B β C β A β D β E β A, total length 79. Use a short cut to improve this upper bound, given the shortest path CβD is 10 and CβA + AβD = 14.
- 1
Identify the repeated vertex: A is visited twice before all vertices are covered, after visiting C.
- 2
Replace the segment C β A β D with the direct shortest path C β D, which has weight 10 (versus 14 for the original segment).
- 3
New route: A β B β C β D β E β A, total length = 79 - 14 + 10 = 75, which is a tighter upper bound.
Exam tip:
Short cuts are only valid if they do not skip any unvisited vertices: ensure all vertices are still visited exactly once after applying the short cut.
3. TSP Bounds using MST Methodsβ β β β ββ± 6 min
β Calculator OK
Since exact TSP solutions are computationally expensive for large networks, you only need to calculate upper and lower bounds for the optimal TSP route in Edexcel D1. Upper bound: any valid TSP route length (the smaller the upper bound, the closer it is to the optimal solution). Lower bound: the minimum possible length of the optimal TSP route (the larger the lower bound, the tighter the constraint on the optimal solution).
MST TSP Lower Bound
A lower bound calculated by deleting one vertex from the network, finding the MST of the remaining vertices, then adding the weight of the two shortest edges connecting the deleted vertex back to the MST. The optimal TSP route is at least this value.
A 4-vertex complete network has edge weights: AB=6, AC=8, AD=5, BC=3, BD=9, CD=4. Calculate the lower bound for TSP by deleting vertex A.
- 1
Delete vertex A, leaving vertices B, C, D.
- 2
Find the MST of B,C,D: edges BC=3, CD=4, total MST weight = 7.
- 3
Find the two shortest edges connecting A to the remaining vertices: AD=5, AB=6, sum = 11.
- 4
Lower bound = 7 + 11 = 18.
To find a valid upper bound using the MST method, double every edge of the MST to create a closed route that traverses every edge twice, then apply short cuts to get a valid TSP route. This gives an upper bound of at most twice the optimal TSP length for classical TSP.
Exam tip:
Calculate lower bounds for multiple deleted vertices, then take the largest value as your final lower bound (the tightest constraint on the optimal route).
4. Nearest Neighbour Algorithmβ β β βββ± 5 min
β Calculator OK
Nearest Neighbour Algorithm
A heuristic algorithm to find an upper bound for TSP, starting at a given vertex, then repeatedly visiting the nearest unvisited vertex until all vertices are visited, then returning to the start vertex.
Follow these steps for nearest neighbour: 1. Select a start vertex. 2. From the current vertex, move to the nearest unvisited vertex. 3. Repeat step 2 until all vertices are visited. 4. Return directly to the start vertex. The resulting route length is an upper bound for TSP. Run the algorithm from every vertex and select the smallest resulting length to get the tightest upper bound.
Use the nearest neighbour algorithm starting at A for the 4-vertex network from the previous example: AB=6, AC=8, AD=5, BC=3, BD=9, CD=4.
- 1
Start at A, nearest unvisited vertex is D (weight 5). Current route: AβD.
- 2
At D, nearest unvisited vertex is C (weight 4). Current route: AβDβC.
- 3
At C, only unvisited vertex is B (weight 3). Current route: AβDβCβB.
- 4
Return from B to A (weight 6). Total route length = 5 + 4 + 3 + 6 = 18.
- 5
Since this upper bound equals the lower bound calculated earlier, this is the optimal TSP route.
Exam tip:
Always explicitly state each step of the nearest neighbour algorithm to gain full marks, do not just write the final route.
5. Common Pitfalls
Wrong move:
For 4 odd nodes in route inspection, only listing 2 pairings instead of all 3.
Why:
You may miss the minimum extra distance pairing, leading to an incorrect total route length, and lose method marks.
Correct move:
Always list all 3 distinct pairings of 4 odd nodes, calculate the extra distance for each, then select the minimum.
Wrong move:
Applying nearest neighbour directly to a practical TSP network without first converting it to a complete shortest distance network.
Why:
The resulting route may not be valid, or may give an unnecessarily loose upper bound.
Correct move:
For practical TSP, first build a complete matrix of shortest paths between all pairs of vertices, then run nearest neighbour on this matrix.
Wrong move:
When calculating TSP lower bound, adding the weight of the MST of all vertices instead of deleting one vertex first.
Why:
This gives an incorrect lower bound that is too low, and does not follow the required method.
Correct move:
Delete one vertex, calculate the MST of the remaining vertices, then add the two shortest edges connecting the deleted vertex back to the network.
Wrong move:
Using a short cut that skips an unvisited vertex when improving a TSP upper bound.
Why:
The resulting route is not a valid TSP route, as it fails to visit every vertex exactly once.
Correct move:
Only replace segments that return to an already visited vertex, ensuring all unvisited vertices are still included in the route.
Wrong move:
Forgetting to add the total weight of all edges to the extra repeat distance in route inspection problems.
Why:
You will only calculate the extra length, not the total route length, losing accuracy marks.
Correct move:
Total route length = sum of all edge weights + minimum extra repeat distance.
6. Quick Reference Cheatsheet
Algorithm | Key Steps | Use Case |
|---|---|---|
Route Inspection |
| Shortest route covering every edge at least once |
TSP MST Lower Bound |
| Minimum possible optimal TSP length |
Nearest Neighbour |
| TSP upper bound |
Practical TSP Prep |
| Non-complete or non-triangle inequality networks |
7. Frequently Asked
How many pairings do I need to list for 4 odd nodes in route inspection?
For 4 odd nodes, there are exactly 3 distinct pairings to evaluate. You do not need to use any algorithm to find pairings: list all explicitly by inspection to gain full method marks.
When do I need to create a complete shortest distance network for TSP?
For practical TSP (where the original network is not complete or does not satisfy the triangle inequality), first convert it to a complete network of shortest paths between all pairs of nodes before calculating bounds or applying nearest neighbour.
Going deeper
What's Next
Now that you have mastered graph algorithms for route inspection and TSP, you are ready to move on to the next core topics in Edexcel IAL Decision Maths 1. These graph algorithms are frequently tested together with network flow and critical path analysis in longer 8-12 mark exam questions, so make sure you practice combining these concepts with past paper questions. You should also practice constructing complete shortest distance matrices from non-complete networks, as this is a common first step for practical TSP questions that many students lose marks on. Make sure you can clearly show all workings for pairings, MST calculations, and nearest neighbour steps to gain full method marks in your exam.