Travelling salesman

Question 1

What is a tour

Answer 1

A walk which visits every vertex, returning to its starting vertex. A tour which visits every vertex exactly once is a hamiltonian cycle

Question 2

Diff between a tour and cycle

Answer 2

A tour can visit vertices multiple times, a cycle can only visit each one once (apart from starting/ending)

Question 3

Travelling salesman practical vs classical

Answer 3

Classical - Visit each vertex exactly once
Practical - Visit each vertex at least once

before returning to starting vertex

Question 4

When classical and practical are equivalent

Answer 4

If network is complete and edge distances are the least distance from A-B (satisfies triangle inequality)

Question 5

Methods of finding upper/lower bounds

Answer 5

Upper - mst - prims/kruksal/nearestneighbour
Lower - residual mst

Question 6

Why nn might be favourable over prims

Answer 6

Finding mst + shortcuts for large networks inefficient, nearest neighbour provides a hamiltonian cycle.

Nearest neighbour finds a Hamiltonian Cycle, Primm finds a minimum spanning tree.
Nearest neighbour finds the closest vertex to the vertex last chosen, Primm finds the closest vertex to any of the vertices already selected

(Nearest neighbour u do with every vertex then see lowest UB)

Question 7

Explain why there must be a solution to classical travelling salesman for any complete network

Answer 7

In a complete graph any two vertices are connected. Hence, after fixing the start vertex,
you can visit all other vertices in arbitrary order. The tour of that type which has
minimum total weight provides the solution to the classic problem.
For example consider 4
K with vertices A,B,C,D and take A as a start vertex. Since there
is an edge between any two nodes, ABCDA, ABDCA, ACBDA, ACDBA, ADBCA and
ADCBA are all possible tours. The one of minimum weight provides a solution to
classical problems. Similarly, for any other vertex.

Question 8

Note when using RMST to calculate highest upper bound

Answer 8

Delete arc find Mst then add on lowest weight. Only provides solution to classical problem, if u want practical then u need to apply rmst to table of shortest distances

Question 8

Nearest neighbour

Answer 8

Diff to Prim’s in that next arc MUST come from previously chosen vertex, can lead to drawbacks as can end up “forcing” long arcs