4. Route Inspection

Question 1

Define the term Eulerian graph/network

Answer 1

One which contains a trail that includes every edge and starts and finishes at the same vertex (called an Eulerian circuit)

Question 2

When is a graph Eulerian?

Answer 2

When the graph is connected and the graph’s vertices are all even

Question 3

Define the term semi-Eulerian graph/network

Answer 3

One which contains a trail that includes every edge but starts and finishes at different vertices

Question 4

When is a graph semi-Eulerian?

Answer 4

When the graph is connected and exactly two vertices are odd

Question 5

What is the route inspection algorithm used for?

Answer 5

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

Question 6

If all the vertices in a network have an even degree, what is the length of the shortest route?

Answer 6

The total weight of the network

Question 7

If a network has exactly 2 odd vertices, what is the length of the shortest route?

Answer 7

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

Question 8

If a network has more than two odd vertices, what do you do?

Answer 8

Consider all the possible pairings of the odd vertices

Question 9

What are the steps to the route inspection algorithm?

Answer 9

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