4 - Route Inspection Flashcards
Define Eulerian graph/network.
Has a trail that contains every edge and starts and finishes at the same vertex - all vertices of even degree.
Define Eulerian circuit.
Trail of an Eulerian graph.
Define semi-Eulerian graph/network.
Has a trail including every edge but starts and finishes at different vertices - two vertices of odd degree.
What if the graph is not connected/has more odd vertices?
Not Eulerian.
What does the route inspection algorithm do?
Find shortest route which traverses each arc at least once and returns to starting point.
What is the length of the shortest route if all vertices are of even degree?
Total weight of network.
What is the length of the shortest route if two of the vertices are of odd degree?
Total weight plus length of shortest path between the two odd vertices.
What is the route inspection algorithm?
.Identify odd vertices.
.Consider all complete pairings of these.
.Select complete pairing with least sum.
.Add arcs indicated by this pairing to the network.
