Chapter 4: Route Inspection Flashcards
What is a Eulerian graph?
All nodes in the graph have an even degree
A eulerian graph contains a trail that includes every edge and starts and finishes at same vertex
What is a semi-eulerian graph?
All nodes in the graph have an even degree except for up to two nodes.
A trail covering every edge exactly once must start at one odd node and end at the othet
What is a non eulerian graph?
More than two vertices have an odd degree
It is impossible to draw the graph without removing your pen from the page or repeating an edge
What does traversable mean?
Eulerian graphs are traversable which means which means you can draw along each edge once without taking your pen off the paper
Semi eulerian graphs are traversable
If you start at an odd node and end at an odd node
What is the route inspection algorithm?
It can be used to find the shortest route in a network that traverses each edge at least once and returns to its starting point
How to find the route inspection algorithm for an eulerian graph?
If all vertices have an even degree, the length of the shortest route will be equal to the total weight of the network
How to use the route inspection algorithm for a semi eulerian network?
if there are exactly two odd nodes, the length of the shortest rout is equal to the total weight of the network plus the length between the two odd vertices
How to use the route inspection algorithm for a network which more than two odd nodes?
1) identify all vertices with an odd degree
2) consider all complete parings of these vertices
3) select the pairing with the smallest weight
4) add a repeat of the arcs that you have chose which have the smallest weight
How can you shorten the length of a route inspection problem?
Start and end with odd vertices and use the smallest weight arc pairings to be repeated
