The Route Inspection (Chinese Postman) problemEdexcel A-Level Further Maths: Mind map

Exam questions on The Route Inspection (Chinese Postman) problem

1. A network has vertices A, B, C, D and E. The arcs and their weights are: AB 5, AC 7, BC 4, BD 6, CD 3, CE 8 and DE 5.
   Find the length of the shortest route that starts and ends at A and uses every arc at least once.2 marks
2. A network has vertices A, B, C, D, E and F. The arcs and their weights are: AB 8, BC 6, CD 9, DE 7, EF 5, FA 10, BE 12 and CF 11.
   State which arcs are repeated and find the length of the shortest route that starts and ends at A and uses every arc at least once.2 marks
3. A council must inspect every road in a village. The junctions are A, B, C, D, E and F and the road lengths in km are: AB 3, AC 5, BC 2, BD 7, CD 4, CE 7, DF 5 and EF 3. The inspector starts and finishes at junction A.
   Find the length of the shortest inspection route.3 marks