The Route Inspection Algorithm

Revise The Route Inspection Algorithm for Further Decision Mathematics 1 WDM11 (AS Level) — revision notes and instant AI marking.

📖 Revision notes · preview

Edexcel A Level Further Maths — Decision 1

The Route Inspection Algorithm

The big idea: Imagine you're a postman who has to walk down every single street in a neighbourhood and get back to where you started. If some streets have to be walked twice because the network of roads doesn't "join up nicely," this chapter is all about finding the smart way to figure out which streets to repeat so your total walking distance is as small as possible.

Summary — What This Chapter Covers

The Route Inspection Problem (a.k.a. the Chinese Postman Problem) asks for the shortest route that travels along every edge of a graph and returns to the start.
Whether you need to repeat any edges depends entirely on the degree (order) of each vertex — specifically, how many vertices have an odd degree.
0 odd vertices → the graph is Eulerian → no repeats needed at all.
2 odd vertices → the graph is semi-Eulerian → you must repeat the shortest path connecting those two odd vertices.
More than 2 odd vertices (always an even number of them) → you must test every possible way of pairing them up, and repeat whichever pairing gives the smallest total.
The final answer = (sum of all edge weights in the original graph) + (sum of the weights of the repeated edges).

1. What Actually Is the Chinese Postman Problem?

Picture a real postman. Every morning he has to walk down every road on his route to deliver letters. He starts at the depot, and he has to end back at the depot. Naturally, he wants to walk the shortest possible total distance while still covering every road at least once.

The catch: road networks are messy. Sometimes the layout of roads means it's mathematically impossible to walk every road exactly once and return to the start — some roads will have to be walked twice. The question the algorithm answers is: which roads should be repeated to keep the extra distance as small as possible?

Formal definition

Given a weighted graph, find the route of least total weight that:

Traverses every edge in the graph at least once, and
Starts and finishes at the same vertex.

Key phrase to remember Minimise the total weight of repeated edges — you can't avoid walking every edge once, so the only thing you're actually optimising is which edges get walked twice.

Common variations you might be asked about

Different start and finish vertices — e.g. a delivery van starts at the depot but ends its shift at home.
Edges disregarded — e.g. a particular road is closed for roadworks, so it's removed from the graph entirely.
Routes that require deliberate repetition — e.g. a road-sweeping lorry that has to sweep both sides of every road, meaning every edge is effectively walked twice on purpose (this doubles every edge weight rather than looking for odd vertices).

Quick analogy Think of it like tracing a shape without lifting your pencil and without going over any line twice. Some shapes you can trace perfectly (like a figure-8 or a triangle) — others you simply can't, no matter how hard you try, because of how the lines meet at each point. That "can I trace it cleanly?" question is exactly what checking vertex degrees tells you.

2. The Golden Rule: Count the Odd Vertices

every vertex degree order even degree odd degree

Eulerian circuit

Useful fact — always true any

🔓 Read the full The Route Inspection Algorithm note → You're seeing the preview · sign in to read it all

Also in the full note

Worked Example — Cable Network (2 Odd Vertices)
Worked Example — Pothole Inspection (4 Odd Vertices)

What's inside

📖 Revision notes 🎯 Learn mode ✦ AI flashcards ✓ Instant AI marking 🧊 3D explorers 🧪 Experiments & simulations 📈 Progress tracking

📄 Practise The Route Inspection Algorithm with Further Decision Mathematics 1 WDM11 past papers Every paper with its mark scheme — answer online, marked instantly. Open →

Read the full The Route Inspection Algorithm notes free

That's the preview — create a free account to read the rest, plus flashcards and practice questions with instant AI marking. No credit card.

Unlock the full notes free →

The Route Inspection Algorithm