Route Inspection & Repeated Routes | Edexcel A Level Further Maths: Decision Maths 1 Revision Notes 2017

Networks with more than 2 Odd Nodes

How do I solve the Chinese postman problem when the network has more than 2 odd nodes?

In any graph there will always be an even number of odd nodes
- the total sum of the degrees of the nodes is double the number of edges
If there are more than two odd nodes, the shortest route between each possible pairing of the odd nodes must be considered in order to find the minimum weight of the routes/edges that need to be repeated
- In cases of four odd nodes, there will be three such pairings
- For example in a graph where the four odd nodes are P, Q, R and S the pairings would be
  - PQ and RS
  - PR and QS
  - PS and QR
- In questions where there are more than four odd vertices, additional information will be given (such as a different start and end vertex) that essentially reduces the problem to four odd nodes
  - (There are 15 pairings to consider for 6 odd vertices!)

What are the steps of the Chinese postman algorithm for networks with more than 2 odd nodes?

STEP 1
Inspect the degree of all nodes and identify any odd nodes
STEP 2
Find all the possible pairings between the odd nodes
STEP 3
For each possible pairing of odd nodes, find (by inspection) the shortest route between them
The shortest of these routes will be repeated so add any repeated edges required to the network
STEP 4
Write down an Eulerian circuit of the adjusted network to find a possible route
- Find the sum of the edges traversed to find the total weight

What variations may there be on the Chinese postman algorithm?

A variation on the 4 odd nodes problem is that the start and end nodes can be any two of the odd nodes
- The problem is to find the shortest route and the corresponding start and end nodes
- To solve this problem
  - find the length of the routes for all possible pairings of the odd nodes
  - choose the shortest route between any 2 of them to be repeated
  - the other two odd vertices will be your start and finish points
Another variation may be that the weighting of an edge between a pair of nodes may be different depending on if it is the first time it is being traversed or a repeat
- For example, if an inspector was checking a pipeline for defects then the first time going along a section of pipeline could take longer during inspection than if it is being repeated simply to get from one node to another

Worked example

The network shown below displays the distances, in kilometres, of the main roads between towns A, B, C, D and E.
Each road is to be inspected for potholes.

chinese-postman-example-2

Explain why the network does not contain an Eulerian circuit.

Inspect the degree of each node

A: 3 (odd)
B: 3 (odd)
C: 3 (odd)
D: 3 (odd)
E: 2 (even)

The graph does not contain an Eulerian circuit as some of the vertices are odd

Find the shortest route that starts and finishes at town A and allows for each road to be inspected.

STEP 1
There are 4 odd nodes, A, B, C and D

STEP 2
The possible pairings between the odd nodes are AB and CD, AC and BD and AD and BC

STEP 3
By inspection, find the shortest route (and edges involved) between each pairing

AB + CD = (ABD) + (CD) = 12 + 10 = 22

AC + BD = (ADC) + (BD) = 18 + 4 = 22

AD + BC = (AD) + (BC) = 8 + 9 = 17

\underset{}{\leftarrow}

shortest

The shortest of these routes is AD and BC, so add the edges AD and BC to the graph
chinese-postman-example-2-2

STEP 4
Write down an Eulerian circuit (from the adjusted graph) starting at vertex A

Eulerian circuit: ADABDCBCEA
There are other possible Eulerian circuits that you could find

State the total length of the shortest route.

Add the length of each edge in the graph, then add the weight of the repeated edges.

15 + 17 + 8 + 4 + 9 + 10 + 6 = 69 (edges in the original graph)

17 (repeated edges)

Total length of the shortest route: 86 km

Route Inspection & Repeated Routes (Edexcel A Level Further Maths: Decision Maths 1)

Revision Note

Networks with more than 2 Odd Nodes

How do I solve the Chinese postman problem when the network has more than 2 odd nodes?

What are the steps of the Chinese postman algorithm for networks with more than 2 odd nodes?

What variations may there be on the Chinese postman algorithm?

Worked example

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

Join the 100,000+ Students that ❤️ Save My Exams

Author: Naomi C