What is the route inspection problem ?

The route inspection problem, also known as the Chinese postman problem , is to find the route of least weight that travels along every edge of a graph and returns to its starting vertex. Some edges may have to be covered more than once, and the aim is to keep the total weight of those repeats as small as possible.

A network has exactly two odd vertices, and the route must start and finish at the same vertex. What has to be repeated?

The shortest path between the two odd vertices , whose edges are then added to the graph. The length of the route is the sum of every edge in the network plus the weight of that repeated path.

Why does repeating the shortest path between the two odd vertices make a closed inspection route possible?

Each repeated edge adds one to the degree at both of its ends, so the two odd vertices gain one each and turn even, while every vertex in the middle of the path gains two and keeps the parity it already had. With no odd vertices left, the adjusted graph is Eulerian and a closed route using every edge now exists.

True or False? A route inspecting every edge of a network with two odd vertices can sometimes avoid repeating any edge at all.

True. If the route is allowed to start at one odd vertex and finish at the other , it is an Eulerian trail and nothing needs repeating. Repetition is only forced when the route has to begin and end at the same vertex.

Why should you not assume that the direct edge is the shortest path between two odd vertices?

A path made up of several shorter edges can easily total less than one long direct edge. Every route between the two odd vertices has to be compared, not just the one joining them directly.

What variations on the route inspection problem can arise?

The start and finish vertices may be different from one another, or certain edges may be disregarded , for instance because of a road closure. Repetition may even be required rather than avoided, as for a road sweeper that has to cover both sides of every road.

A network has four odd vertices. What must you consider before you can decide which edges to repeat?

All the possible pairings of the odd vertices, and the shortest path between the two vertices making up each pair. For odd vertices P, Q, R and S the pairings are PQ with RS, PR with QS, and PS with QR.

True or False? A network can have an odd number of odd vertices.

False. The number of odd vertices in any graph is always even. That is exactly why the odd vertices can always be split into pairs with none left over, which is what makes the pairing method work at all.

Once you have all the pairings, which one decides the edges to repeat?

The pairing whose two shortest paths add to the smallest total . Those two paths are the ones repeated, and their edges are added into the network.

The repeated edges have been added to the network. How do you finish the route inspection problem?

Write down an Eulerian circuit of the adjusted network, which is now possible because adding those paths has made every vertex even. Any such circuit is a valid answer, and there is usually more than one to choose from.

With four odd vertices, the route may start and finish at any two of them. How does that change the method?

Find the shortest paths for all the pairings as usual, then repeat only the single shortest of those paths. The two odd vertices it does not touch become the start and finish points, since a route is allowed to begin and end at odd vertices.

How can the weight of an edge depend on whether it is being repeated?

A first traversal may cost more than a second one along the same edge. An inspector walking a pipeline takes longer over a section being checked than over one already inspected, so the return journey along it carries a smaller weight.

International A Level (IAL)MathsEdexcelDecision 1FlashcardsAlgorithms on GraphsThe Route Inspection Algorithm

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

Exam code: YMA01

1/15

0Still learning

Know0

FrontRoute Inspection
What is the route inspection problem?

Was this flashcard helpful?

Cards in this collection (15)

What is the route inspection problem?
The route inspection problem, also known as the Chinese postman problem, is to find the route of least weight that travels along every edge of a graph and returns to its starting vertex.
Some edges may have to be covered more than once, and the aim is to keep the total weight of those repeats as small as possible.
A network has no odd vertices at all. Complete the conclusion:
The graph is $______$ so a closed route using every edge exactly once already exists, and nothing has to be repeated.
The completed conclusion is:
The graph is Eulerian so a closed route using every edge exactly once already exists, and nothing has to be repeated.
The length of the shortest inspection route is then simply the sum of the weights of all the edges in the network.
A network has exactly two odd vertices, and the route must start and finish at the same vertex. What has to be repeated?
The shortest path between the two odd vertices, whose edges are then added to the graph.
The length of the route is the sum of every edge in the network plus the weight of that repeated path.
Why does repeating the shortest path between the two odd vertices make a closed inspection route possible?
Each repeated edge adds one to the degree at both of its ends, so the two odd vertices gain one each and turn even, while every vertex in the middle of the path gains two and keeps the parity it already had.
With no odd vertices left, the adjusted graph is Eulerian and a closed route using every edge now exists.
True or False?
A route inspecting every edge of a network with two odd vertices can sometimes avoid repeating any edge at all.
True.
If the route is allowed to start at one odd vertex and finish at the other, it is an Eulerian trail and nothing needs repeating.
Repetition is only forced when the route has to begin and end at the same vertex.
Why should you not assume that the direct edge is the shortest path between two odd vertices?
A path made up of several shorter edges can easily total less than one long direct edge.
Every route between the two odd vertices has to be compared, not just the one joining them directly.
The edges of a network total $73$ , and its two odd vertices are joined by a shortest path of weight $14$ . How long is the shortest closed inspection route?
The route has length $73 + 14 = 87$ .
The weight of the repeated path is added to the total of every edge, because each repeated edge is travelled a second time.
What variations on the route inspection problem can arise?
The start and finish vertices may be different from one another, or certain edges may be disregarded, for instance because of a road closure.
Repetition may even be required rather than avoided, as for a road sweeper that has to cover both sides of every road.
A network has four odd vertices. What must you consider before you can decide which edges to repeat?
All the possible pairings of the odd vertices, and the shortest path between the two vertices making up each pair.
For odd vertices P, Q, R and S the pairings are PQ with RS, PR with QS, and PS with QR.
True or False?
A network can have an odd number of odd vertices.
False.
The number of odd vertices in any graph is always even.
That is exactly why the odd vertices can always be split into pairs with none left over, which is what makes the pairing method work at all.
Complete the count of pairings for a network with four odd vertices:
Four odd vertices can be split into $______$ different pairings, and each pairing uses up all $______$ of the odd vertices.
The completed count is:
Four odd vertices can be split into three different pairings, and each pairing uses up all four of the odd vertices.
Every odd vertex has to be paired off, since any left odd would still block a closed route.
Once you have all the pairings, which one decides the edges to repeat?
The pairing whose two shortest paths add to the smallest total.
Those two paths are the ones repeated, and their edges are added into the network.
The repeated edges have been added to the network. How do you finish the route inspection problem?
Write down an Eulerian circuit of the adjusted network, which is now possible because adding those paths has made every vertex even.
Any such circuit is a valid answer, and there is usually more than one to choose from.
With four odd vertices, the route may start and finish at any two of them. How does that change the method?
Find the shortest paths for all the pairings as usual, then repeat only the single shortest of those paths.
The two odd vertices it does not touch become the start and finish points, since a route is allowed to begin and end at odd vertices.
How can the weight of an edge depend on whether it is being repeated?
A first traversal may cost more than a second one along the same edge.
An inspector walking a pipeline takes longer over a section being checked than over one already inspected, so the return journey along it carries a smaller weight.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:Shortest Path AlgorithmsNext:The Travelling Salesman Problem