D1, C4 - Route Inspection Flashcards
When is a connected graph Eulerian
All nodes / vertices have EVEN order / degree / valency
What type of graphs could be Eulerian
Connected graphs
When is a connected graph semi-Eulerian
Exactly two nodes / vertices have ODD order / degree / valency
What is different for trails on Eulerian and semi-Eulerian graphs
Eulerian- it is possible to have a trail that includes every edge and starts and finishes at the same vertex (Eulerian circuit)
Semi-Eulerian- a trail will include every edge, but will start and finish at different vertices
What is the method for finding a trail on a semi-Eulerian graph (start and finish point)
Start and finish at the odd nodes
Do all connected graphs have to be Eulerian or semi-Eulerian
YES?? - unsure
What is Euler’s Handshaking Lemma
sum of valencies = 2 * number of edges
Describe a graph that is neither Eulerian nor Semi-Eulerian
A graph with more than 2 odd valencies
What does the route inspection algorithm tell us
The shortest route that traverses every arc at least once and returns to its starting vertex
What is the shortest path (using the route inspection algorithm) for a Eulerian graph
Shortest path length = total weight of the network
What is the shortest path (using the route inspection algorithm) for a Semi-Eulerian graph
Shortest path length = total weight of the network + length of shortest path between odd vertices
How do you find the shortest path (using the route inspection algorithm) for a graph which is neither Eulerian nor Semi-Eulerian
1) Identify all odd vertices
2) List all pairings of these vertices
3) Select pairing with the lowest weight between vertices
4) Add repeat arcs between these pairing
A network with 4 odd valencies originally has the route inspection algorithm applied. To save money it is decided that the route no longer must start and end at the same place. How do you decide which 2 vertices to now start and end at
Problem become Semi-Eulerian
Pick the 2 odd vertices that have the smallest weight between them and add that weight as another arc
What happens to questions for route inspection where there are over 4 odd nodes and why
There will be some information that restricts the number of pairings e.g. start and finish at different places
Because 6 odd nodes –> 15 pairings
8 odd nodes –> 105 pairings
When doing route inspection on a graph with more than 4 odd nodes, what does it mean if you can start and finish at different places
The start and finish can be kept as odd and can be rejected from the pairings
