**REF.**- Eugene L Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B.Shmoys, editors.
*The Traveling Salesman Problem*. John Wiley & Sons, 1985.

- Tour (Hamilton) (Hamiltonian cycle)
Given a graph with weights on the edges a

**tour**is a simple cycle that includes all the vertices of the graph. For examples of tours, see Figure 6.30. - TSP
Given a graph with weights on the edges, find a tour having a minimum sum of edge weights.

- NP-hard problem

eEL,CSA_Dept,IISc,Bangalore