Revision NotesExam QuestionsPast Papers
A LevelFurther Maths: Decision Maths 1EdexcelRevision NotesAlgorithms on GraphsThe Route Inspection AlgorithmRoute Inspection

Route Inspection (Edexcel A Level Further Maths: Decision Maths 1)

Revision Note

Naomi C

Author

Naomi C

Last updated

Chinese Postman Problem

What is the Chinese postman problem?

  • The route inspection problem is also known as the Chinese postman problem
  • You are required to find the route of least weight that traverses every edge in the graph such that the route starts and finishes at the same vertex
  • Some edges may need to be traversed twice and the challenge is to minimise the total weight of these repeated edges
  • Variations to the route inspection problem could involve
    • the start and finish vertices being different
    • certain edges being disregarded
      • e.g. a road closure
    • the route requiring repetition
      • e.g. a road sweeper covering both sides of the road

Networks with 0 or 2 Odd Nodes

How do I solve the Chinese postman problem?

  • If the graph is Eulerian
    • all of the vertices in the graph are even
      • i.e. 0 odd nodes
    • it will be possible to find an Eulerian circuit
      • i.e. a route that traverses each edge once only, starting and finishing at the same vertex
    • no route/edges will need repetition 
    • the shortest route will be the sum of the weights of the edges in the network
  • If the graph is semi-Eulerian
    • there will be one pair of odd vertices
      • i.e. 2 odd nodes
    • if the route has to start and end at the same vertex
      • the shortest path between the two odd nodes will need to be found
        • the edges making that route will need to be repeated
      • the shortest route will be the sum of the weights of the edges in the network plus the weight of the repeated edges
    • if the route starts at one of the odd vertices and ends at the other
      • no edges will need repetition
      • the shortest route will be the sum of the weights of the edges in the network

What are the steps of the Chinese postman algorithm?

  • STEP 1
    Inspect the degree of all of the vertices and identify any odd nodes
     
  • STEP 2
    If all of the vertices are even go to STEP 3
    If there is one pair of odd nodes, find the shortest path between them - the edges making this path will need repeating so add them to the graph
     
  • STEP 3
    Write down an Eulerian circuit of the adjusted graph to find a possible route
    • Find the sum of the edges traversed to find the total weight

Examiner Tip

  • Look carefully for the shortest path between two vertices
    • exam questions often have graphs where a path made up of several edges will create a shorter distance than a direct connection

Worked example

The network shown below displays the distance, in metres, of the cables in a network between different connection points A, B, C, D, E and F.

Each length of cable must be inspected.

jv2R5V-u_chinese-postman
 

a)
Find the shortest route that starts and finishes at connection point E.

  • STEP 1
    Inspect the order of the nodes
     
A: 5 (odd)
B: 2 (even)
C: 3 (odd)
D: 2 (even)
E: 4 (even)
F: 2 (even)

  • STEP 2
    There is exactly one pair of odd vertices, A and C
    The shortest route between A and C is ABC so the edges AB and BC need repeating
    An Eulerian circuit, starting and ending at connection point E, is now possible
     chinese-postman-2
  • STEP 3
    Find an Eulerian circuit, starting and ending at connection point E
Shortest route: EFAEDABACBCE

b)
State the total length of the shortest route.
 
Add together the lengths of the edges in the original graph
 
3 + 4 + 4 + 5 + 8 + 9 + 11 + 13 + 16 = 73
 
Add the result to the lengths of the repeated edges
 
73 + 5 + 9 = 87
 
Shortest route = 87 km

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

    Test yourself

    Did this page help you?

    Previous:Comparing Dijkstra's & Floyd's AlgorithmsNext:Route Inspection & Repeated Routes
    Naomi C

    Author: Naomi C

    Expertise: Maths

    Naomi graduated from Durham University in 2007 with a Masters degree in Civil Engineering. She has taught Mathematics in the UK, Malaysia and Switzerland covering GCSE, IGCSE, A-Level and IB. She particularly enjoys applying Mathematics to real life and endeavours to bring creativity to the content she creates.