• Revision:Route Inspection

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Route Inspection



Route inspection is the problem of finding a least weight closed trail covering every arc of a network.

A route is traversable if and only if it is Eulerian (or semi-Eulerian). An Eulerian graph has nodes of even order only. In an Eulerian graph, the least weight path is the sum of all the arc weights.

To find the least weight path of non-Eulerian graphs we must first effectively make the graph Eulerian by adding arcs to make all nodes even. These newly added arcs are the routes that must be repeated to make the graph traversable. In this case the least weight path is the sum of all arc weights plus the sum of the repeated weights (i.e. the newly added weights).

Contents

The Chinese Postman algorithm

This algorithm produces the least weight closed trail containing every arc in a network, starting and ending at the same node.

  1. Find all nodes of odd order
  2. For every pair of odd nodes find the connecting path of minimum weight
  3. Group the odd nodes so that the sum of the weights is minimised
  4. Add the new minimum weight paths found in step 3 to the original graph.

Weight of closed trail = total weight of network + sum of minimum weight paths found in step 3

Example

Image:Route inspection question.jpg

  • Nodes of odd order are A, B, D and E
  • Pairings possible:
    • AB (20)
    • AD (30)
    • AE (25)
    • BD (32 + 40 = 72)
    • BE (45)
    • DE (35)
  • Groupings possible:
    • AB, DE (20 + 35 = 55)
    • AD, BE (30 + 45 = 75)
    • AE, BD (25 + 72 = 97)

Minimum weight grouping is AB, DE (55)

Image:Route inspection solution.jpg

  • Total weight of (original) network = 312
  • Minimum weight grouping = 55

Therefore, weight of closed trail = 312 + 55 = 367


Problems with the algorithm

As the number of odd nodes increases, the number of possible pairings to be considered increases dramatically. It is therefore impractical to do the algorithm by hand with more than 6 nodes. Even with a computer, it can become too time consuming - with 12 odd nodes there are 10395 combinations to consider.

Also See

See the other D1 notes:

  1. Algorithms
  2. Sorting algorithms
  3. Packing algorithms
  4. Graphs and networks
  5. Minimum connector problems
  6. The shortest path
  7. Route inspection
  8. The travelling salesman problem
  9. Linear programming
  10. The simplex algorithm

Comments

Try Learn together, TSR's study area

37,342
revision notes

41,529
mindmaps

42,712
crosswords

15,691
quizzes

create
a study planner

thousands
of discussions


Today on TSR
Poll
Would you ever go to a non Russell Group uni?
Study resources

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE