Decision - Route Inspection

Question 1

What is a Eulerian graph?

Answer 1

A graph which contains a trail that includes every edge and starts and finishes at the same vertex. This trail is called a Eulerian Circuit.

Question 2

What determines whether a graph is Eulerian?

Answer 2

A graph is Eulerian if it is a connected graph whose vertices are all even

Question 3

What is a semi-Eulerian graph?

Answer 3

A graph which contains a trail that includes every edge but starts and finishes at different vertices. (It must start at 1 odd vertex and finish at the other odd vertex)

Question 4

What determines whether a graph is semi-Eulerian?

Answer 4

A graph is semi-Eulerian if it contains exactly 2 odd vertices

Question 5

What is the weight of the shortest trail beggining and ending at the same vertex when there are 2 odd vertices (semi-eulerian graph)?

Answer 5

the length of the shortest route will be equal to the total weight of the network + length of shortest route between the 2 odd vertices

Question 6

What is the route inspection algorithm to find the shortest trail beggining and ending at the same vertex when there are 4 odd vertices (non-eulerian graph)?

Answer 6

1. Identify any vertices with odd degrees
2. Consider all possible pairings of there 4 vertices (3 possible combinations)
3. Select the complete pairing that has the lowest sum (of the weights)
4. Add in (sketch) a repeat of the arcs indicated by this pairing to the network
5. Find Route

Question 7

What is the weight of the shortest trail beggining and ending at the same vertex when there are 4 odd vertices (non-eulerain graph)?

Answer 7

the length of the shortest route will be equal to the total weight of the network + length of shortest pairing of the odd vertices

Question 8

What is the weight of the shortest trail beggining and ending at the same vertex in a grpah containing no odd vertices (Eulerian graph)?

Answer 8

The weight of the graph