Decision 4 - Route Inspection Flashcards
What is an Eulerian graph?
An Eulerian graph or network is one which contains a trail that includes every edge and starts and finishes at the same vertex. This trail is called an Eulerian circuit, often called an Eulerian cycle. Any connected graph whose vertices are all even is Eulerian.
What is a semi-Eulerian graph?
A semi-Eulerian graph or network is one which contains a trail that includes every edge but starts and finishes at different vertices. Any connected graph with exactly two odd vertices is semi-Eulerian.
What is the route inspection algorithm?
The route inspection algorithm, or Chinese postman algorithm, can be used to find the shortest route in a network that traverses every arc at least once and returns to its starting point.
•If all the vertices in the network have even degree, then the length of the shortest route will be equal to the total weight of the network.
If a network has exactly two odd vertices, then the length of the shortest route will be equal to the total weight of the network, plus the length of the shortest path between the two odd vertices.
The algorithm:
1) Identify any vertices with 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.
