Edexcel IAL - Decision Mathematics 1- 3.1 Shortest Route Visiting Every Edge (Route Inspection)- Study notes - New syllabus
Edexcel IAL – Decision Mathematics 1- 3.1 Shortest Route Visiting Every Edge (Route Inspection) -Study notes- New syllabus
Edexcel IAL – Decision Mathematics 1- 3.1 Shortest Route Visiting Every Edge (Route Inspection) -Study notes -Edexcel A level Maths- per latest Syllabus.
Key Concepts:
- 3.1 Shortest Route Visiting Every Edge (Route Inspection)
Chinese Postman Problem (Shortest Route Covering All Edges)
The Chinese postman problem is concerned with finding the shortest possible route around a network that:
- travels along every edge at least once
- starts and ends at the same vertex
This type of route is useful for problems such as street sweeping, rubbish collection, postal delivery, and inspection routes.
Key Idea
If every vertex in a network has even degree, then it is possible to find a route that uses each edge exactly once and returns to the start. This route is called an Eulerian circuit.
If the network has vertices of odd degree, some edges must be repeated in order to complete such a route.
Odd Vertices
In the syllabus, networks will have:
- 0 odd vertices, or
- 2 odd vertices, or
- 4 odd vertices
Only cases with up to four odd vertices will be examined.
Overall Strategy
The shortest route is found by:
- Finding the total weight of all edges in the network
- Identifying all vertices with odd degree
- Pairing odd vertices so that the extra distance added is minimal
- Adding this minimum extra distance to the total edge weight
Case 1: No Odd Vertices
If there are no odd vertices, the network already has an Eulerian circuit.
$\text{Shortest route length = sum of all edge weights}$
No edges need to be repeated.
Case 2: Two Odd Vertices
If there are two odd vertices, one additional path must be duplicated to make all degrees even.
- Find the shortest path between the two odd vertices
- Add this distance to the total edge weight
The resulting route starts and ends at the same vertex.
Case 3: Four Odd Vertices
If there are four odd vertices, two pairs of vertices must be joined.
There are three possible pairings of four odd vertices.
Students are expected to use inspection to:
- List all possible pairings
- Find the total added distance for each pairing
- Choose the pairing with the smallest total distance
The shortest route length is then:
$\text{total weight of all edges + minimum extra distance}$
Important Syllabus Notes
- The route must start and end at the same vertex
- Only inspection is required for pairing odd vertices
- Use of Floyd’s algorithm is not required
- Clear identification of odd vertices and pairings is essential
Example
A network has the following edge weights:
AB(5), BC(4), CD(6), DA(7)
Find the length of the shortest route that travels along every edge at least once and returns to the starting vertex.
▶️ Answer / Explanation
Degree of each vertex:
A: 2, B: 2, C: 2, D: 2
All vertices have even degree.
Conclusion:
The network already has an Eulerian circuit.
Shortest route length =
\( \mathrm{5 + 4 + 6 + 7 = 22} \)
Example
A network has edge weights:
AB(3), BC(5), CD(4), DA(6), AC(2)
Find the shortest route that starts and ends at the same vertex and travels along every edge at least once.
▶️ Answer / Explanation
Degrees of vertices:
A: 3, B: 2, C: 3, D: 2
Odd vertices are A and C.
Total weight of all edges:
\( \mathrm{3 + 5 + 4 + 6 + 2 = 20} \)
Shortest path between odd vertices A and C is:
AC(2)
Conclusion:
Shortest route length =
\( \mathrm{20 + 2 = 22} \)
Example
A network has vertices A, B, C, D with the following shortest distances between odd vertices:
AB = 6, AC = 5, AD = 7, BC = 4, BD = 3, CD = 8
The total weight of all edges in the network is 40.
Find the length of the shortest route that travels along every edge at least once and returns to the starting vertex.
▶️ Answer / Explanation
Odd vertices are A, B, C, D.
Possible pairings:
(AB + CD) = \( \mathrm{6 + 8 = 14} \)
(AC + BD) = \( \mathrm{5 + 3 = 8} \)
(AD + BC) = \( \mathrm{7 + 4 = 11} \)
Minimum additional distance is 8.
Conclusion:
Shortest route length =
\( \mathrm{40 + 8 = 48} \)