ROUTE INSPECTION Flashcards
What is an Eulerian/Semi Eulerian graph
An Eulerian graph is a CONNECTED graph with every vertex of even degree. An Eulerian cycle is a
cycle that includes every edge of a graph exactly once.
A semi-Eulerian graph is a CONNECTED graph with exactly two vertices of odd degree.
. .
remember that 0
is even. The circuit is the “empty circuit”
Since the graph has no edges, we’ve already passed every edge if we don’t even move :D
Which of the complete graphs are Eulerian/Semi Eulerian?
Odd ones [ K2n+1] where degree of each vertex is 2n
Including K1 - 1 vertex w degree 0
What does the route inspection algorithm accomplish?
Finds the length of the shortest route that traverses each arc at least once, and returns to its starting point.
[Doesn’t give the route, only its length]
What is the length of the shortest route of a Eulerian graph?
Length equals its weight
Uses of route inspection algorithm
“Chinese postman”
Planning postal routes
Snow plough routes
Inspections of pipes/roads
What is the length of the shortest route on a semi Eulerian graph?
Total weight of the network + weight of shortest path between the two odd vertices
Route between the two odd vertices = weight [start and finish at odd]
(Adding shortest path essentially turns odd vertices into even ones)
What is the length of the shortest route in a network with 4 odd vertices?
Total weight + weight of shortest pairs of distances (between odd vertices)
Difference between nearest neighbour for digraphs vs normal
Read across rows
Why is a Eulerian cycle not necessarily a true cycle
In general, some vertices may be visited more than once
Explanation for why Eulerian graphs are the way they are
If u don’t want to get “stuck” at a vertex, you need to leave it the same number of times you arrive at it, so the degree of every vertex must be even
https://www.youtube.com/watch?v=CQNH2ifOAQE
A connected graph has 4 nodes and 8 edges.
The nodes have degree 2n−2, n−1, n−1, n
State if the graph is Eulerian, Semi-Eulerian or neither. You must fully explain your answer.
Each edge adds 2 to the total valency, so the 8 edges give a total valency of 16.
2𝑛−2+𝑛−1+𝑛−1+𝑛=16 𝑛 =4
So the nodes have degree 6, 3, 3, 4.
An alternative approach here uses the Handshake Lemma . We note that if n was odd there would be one odd vertex, which isn’t possible by the Handshake Lemma, therefore n is even, there are 2 odd vertices and the graph is semi-Eulerian
Lets say they allow u to start and end on a diff vertex, how do u choose which one to repeat
Identify possible pairings - least distance will be repeated, then start and end on other two
More than 4 odd nodes
Use info given in question - start and end nodes “evenified” as u can’t get stuck there
