Algorithms on graphs II

D1 Topic 3, spec point by spec point (Algorithms on graphs II). Each spec point has the method, worked examples written the way the mark scheme wants them, how the marks go and the mistakes that cost the most marks.

Spec3.1Route inspection (the Chinese postman problem)

The algorithm for the shortest route around a network that travels along every edge at least once and ends at the start vertex. Networks have up to four odd nodes, and all pairings of odd nodes are considered by inspection.

Why odd nodes matter

Each time a route passes through a vertex, it uses two edges (one in, one out). So a closed route using every edge exactly once is possible only if every vertex has even degree.

Odd nodes What's possible
0 a closed route using every edge exactly once (length = total weight)
2 every edge exactly once, but starting at one odd node and finishing at the other
4 some edges must be repeated

The algorithm

  1. Find the odd nodes.
  2. List every pairing of them. With four odd nodes P, Q, R, S there are three: PQ + RS, PR + QS, PS + QR.
  3. For each pairing, find the shortest distances (by inspection or Dijkstra) and add them.
  4. Choose the pairing with the smallest total. Those shortest paths are repeated.
  5. Length of route \(=\) total weight of the network \(+\) smallest pairing total.

If the route needn't end where it started

Start and finish at two of the odd nodes, and repeat the shortest path between the other two. Choose the start and finish so that the repeated path is as short as possible (or as the question fixes).

four odd nodes

Arcs: AB 7, AC 5, AD 9, BC 4, BE 8, CD 6, CE 11, DF 11, EF 3. Total weight 64.

Degrees: A 3, B 3, C 4, D 3, E 3, F 2. Odd nodes: A, B, D, E.

Pairing Shortest distances Total
AB + DE 7 + 14 (DFE) 21
AD + BE 9 + 8 17
AE + BD 15 (ABE) + 10 (BCD) 25

Repeat AD and BE. Shortest route \(= 64 + 17 = 81\).

If the route may start at A and finish anywhere: finish at D and repeat only BE (the shortest path between the other two odd nodes), giving \(64 + 8 = 72\).

  • M1 for the three pairings of the four odd nodes, A1ft two rows correct, A1 all three rows, A1 for the repeated arcs named as arcs, A1ft for the length (WDM11A Jan 2026 Q3b, WDM11 Jun 2021 Q4e).
  • Changing from "start and finish at A" to a fixed different finish: compare the two repeated paths (WDM11 Jun 2023 Q6d).

Often asked as: very common (48 questions), usually right after Dijkstra on the same network. Variants: a different start and finish; a new edge added; the edges traversed twice; the number of times a vertex is passed through.

Missing one of the three pairings.

Giving the repeated arcs as a path like "ABE" when the scheme wants the arcs AB, BE.

Spec3.2The travelling salesman problem

The practical and classical travelling salesman problems; the classical problem for complete graphs satisfying the triangle inequality; short cuts to improve an upper bound.

Classical vs practical

The travelling salesman problem (TSP) asks for the shortest route that visits every vertex and returns to the start. (Compare route inspection, which covers every edge.)

Classical Practical
each vertex visited exactly once each vertex visited at least once (revisits allowed)

Turning a practical problem into a classical one

Make a complete network of shortest distances: replace each entry with the shortest distance between the two vertices (found by inspection or Dijkstra). This table satisfies the triangle inequality (the direct route is never longer than going via another vertex: \(AB \leqslant AC + CB\)), so a classical tour on it solves the practical problem.

When you interpret a tour from that table, expand each leg into the actual roads used (some vertices then appear twice).

Bounds

There's no efficient algorithm for the optimal tour, so you find bounds:

\[\text{best lower bound} \leqslant \text{optimal tour} \leqslant \text{best upper bound}\]

The best upper bound is the smallest; the best lower bound is the largest (3.3, 3.4).

least distances and interpreting a tour

Roads: AB 5, BC 4, CD 6, DA 12, BD 3.

Table of least distances: AB 5, AC 9 (via B), AD 8 (via B, shorter than the direct 12), BC 4, BD 3, CD 6.

The tour A, B, C, D, A on this table has length \(5 + 4 + 6 + 8 = 23\).

The leg D to A really goes D–B–A, so the actual route is A–B–C–D–B–A (23), visiting B twice. Using the direct road DA would give 27.

  • B1 classical: every vertex exactly once and back to the start; B1 practical: every vertex at least once and back to the start. Any mention of travelling along every arc is B0 (WDM11 Jan 2025 Q6a, WDM11 Jan 2021 Q4a).
  • Interpreting a route: B1 for the full route with each leg expanded into actual roads (WDM11 Jun 2021 Q4b+c).

Often asked as: definitions; complete a table of least distances; interpret a route.

"Practical: vertices can be visited more than once" without making clear that revisiting is allowed, not required.

Confusing TSP (every vertex) with route inspection (every edge).

Spec3.3Upper and lower bounds using minimum spanning trees

Determination of upper and lower bounds using minimum spanning tree methods, including converting a network into a complete network of shortest distances.

Upper bound: the MST method

  1. Find the MST (Prim on the matrix is usual).
  2. Initial upper bound \(= 2 \times\) MST weight (walk "round" the tree, using each arc twice).
  3. Improve it with short cuts: replace part of the doubled walk by a direct arc, as long as the result is shorter and still visits every vertex.

Lower bound: deleted vertex method

  1. Delete a vertex and all its arcs.
  2. Find the MST of the remaining vertices.
  3. Add the two shortest arcs from the deleted vertex.

Any tour must contain two arcs at the deleted vertex plus a path joining the rest, which can't be lighter than an MST. Repeat with different deleted vertices; the largest result is the best lower bound.

both bounds (5 towns)

Using the matrix in 2.1 (MST AB, BC, CD, DE, weight 47):

Initial upper bound \(= 2 \times 47 = 94\).

Short cut: the doubled walk A–B–C–D–E–D–C–B–A ends with E–D–C–B–A (47). Replace it with EA (18): tour ABCDEA \(= 12 + 10 + 14 + 11 + 18 = 65\).

Lower bound, deleting A: MST of B, C, D, E is BC, DE, CD \(= 35\); two shortest arcs from A: 12, 15. Lower bound \(= 62\).

Deleting D: MST of A, B, C, E is AB, BC, CE \(= 38\); two shortest from D: 11, 14. Lower bound \(= 63\).

So far: \(63 \leqslant\) optimal \(\leqslant 65\).

  • M1 for doubling their MST weight, A1ft. Further wrong calculations after the answer are not ignored (WDM11 Jun 2025 Q2a+b).
  • Short cut: M1 for stating which arcs are replaced (or the calculation), A1 cao for the arcs and the new bound (WDM11A Jun 2026 Q7d).
  • Comparing bounds: "better because 203 is smaller than 206", dependent on a correct bound (WDM11 Jan 2021 Q4b+c).

Often asked as: very common (34 questions). Usually with the nearest neighbour algorithm (3.4) in the same question.

Saying a larger upper bound is better.

In the lower bound, using the MST of all vertices, or adding only one arc from the deleted vertex.

Spec3.4The nearest neighbour algorithm

The nearest neighbour algorithm.

The method

  1. Start at a given vertex.
  2. Travel to the nearest vertex not yet visited.
  3. Repeat until all vertices are visited, then return to the start.

The length of the tour is an upper bound. Starting from different vertices can give different tours; the shortest is the best upper bound.

The nearest neighbour route is quick to find but not guaranteed to be optimal. If it ever equals the best lower bound, it is optimal.

nearest neighbour (5 towns)

Same matrix. From A: nearest is B (12), then C (10), then D (14), then E (11), then back to A (18). ABCDEA \(= 65\).

From C: B (10), A (12), D (15), E (11), back to C (16). CBADEC \(= 64\).

Best upper bound 64, best lower bound 63 (from 3.3): \(63 \leqslant \text{optimal} \leqslant 64\). (The optimal tour here is in fact 64.)

  • M1 for nearest neighbour with the first few vertices right, A1 for one complete route including the return, with its length, A1 for both routes and lengths when there's a tie (WDM11A Jun 2026 Q7e).
  • Algebraic versions: the choices at each step give inequalities in \(x\); combine with "the bound is better than…" to find \(x\) (WDM11 Jun 2026 Q4).
  • Choosing the better of two routes with a reason based on the lengths (WDM11 Jun 2023 Q7c+d).

Often asked as: find tours from given starts; state the best upper bound; write down an interval for the optimal length.

Forgetting to return to the start.

Going to a vertex already visited because it's nearest.