Y1 Decision - C4 - Route Inspection

Question 1

4.1 What is an Eulerian graph?

Answer 1

A network that contains a trail that includes every edge and starts and finishes at the same vertex. Any connected graph whose vertices are all even is Eulerian.

Question 2

4.1 What is a semi-Eulerian graph?

Answer 2

A network that contains a trail that includes every edge and starts and finishes at the same vertex. Any connected graph with two odd vertices is semi-Eulerian (one odd vertex is the start and the other is the end of the trail)

Question 3

4.2 What does the route inspection algorithm do?

Answer 3

Finds the length of the shortest route in a network that transverses every arc at least once, and returns to its starting point

Question 4

4.2 If a network is Eulerian, what can you say about the length of its shortest route that transverses every arc?

Answer 4

length of the shortest route = total weight of the network

Question 5

4.2 If a network is semi-Eulerian, what can you say about the length of its shortest route that transverses every arc?

Answer 5

length of the shortest route = total weight of the network plus the length of the shortest path between the two odd vertices

Question 6

4.2 Describe how to implement the route inspection algorithm

Answer 6

• Identify any odd vertices
• Consider all possible pairings of these pairings
• Select the complete pairing that has the least sum
• Add a repeat of the arcs indicated by this pairing to the network