4 - Route inspection

Question 1

Define a Eulerian graph.

Answer 1

A graph which contains a trail that includes every edge and starts and finished at the same vertex. This is an Eulerian circuit. Any connected graph whose vertices are all even is Eulerian.

Question 2

Define a semi-Eulerian graph.

Answer 2

A graph which contains a trail that includes every edge but start and finished at different vertices. Any connected graph with exactly two odd vertices is semi-Eulerian.

Question 3

In what case, is the length of the shortest route equal to the the total weight of the network.?

Answer 3

If all vertices are even. (A Eulerian graph.)

Question 4

What does the route inspection (Chinese postman) algorithm seek to do?

Answer 4

Find the shortest route in a network that traverses every arc at least once and returns to its starting point.

Question 5

What is the length of the shortest route which covers every arc equal to, when there are exactly 2 odd nodes?

Answer 5

Total weight of network + shortest route between two odd nodes

Question 6

Describe the route inspection algorithm.

Answer 6

1. Identify all nodes with odd degree
2. Consider all possible complete pairings of these nodes
3. Select complete pairing that has the smallest sum
4. Add a repeat of the arcs indicated by this pairing to the network.