Route Inspection

Question 1

Eulerian Graph

Answer 1

A connected graph where all the orders are even

Traversable

Question 2

Semi-Eulerian graph

Answer 2

A connected graph where exactly 2 orders are odd

Semi-traversable

Question 3

Traversable

Answer 3

A graph in which it is possible to travel along every arc just once, returning to the start node and without taking your pen off the paper

Question 4

When is a graph not traversable?

Answer 4

If it has more than 2 nodes with odd degree

Question 5

Route inspection problem

Answer 5

Can be used to find the shortest route in a network that traverses each arc at least once and returns to its starting point

Question 6

Route inspection problem Eulerian

Answer 6

The weight of the network

Sum each arc’s weight, noting each down

Question 7

Route inspection problem semi-Eulerian

Answer 7

The weight of the network plus the length of the shortest route between the two odd nodes

Question 8

Route inspection algorithm

Answer 8

1. Write down any vertices with odd degree
2. Write down all possible combinations of vertex pairs
3. Write down the shortest route between each pair and sum to find for the combination
4. Write down the arcs in the combination with the smallest sum and add to the network

Question 9

What to remember if an arc is removed

Answer 9

To take that away from the total length as well as adding the arcs traversed twice

Question 10

What happens if you are given 2 possible end nodes?

Answer 10

Write out all the possible combinations of pairings from each