Hamiltonian graphs and TSP

Question 1

What is a hamiltonian cycle, path, graph?

Answer 1

Cycle: Visits every vertex once starting and ending at same
Path: Path that visits vertex once and doesnt end at start
Graph: Graph posessing hamiltonian cycle

Question 2

Under which conditions is a graph necessarily hamiltonian?

Answer 2

• Degree of AT LEAST 2

Question 3

What are the steps for the closest insertion heuristic?

Answer 3

1. Start at depot, add smallest cylce from nearest node
2. Look for node with shortest distance from cycle. Find ij in current cycle such that d(i, k) + d(k, j) - d(i,j) is minimum.

Question 4

What are the steps for the cheapest insertion heuristic?

Answer 4

1. Start with smallest cycle
2. Consider each node k not yet part of cycle. Find distance that is at minimum.
3. Calculate all options from those vertices at different positions in the cycle.

Question 5

What are the steps for the nearest-neighbour heuristic and how is it done from a weighted matrix?

Answer 5

1. Start at depot
2. From last node in route, find shortest and add to route.

Matrix: Search in corresponding row/col for smallest unvisited distance.

Question 6

What is the 1-tree lower bound and how is it calculated?

Answer 6

Estimnate how close given solution is to optimal. If far, use different heuristic or improve on current solution.

Calculate:
1. Choose node, remove it and all arcs.
2. Determine MST
3. Put node back in MST with two shortest arcs. Length = |MST| + 2
4. Repeat for all nodes until best lower bound obtained. Higher bound = better for TSP.

Question 7

Why is NN a bad heuristic?

Answer 7

1. Greediness in immediate gains approach
2. Increased num neighbours -> extra distance.