Route Inspection (Edexcel A-Level Further Mathematics): Revision Notes
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
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:
- Vertices B and D have odd degrees.
Step 2: Pair Odd Nodes
- The odd vertices are and . Since there are only two odd nodes, the only possible pairing is -.
- Find the shortest path between and . From the table:
Step 3**: Duplicate Edges**
- Add the edge - 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:
Step 5**: Calculate the Total Distance**
- Original edge weights:
- Added edge weight (for-): 6
- Total distance:
Thus, the shortest route is 37 units long.
Note Summary
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.
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:
- Total Route Distance:
- Constructing the Circuit: Use an Eulerian circuit algorithm to find the final route after adjustments.