10.5.1 Route Inspection

The Route Inspection Algorithm, also known as the Chinese Postman Problem, is a method for finding the shortest closed path that travels along every edge of a network at least once and returns to the starting vertex. This is often applied to solve problems involving postal routes, garbage collection, or street cleaning.

Key Steps in the Route Inspection Algorithm

Check Vertex Degrees
Pair Odd Nodes
Select the Optimal Pairing
Duplicate Edges
Construct the Route
Calculate the Total Distance

Check Vertex Degrees

Identify all vertices with an odd degree (an odd number of edges connected to them).
If all vertices have even degrees, the graph is Eulerian, and the solution is simply the sum of all edge weights.
If there are odd-degree vertices, the graph is semi-Eulerian, and adjustments are needed.

Pair Odd Nodes

List all vertices with odd degrees. There will always be an even number of odd vertices.
Consider all possible pairings of these odd vertices. For each pairing, calculate the total weight of the shortest paths connecting the paired nodes.

Select the Optimal Pairing

Choose the pairing of odd vertices that minimises the total weight of the added paths.

Duplicate Edges

Add the edges corresponding to the selected pairing into the graph, effectively "duplicating" them to make all vertices even-degree.

Construct the Route

Using the modified graph (where all vertices now have even degrees), construct the Eulerian circuit, which visits every edge at least once and returns to the starting vertex.

Calculate the Total Distance

The total distance of the route is the sum of all original edge weights plus the weights of the added edges.

Worked Example

lightbulbExample

Example Consider the graph below with edge weights:

Edge	Weight
A–B	4
A–C	3
B–C	2
B–D	6
C–D	5
C–E	7
D–E	4

Find the shortest route that visits every edge at least once and returns to the starting vertex.

Step 1: Check Vertex Degrees

The degrees of the vertices are:

\text{A: 2, B: 3, C: 4, D: 3, E: 2}

Vertices B and D have odd degrees.

Step 2: Pair Odd Nodes

The odd vertices are $B$ and $D$ . Since there are only two odd nodes, the only possible pairing is $B$ - $D$ .
Find the shortest path between $B$ and $D$ . From the table:

\text{Shortest path } B \to D = 6

Step 3**: Duplicate Edges**

Add the edge $B$ - $D$ again to the graph. This ensures all vertices have even degrees.

Step 4: Construct the Route

Using the modified graph, construct an Eulerian circuit. One possible circuit is:

A \to B \to C \to B \to D \to C \to E \to D \to A

Step 5**: Calculate the Total Distance**

Original edge weights:

4 + 3 + 2 + 6 + 5 + 7 + 4 = :highlight[31]

Added edge weight (for $B$ - $D$ ): 6
Total distance:

31 + 6 = :highlight[37]

Thus, the shortest route is 37 units long.

Note Summary

infoNote

Common Mistakes

Forgetting to Identify Odd Nodes Skipping the identification of vertices with odd degrees leads to incomplete or incorrect adjustments.
Incorrect Pairings Failing to consider all possible pairings of odd nodes or selecting a suboptimal pairing can result in a longer route.
Overlooking Shortest Paths Using non-optimal paths between odd nodes when calculating pairings increases the route length unnecessarily.
Not Constructing a Circuit Forgetting to construct a closed route that starts and ends at the same vertex leads to an incomplete solution.
Neglecting to Add Edge Weights Omitting the weights of duplicated edges when calculating the total distance results in an incorrect total.

infoNote

Key Formulas/Theorems

Eulerian Graph: A graph is Eulerian if all vertices have even degrees, and the total distance is the sum of the original edge weights.
Semi-Eulerian Graph: A graph with exactly two odd-degree vertices requires duplication of edges to make it Eulerian.
Shortest Path for Pairing:

\text{Added Weight} = \min(\text{weights of all possible odd vertex pairings})

Total Route Distance:

\text{Total Distance} = \text{Sum of Original Edge Weights} + \text{Sum of Added Edge Weights}

Constructing the Circuit: Use an Eulerian circuit algorithm to find the final route after adjustments.

Route Inspection Simplified Revision Notes for A-Level Edexcel Further Maths Decision Maths 1