Route Inspection

Question 1

Transversable graphs

Answer 1

One that can be drawn without taking the pen off the paper

Question 2

Eulerian trail =

Answer 2

Uses all edges and all vertices must be of even order

Question 3

Semi - eulerian

Answer 3

Two odd vertices

Question 4

How many ways of pairing 2 odd vertices and 4 odd vertices

Answer 4

1 way
3 ways

Question 5

How to work out how many ways of pairing odd vertices

Answer 5

(N-1)x (n-3) x (n-5)….. x1

Question 6

Route inspection Problem

Answer 6

List all odd vertices
List all possible pairings of odd vertices
For each pairing find the edges that connect the vertices with the minimum weight
Find the pairings such that the sum of the weights is minimised
On the original graph add on the new edges
Add the sum of the edges to the total found