Chapter 4 Route Inspection

Question 1

What are the 3 types of graphs that all graphs can be organised into?

Answer 1

Eulerian, semi Eulerian or neither

Question 2

What is a Eulerian graph or network?

Answer 2

An Eulerian graph or network is one which contains a trail that includes every edge and starts and finishes at the same vertex

Question 3

What is an Eulerian graph called?

Answer 3

Eulerian circuit

Question 4

What is a quick way to check that a graph is Eulerian?

Answer 4

If all of the vertices have even degrees and the graph is connected then it is an Eulerian graph

Question 5

What is a semi Eulerian graph or network?

Answer 5

A semi Eulerian graph or network is one which contains a trail that includes every edge but starts and finishes at different vertices

Question 6

What is a quick way to check if a graph is semi Eulerian?

What do you know about the graph?

Answer 6

Any connected graph with exactly 2 odd vertices is semi Eulerian

Where the trail will start and end at those 2 odd vertices

Question 7

What do Eulerian and semi Eulerian graphs both include?

Answer 7

Both include a trail that includes every edge

Question 8

What are Eulerian circuits sometimes called?

Answer 8

Eulerian cycles

Question 9

Why may a Eulerian cycle as a name be misleading?

Answer 9

Eulerian cycles may not be a true cycle as some nodes may be visited more than once

Question 10

What is a trail?

Answer 10

A trail is a walk in which no edge is visited more than once

Question 11

What is a cycle?

Answer 11

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)

Question 12

What is a good way to check that a graph is eulerian or semi eulerian?

Answer 12

You can draw a semi Eulerian and an Eulerian graph without taking your pen off the page and without repeating any arcs

Question 13

What is a quick way to tell if a graph is neither Eulerian non semi Eulerian?

Answer 13

If it is not connected or if it doesn’t have exactly 2 odd vertices it is neither

Question 14

What is an easy way to draw a non Eulerian and non semi Eulerian graph/

Answer 14

You can just draw 2 vertices which aren’t connected
(No arcs just 2 nodes)

Question 15

What are the 2 different names for the same route inspection algorithm?

Answer 15

The route inspection algorithm
Chinese postman algorithm

Question 16

What can the Chinese postman algorithm be used for?

Answer 16

To find the shortest route in a network that transverses every arc at least once and returns to its starting point

Question 17

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?

Answer 17

The shortest route will be equal to the total weight of the network

Question 18

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?

Answer 18

You will have to transverse some length more than once

Question 19

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?

Answer 19

Total weight of the network + the length of the shortest path between the 2 odd vertices

Question 20

What is a quick way to show that you know which degrees are odd and even in the exam?

Answer 20

In an exam you can label each point in a graph like this picture to show the value of the degrees of each vertex

Question 21

What is something that some people do to make things simpler when applying the Chinese postman algorithm?

Answer 21

They will draw in an extra arc from the 2 odd vertices to show the shortest route between them

Question 22

Which algorithm can use use if there are more than 2 odd vertices?

Answer 22

Route inspection algorithm / Chinese postman algorithm

Question 23

What is the Chinese postman algorithm?

Answer 23

Question 24

What is the general method for questions involving the route inspection algorithm?

Answer 24

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

Question 25

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?

Answer 25

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