1
$\begingroup$

A bit of background to help explain the question:

In a class we were given a large spreadsheet of stars and were asked to find two paths, starting from the Sun and visiting every star within 10 parsecs of the Sun. We were asked to do this in two ways. The first was to find the "shortest" path, that is for the last star in the path, find the closest star to it, then find the closest to that star, and so forth. Then we were asked to find an optimal path, that is a path to find the shortest possible path (based on distance) to visit all the stars.

Shifting the idea into graph theory mode, I thought it as trying to find two Hamiltonian paths in a complete, simple, undirected graph. The more I thought about it and tried it out on some small complete graphs, I couldn't find a case where the shortest path wasn't the optimal path.

So now, my question: In complete, weighted, simple graphs, is the "shortest" Hamiltonian path the optimal Hamiltonian path?

PS. While the question comes from a class, its not part of the assignment. This is for my own curiosity.

$\endgroup$
2
$\begingroup$

Suppose you have 7 stars. A, B, and C form a nearly equilateral triangle; AB and BC have length 1, AC is a little longer, $1+\epsilon$. B, D, E, F, and G lie on a straight line, going away from AC; each is $1/2$ a unit away from the next.

Starting at A, the closest is B, then D, E, F, G, and then you have to go back to C. That's total length $3+GC$, which is a little under 6.

But if instead you go ACBDEFG, that's total length $4+\epsilon$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.