Route inspection

Question 1

What is a Eulerian graph?

Answer 1

A graph in which all vertices have an even degree

Question 2

What is a semi-Eulerian graph?

Answer 2

A graph in which precisely two vertices are of odd degree

Question 3

What does it mean for a graph to be traversable?

Answer 3

It is possible to travel along every edge just once without skipping over any sections

Question 4

When is a graph traversable?

Answer 4

When it is a Eulerian graph

Question 5

When is a graph semi-traversible?

Answer 5

When it is a semi-Eulerian graph

Question 6

When is a graph not traversible?

Answer 6

When it has more than two vertices of odd degree

Question 7

What can be said about the number of vertices of odd degree in any graph?

Answer 7

It is always even

Question 8

What is a Eulerian walk?

Answer 8

A walk which uses each edge exactly once

Question 9

What is a Eulerian cycle?

Answer 9

A cycle which uses each edge exactly once

Question 10

What does the Chinese postman algorithm do?

Answer 10

It finds the shortest route that traverses every edge at least once and returns to the starting vertex, by transforming the graph into an Eulerian graph if necessary

Question 11

Explain the Chinese postman algorithm

Answer 11

If the graph is Eulerian already then no further action is necessary, and the shortest route’s weight is equal to the network’s total weight. Otherwise, for each combination of pairings of the odd vertices, the total weight of the minimum paths between each pairing is calculated. The combination with the lowest total weight has its edges repeated, thus making the graph Eulerian