# Decision - Route Inspection Flashcards

What is a Eulerian graph?

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.

What determines whether a graph is Eulerian?

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

What is a semi-Eulerian graph?

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)

What determines whether a graph is semi-Eulerian?

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

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

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**

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)?

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

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

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

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

The weight of the graph