Suppose that we want to solve the Travell ing Salesman Problem

$($TSP$)$ which is represented as a weighted graph G$.$ Given a vertex

$v,$ we can find the $1-$tree lower bound for the TSP by computing

A minimum spanning tree $T$ on the sraph $Gv,$ then addins the

Two shortest edges from v to T$.$ Explain why the $1-$tree lower

Bound is indeed a lower bound on the solution to the TSP$.$

The distances between $6$ cities $A,B,C,D,E$ and $F$ are as follows:

$($a$)$ Calculate the $1-$tree lower bound for the TSP on the corresponding

Graph. Take Aas point $1.$

$($b$)$ The method of $2-$changes is a way of exploring a neistbourhood

of an existirs solution to try to come up with a better

One. In the TSP$,$ a $2-$change neighbourhood of a tour g is

Def ined as

$N2(g)=\{$f: fis also a tour and can be obtained from $g$

By removing two edses from gand replacing them

with two other edges.