3: Algorithms on Graphs II

Question 1

Route Inspection Algorithm (4)

Answer 1

1. Identify any nodes with odd degree
2. Consider all possible complete pairings of these nodes
3. Select the complete pairing that has the least sum (of shortest paths between each pair)
4. Add a repeat of the arcs indicated by this pairing to the network

Question 2

Walk in a Network

Answer 2

A finite sequence of edges such that the end vertex of one edge is the start vertex of the next

Question 3

Tour

Answer 3

A walk, which visits every vertex, returning to its start vertex

Question 4

In the Classical Travelling Salesman Problem, ____

Answer 4

Each vertex must be visited exactly once before returning to the start

Question 5

In the Practical Travelling Salesman Problem, ____

Answer 5

Each vertex must be visited at least once before returning to the start

Question 6

Triangle Inequality

Answer 6

The longest side of any triangle ≤ the sum of the two shorter sides

Question 7

Minimum Spanning Tree Method for an Upper Bound (3)

Answer 7

1. Find the minimum spanning tree for the network
2. Double this minimum connector
3. Seek ‘shortcuts’, making use of some of the non-included arcs that enable you to bypass a repeat of some of the minimum spanning tree

Question 8

Initial Upper Bound

Answer 8

Found by finding the weight of the minimum spanning tree for the network and doubling it

Question 9

You can use the minimum spanning tree method to find an upper bound for ____

Answer 9

The practical travelling salesman problem

Question 10

You can use the minimum spanning tree method to find a lower bound for ____

Answer 10

The classical travelling salesman problem

Question 11

Minimum Spanning Tree Method for a Lower Bound (5)

Answer 11

1. Remove each vertex in turn, together with its arcs
2. Find the residual minimum spanning tree (RMST) and its length
3. Add to the RMST the ‘cost’ of reconnecting the deleted vertex by the two shortest, distinct arcs and note the totals
4. The greatest of these totals is used for the lower bound
5. You have found an optimal solution if the lower bound gives a Hamiltonian cycle or if it has the same value as the upper bound