Decision Chapter 4: Route Inspection

9 flashcards · Mathematics · by TheoTyson

1. Eulerian Graph

   A trail that includes every edge and starts and ends at the same vertex.

2. A graph is Eulerian when...

   All of the vertices have an even degree.

3. Semi-Eulerian Graph

   A trail that includes every edge but starts and ends at different vertices.

4. A graph is semi-Eulerian when...

   Exactly two vertices have an odd degree.

5. Start and End Points of a Semi-Eulerian Graph

   The trail starts and ends at the odd vertices.

6. Function of the Route Inspection Algorithm

   Finds the shortest route in a network that includes every edge at least once and returns to the starting point.

7. Route Inspection Algorithm - Eulerian Graph

   The length of the shortest route is equal to the total weight of the network.

8. Route Inspection Algorithm - Semi-Eulerian Graph

   The length of the shortest route is equal to the total weight of the network plus the length of the shortest path between the two odd vertices.

9. Route Inspection Algorithm - Non-Eulerian Graph

   Identity any vertices with odd degree. Consider all pairings of these vertices. Select the pairing with the lowest weight. Add a repeat of the edges in the pairing to the network.