1. Show that, in the ATSP formulation, the connectivity constraints (6.61) and the subtour elimination constraints (6.62) are equivalent.
2. Show that the number of vertices of odd degree in a graph is even.
3. Let G = (V , A) be a complete directed graph such that |V | = 10 and the costs associated to the arcs belong to A, as reported in Table 6.51:
• check if the triangle inequality property holds for each arc cost;
• formulate the corresponding ATSP;
• solve the relaxed AP;
• determine a feasible ATSP solution and evaluate its quality;
• apply a 2-exchange procedure for finding a better feasible solution
