I am solving an exercise from Mathematics High Level for the IB Diploma (the Discrete Math book). One of the exercises in graph theory is the following:
- We want to solve the traveling salesman problem for the graph $K$ shown here.
(a) Use the nearest neighbour algorithm starting at vertex $B$ to find an upper bound for the traveling salesman problem.
(b) By removing vertex $B$ find a lower bound.
(c) Write down an inequality satisfied by $L$, the length of the shortest Hamiltonian cycle in $K$.
The mark scheme follows:
- (a) $114$
(b) $89$
(c) $89 \leq L\leq 114$
What I got as an answer was very different from the book's answers. For question a, I got $16 + 19 + 17 + 19 + 18 + 22 = 111$. In exercise b, shouldn't the authors specify after deleting such vertex what other vertex to start? And assuming that I would start with vertex A, I would get as a lower bound $73 + 16 + 17 = 106$ (corresponding to the minimum spanning tree plus the two smallest weights connecting B to the tree).
Can someone verify my answers or tell me whether I'm thinking this wrong? Any help is highly appreciated.
Your answer is definitely correct for part (a), with the tour that travels $$B \to A \to F \to C \to D \to E \to B.$$
I can't be fully certain the textbook doesn't have something else in mind for part (b), just because "by removing vertex $B$ find a lower bound" is so vague, but your answer is a correct answer, ad it's definitely better than the textbook's. The scheme you're proposing is to remove vertex $B$, find a minimum-cost spanning tree of the remaining graph, and add on the two lowest-cost edges from $B$. I agree that:
This is a valid way to find a lower bound for the traveling salesman problem. (For any closed tour through all six cities, if we delete the two edges in and out of $B$, the remainder is a path through the other five cities, which is a kind of spanning tree - so its cost is at least that of the minimum-cost spanning tree. Meanwhile, the two edges we deleted cost at least as much as the two cheapest edges from $B$.)
The minimum cost of a spanning tree is $17 + 18 + 19 + 19 = 73$ (there are two possible spanning trees with this cost, depending on if we use edge $CD$ or $EF$) so this gives us a lower bound of $106$.
The value $89$ given by the textbook is what we'd get if we added the single edge of cost $16$ to the spanning tree, which would be a lower bound on the cost of an open tour beginning at $B$. Technically that's also a lower bound on the cost of a closed tour, but that's silly: you're leaving money on the ground by ignoring the cost of the second edge out of $B$.
(And if we wanted a general lower bound on open tours, $89$ wouldn't do: there is a spanning tree of cost $87$ in the whole graph, and in fact there is an open tour $A\to B \to C \to F \to E \to D$ of cost $87$.)
So, short answer: you're definitely doing reasonable things, and the textbook answer is definitely doing something weird (though we can't be sure what).