Route Inspection Flashcards
1
Q
What is a Eulerian graph?
A
A network which contains a trail that includes every arc and starts and finishes at the same node.
2
Q
What are the Valencies of nodes in a Eulerian graph?
A
Even
3
Q
What is a semi Eulerian graph?
A
A network which contains a trail that includes every arc but starts and finishes at different nodes.
4
Q
What makes a graph semi Eulerian?
A
When it has exactly two nodes of odd Valencies
5
Q
What does route inspection do?
A
Finds the shortest route in a network that transverses every arc at least once and returns to its starting point
6
Q
How do you follow the route inspection algorithm?
A
- Identify any vertices with odd degree
- consider all possible complete pairings of these vertices
- Select the complete pairing that has the least sum
- Add a repeat of the arcs indicated by this pairing to the network
