Weighted Hamiltonian Cycles And Tour Costs

From Hamiltonian Cycles to Tour Costs

A Hamiltonian cycle answers a yes-or-no question: can we visit every vertex exactly once and return to the start? The traveling-salesman problem adds a cost to each edge and asks which such cycle has least total cost. On a small graph, we can answer by listing the distinct cycles and adding their edge weights. The exhaustive search is simple, but it depends on being precise about what counts as a tour and how rotations and reversals are treated.

Throughout, graphs are finite and simple. The traveling-salesman instances considered here have at least three vertices. Edge costs are real numbers, and costs are symmetric: traveling along an edge has the same cost in either direction. We do not assume the triangle inequality.

A Hamiltonian cycle is a cycle that visits every vertex exactly once before returning to its starting vertex. A Hamiltonian tour in a weighted graph is that cycle together with its total cost. If the vertices in cyclic order are \(v_1,\ldots,v_n\), its cost is

Changing the starting point only rotates this list; traversing the same undirected cycle in reverse gives the reverse list. Neither change creates a different tour. An optimal tour is a Hamiltonian tour of minimum cost among all tours in the instance. Completeness guarantees that tours exist when \(n\ge3\): any ordering of the vertices, followed by a return to the first, is a Hamiltonian cycle.

Why Fixing a Starting Vertex Works

Proof. Fix one vertex \(r\) as the first vertex in a written description of a cycle. Arrange the other \(n-1\) vertices in any order, then return from the last vertex to \(r\). This gives \((n-1)!\) written descriptions. Every Hamiltonian cycle has exactly two such descriptions: one for each direction around the cycle, both starting at \(r\). The descriptions are distinct because \(n\ge3\), so the two neighbors of \(r\) occur in opposite orders. There are no other descriptions of that cycle starting at \(r\), since its cyclic order is fixed once a direction is chosen. Thus each distinct undirected cycle has been counted twice, and the number of cycles is \((n-1)!/2\). \(\square\)

Proof. Choose a vertex \(r\). Each permutation of the other vertices gives a Hamiltonian cycle by starting at \(r\), following the permutation, and returning to \(r\). Conversely, every Hamiltonian cycle has a description starting at \(r\), so at least one of its two directions appears in this list. Therefore every possible tour cost is represented. The list is finite and nonempty, so its costs have a minimum. Since the list contains every tour, its minimum is the minimum over all tours and is optimal. Symmetry ensures that the reverse description has the same cost, so retaining both directions does not change the minimum. \(\square\)

For hand calculations, we can avoid listing both directions: after fixing \(r\), keep just one ordering from each reverse pair. The proposition shows that this leaves \((n-1)!/2\) tours. For larger instances, the number grows rapidly; exhaustive enumeration is therefore a useful exact method for small examples, not a promise that brute force is efficient at every size.

Worked Examples

Common Pitfalls and Interpretation

Adding only the edges used to arrive at the last vertex is not enough. A tour must return to its starting vertex. In the first example, the mistaken calculation \(4+5+3=12\) follows \(A-B-C-D\) but omits the return edge \(DA\), whose cost is \(7\). The corrected tour cost is \(4+5+3+7=19\). Omitting the return edge calculates the cost of a path, not a tour.

Do not treat rotations or reversals as new undirected tours. For example, \(A-B-C-D-A\), \(B-C-D-A-B\), and \(A-D-C-B-A\) describe the same cycle. Fixing a starting vertex removes the rotations; retaining one ordering from each reverse pair removes the duplicate direction. These conventions prevent overcounting while preserving every possible tour.

A cheapest-looking collection of edges may not form a tour. A tour has to visit every vertex once and return to its start. Its cost is the sum around a single Hamiltonian cycle, not the sum of an arbitrary selection of low-cost edges. Exhaustive enumeration checks the full cycle condition at the same time as it compares costs.

The examples show why the weighted problem has two ingredients: the graph specifies which edges can be used, and the cost function determines how tours compare. In a complete instance every edge is available, but the tour condition still restricts the choices. For a small instance, listing all distinct cycles gives a transparent certificate of optimality: a tour of the stated cost, together with the costs of every other candidate.