Define the route inspection problem .

The route inspection problem, also called the Chinese postman problem , is to find the route of least weight that traverses every edge of a network and returns to its starting vertex. Some edges may have to be travelled twice, and the aim is to keep the total weight of those repeats as small as possible.

What variations on the route inspection problem might a question use?

The start and finish vertices may be different , or certain edges may be disregarded , such as a closed road. Some edges may also have to be repeated deliberately , as when a road sweeper covers both sides of a road.

What is the shortest route inspection route when every vertex of a network is even?

The shortest route is simply the sum of the weights of all the edges , with no repeats needed at all. The network is Eulerian, so a circuit exists that covers every edge exactly once and returns to the start.

A network has exactly two odd vertices and the route must return to its start. What has to be repeated?

The edges making up the shortest path between the two odd vertices have to be repeated. Adding those edges makes every vertex even, so an Eulerian circuit through the adjusted network becomes possible.

True or False? With exactly two odd vertices, edges must always be repeated.

False. If the route is allowed to start at one odd vertex and finish at the other , nothing needs repeating at all. Repeats become necessary only when the route has to return to where it started.

What are the steps of the route inspection algorithm?

Find the degree of every vertex and identify the odd ones, then find the shortest path between the odd pair and add those edges to the network as repeats. Finally write down an Eulerian circuit of the adjusted network and add up the weights traversed.

When repeating edges, why must you look for the shortest path rather than the direct edge?

A path made up of several edges is often shorter than the single direct edge between the same two vertices. Taking the direct edge without checking gives a heavier repeat than necessary, and so a total that is too large.

A network has four odd vertices P, Q, R and S. How many pairings must be considered, and what are they?

There are three pairings: PQ with RS, PR with QS, and PS with QR. Each pairing splits the four odd vertices into two pairs, and the shortest path within each pair is what would be repeated.

Having listed the pairings of four odd vertices, what do you do next?

For each pairing, find the shortest path between the two vertices in each pair and add those two lengths together. The pairing with the smallest total is the one whose edges get repeated.

True or False? A network with six odd vertices gives fifteen pairings to consider.

True. That is far too many to work through by hand, so a question with more than four odd vertices always supplies extra information. That information, such as a fixed start and finish, reduces the problem to four odd vertices in practice.

The route may start and finish at any two of four odd vertices. How is the shortest route found?

Find the lengths for all the pairings as usual, then repeat the edges of the shortest single pair . The other two odd vertices become the start and the finish, since a route running between two odd vertices needs no repeats.

What changes if an edge has a different weight the second time it is travelled?

The repeat weight is used when costing that repetition, rather than the original weight. An inspector checking a pipeline, for instance, might cover a section faster the second time because there is nothing left to inspect.

A LevelFurther MathsEdexcelDecision 1FlashcardsAlgorithms on GraphsThe Route Inspection Algorithm

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

Exam code: 9FM0

1/13

0Still learning

Know0

FrontRoute Inspection
Define the route inspection problem.

Was this flashcard helpful?

Cards in this collection (13)

Define the route inspection problem.
The route inspection problem, also called the Chinese postman problem, is to find the route of least weight that traverses every edge of a network and returns to its starting vertex.
Some edges may have to be travelled twice, and the aim is to keep the total weight of those repeats as small as possible.
What variations on the route inspection problem might a question use?
The start and finish vertices may be different, or certain edges may be disregarded, such as a closed road.
Some edges may also have to be repeated deliberately, as when a road sweeper covers both sides of a road.
What is the shortest route inspection route when every vertex of a network is even?
The shortest route is simply the sum of the weights of all the edges, with no repeats needed at all.
The network is Eulerian, so a circuit exists that covers every edge exactly once and returns to the start.
A network has exactly two odd vertices and the route must return to its start. What has to be repeated?
The edges making up the shortest path between the two odd vertices have to be repeated.
Adding those edges makes every vertex even, so an Eulerian circuit through the adjusted network becomes possible.
True or False?
With exactly two odd vertices, edges must always be repeated.
False.
If the route is allowed to start at one odd vertex and finish at the other, nothing needs repeating at all.
Repeats become necessary only when the route has to return to where it started.
What are the steps of the route inspection algorithm?
Find the degree of every vertex and identify the odd ones, then find the shortest path between the odd pair and add those edges to the network as repeats.
Finally write down an Eulerian circuit of the adjusted network and add up the weights traversed.
When repeating edges, why must you look for the shortest path rather than the direct edge?
A path made up of several edges is often shorter than the single direct edge between the same two vertices.
Taking the direct edge without checking gives a heavier repeat than necessary, and so a total that is too large.
A network has four odd vertices P, Q, R and S. How many pairings must be considered, and what are they?
There are three pairings: PQ with RS, PR with QS, and PS with QR.
Each pairing splits the four odd vertices into two pairs, and the shortest path within each pair is what would be repeated.
Having listed the pairings of four odd vertices, what do you do next?
For each pairing, find the shortest path between the two vertices in each pair and add those two lengths together.
The pairing with the smallest total is the one whose edges get repeated.
Complete the total weight of the shortest route inspection route:
$total = sum of all edge weights +______$
The completed result is:
$total = sum of all edge weights + weight of the repeated edges$
Every edge has to be walked at least once, so the repeats are the only extra distance involved.
True or False?
A network with six odd vertices gives fifteen pairings to consider.
True.
That is far too many to work through by hand, so a question with more than four odd vertices always supplies extra information.
That information, such as a fixed start and finish, reduces the problem to four odd vertices in practice.
The route may start and finish at any two of four odd vertices. How is the shortest route found?
Find the lengths for all the pairings as usual, then repeat the edges of the shortest single pair.
The other two odd vertices become the start and the finish, since a route running between two odd vertices needs no repeats.
What changes if an edge has a different weight the second time it is travelled?
The repeat weight is used when costing that repetition, rather than the original weight.
An inspector checking a pipeline, for instance, might cover a section faster the second time because there is nothing left to inspect.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:Shortest Path AlgorithmsNext:The Travelling Salesman Problem