All flashcards topics

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

Card 1 of 120 of 12 known

Question

What is the Route Inspection problem?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards
What is the Route Inspection problem?
Finding the shortest closed route that traverses every arc of a network at least once.
What is the degree of a vertex?
The number of arc-ends meeting at the vertex.
How many odd vertices can a network have?
An even number, because the degrees add up to twice the number of arcs.
When is a network Eulerian?
When every vertex has even degree.
Shortest route in an Eulerian network?
The total weight of all the arcs, with no repeats.
Step 1 of the Route Inspection Algorithm?
Identify all the odd vertices.
How many pairings are there for 2 odd vertices?
One.
How many pairings are there for 4 odd vertices?
Three.
What is added to the total weight?
The least total for a pairing, using the shortest path for each pair.
Why is the direct arc not always used?
An indirect path between the odd vertices can be shorter.
What must you do if an arc is added?
Recount the degrees, because the odd vertices may change.
What if the network has more than four odd vertices?
Extra information limits the pairings you need to consider.

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
See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).