# Algorithms on graphs II

> Edexcel International A-Level Mathematics · D1 WDM11 2018
> Source: https://www.owlsprep.com/study/edexcel-ial-math-d1-algorithms-on-graphs-ii/

This guide covers core graph algorithm topics for Edexcel IAL Decision Maths 1: route inspection (Chinese postman) problems, TSP bounds, nearest neighbour algorithm, and practical TSP short cuts, aligned to the 2018 specification.

**Prerequisites:** [Graphs and networks terminology](https://www.owlsprep.com/study/edexcel-ial-math-d1-graphs-networks-basics/); [Minimum spanning tree algorithms (Kruskal, Prim)](https://www.owlsprep.com/study/edexcel-ial-math-d1-minimum-spanning-trees/)

## Learning objectives

- Solve route inspection (Chinese postman) problems for networks with up to 4 odd nodes
- Distinguish between classical and practical Travelling Salesman Problem (TSP) variants
- Calculate upper and lower bounds for TSP using minimum spanning tree (MST) methods
- Apply the nearest neighbour algorithm to find TSP upper bounds
- Use short cuts to improve TSP upper bounds

## Route Inspection (Chinese Postman) Problem

**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.

**Worked example:** 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.

*Calculator:* allowed

## Travelling Salesman Problem (TSP) Variants

**Travelling Salesman Problem** — Finds the shortest closed route that visits every vertex in a network exactly once, returning to the start vertex.

*Notation:* TSP

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.

**Worked example:** 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.

*Calculator:* allowed

## TSP Bounds using MST Methods

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.

**Worked example:** 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).

*Calculator:* allowed

## Nearest Neighbour Algorithm

**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.

**Worked example:** 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.

*Calculator:* allowed

## Common pitfalls

- **Wrong:** For 4 odd nodes in route inspection, only listing 2 pairings instead of all 3.
  - Why it fails: You may miss the minimum extra distance pairing, leading to an incorrect total route length, and lose method marks.
  - Correct: Always list all 3 distinct pairings of 4 odd nodes, calculate the extra distance for each, then select the minimum.
- **Wrong:** Applying nearest neighbour directly to a practical TSP network without first converting it to a complete shortest distance network.
  - Why it fails: The resulting route may not be valid, or may give an unnecessarily loose upper bound.
  - Correct: For practical TSP, first build a complete matrix of shortest paths between all pairs of vertices, then run nearest neighbour on this matrix.
- **Wrong:** When calculating TSP lower bound, adding the weight of the MST of all vertices instead of deleting one vertex first.
  - Why it fails: This gives an incorrect lower bound that is too low, and does not follow the required method.
  - Correct: 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:** Using a short cut that skips an unvisited vertex when improving a TSP upper bound.
  - Why it fails: The resulting route is not a valid TSP route, as it fails to visit every vertex exactly once.
  - Correct: Only replace segments that return to an already visited vertex, ensuring all unvisited vertices are still included in the route.
- **Wrong:** Forgetting to add the total weight of all edges to the extra repeat distance in route inspection problems.
  - Why it fails: You will only calculate the extra length, not the total route length, losing accuracy marks.
  - Correct: Total route length = sum of all edge weights + minimum extra repeat distance.

## Cheatsheet

| Algorithm | Key Steps | Use Case |
| --- | --- | --- |
| Route Inspection | 1. Count odd nodes 2. List all pairings 3. Minimize extra distance 4. Add to total edge weight | Shortest route covering every edge at least once |
| TSP MST Lower Bound | 1. Delete one vertex 2. Find MST of remaining vertices 3. Add two shortest edges back to deleted vertex | Minimum possible optimal TSP length |
| Nearest Neighbour | 1. Start at a vertex 2. Visit nearest unvisited vertex 3. Repeat, return to start | TSP upper bound |
| Practical TSP Prep | 1. Build complete shortest distance matrix 2. Solve classical TSP on matrix 3. Apply short cuts | Non-complete or non-triangle inequality networks |

## 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.

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/edexcel-ial-math-d1-algorithms-on-graphs-ii/