Decision 1 Unit 5

Question 1

What is the Chinese Postman algorithm used for?

Answer 1

When all arcs need to be used once and start/finish at same node.

Question 2

What type of graph is needed for the Chinese Postman algorithm?

Answer 2

Eularian (all nodes have even order)

Question 3

How do you create a Eularian graph if there are an even no. of odd nodes?

Answer 3

Find all possible pairings of odd nodes.

Find the least length between the pairs and add these arcs to the graph (because those routes will be repeated)