Chapter 4 Route Inspection Flashcards
What are the 3 types of graphs that all graphs can be organised into?
Eulerian, semi Eulerian or neither
What is a Eulerian graph or network?
An Eulerian graph or network is one which contains a trail that includes every edge and starts and finishes at the same vertex
What is an Eulerian graph called?
Eulerian circuit
What is a quick way to check that a graph is Eulerian?
If all of the vertices have even degrees and the graph is connected then it is an Eulerian graph
What is a semi Eulerian graph or network?
A semi Eulerian graph or network is one which contains a trail that includes every edge but starts and finishes at different vertices
What is a quick way to check if a graph is semi Eulerian?
What do you know about the graph?
Any connected graph with exactly 2 odd vertices is semi Eulerian
Where the trail will start and end at those 2 odd vertices
What do Eulerian and semi Eulerian graphs both include?
Both include a trail that includes every edge
What are Eulerian circuits sometimes called?
Eulerian cycles
Why may a Eulerian cycle as a name be misleading?
Eulerian cycles may not be a true cycle as some nodes may be visited more than once
What is a trail?
A trail is a walk in which no edge is visited more than once
What is a cycle?
A cycle is a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once
(A path that starts and ends in the same place)
What is a good way to check that a graph is eulerian or semi eulerian?
You can draw a semi Eulerian and an Eulerian graph without taking your pen off the page and without repeating any arcs
What is a quick way to tell if a graph is neither Eulerian non semi Eulerian?
If it is not connected or if it doesn’t have exactly 2 odd vertices it is neither
What is an easy way to draw a non Eulerian and non semi Eulerian graph/
You can just draw 2 vertices which aren’t connected
(No arcs just 2 nodes)
What are the 2 different names for the same route inspection algorithm?
The route inspection algorithm
Chinese postman algorithm
What can the Chinese postman algorithm be used for?
To find the shortest route in a network that transverses every arc at least once and returns to its starting point
If all the vertices are even (is an Eulerian graph) and you want to start and end in the same place what will be the length of the shortest route?
The shortest route will be equal to the total weight of the network
If you want to start and end in the same place what do you know you will have to do if you want to transverse all of the edges if you have a semi Eulerian graph?
You will have to transverse some length more than once
If a network has exactly 2 odd vertices (semi Eulerian network) what will the length of the shortest path starting and ending at the same place and transversing all the edges?
Total weight of the network + the length of the shortest path between the 2 odd vertices
What is a quick way to show that you know which degrees are odd and even in the exam?
In an exam you can label each point in a graph like this picture to show the value of the degrees of each vertex
What is something that some people do to make things simpler when applying the Chinese postman algorithm?
They will draw in an extra arc from the 2 odd vertices to show the shortest route between them
Which algorithm can use use if there are more than 2 odd vertices?
Route inspection algorithm / Chinese postman algorithm
What is the Chinese postman algorithm?
What is the general method for questions involving the route inspection algorithm?
When doing this sort of question the first step is to label and state all the odd vertices
Then state all the possible pairings with a sum representing their shortest route
Then pick the smallest number and then add the weight of the entire network onto that number for the answer
If asked to do a question in where you need to find an optimum route in a network with more than 2 odd vertices which can finish in 2 different places what do you need to think about?
This is a semi Eulerian problem
To minimise travel time the route will start and end at odd vertices
You need to find which 2 odd vertices are closest and you will transverse the arcs between them again to minimise wasted travel time
