Skip to main content
noting possible extensions
Source Link
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

Consider the nine-vertex weighted graph in the figure (left). All edges have the same weight in either direction. Edges not shown are given a high weight, say, $10^6$.

9-vertex weighted graph

The minimum-weight Hamiltonian path has weight zero (shown in the middle). Connecting its ends, you obtain a Hamiltonian circuit of weight $99$. Any swap of two edges $(a,b),(c,d)$ into $(a,d),(c,b)$ would only increase the weight.

However, the minimum-weight Hamiltonian circuit has weight $3$ (on the right).

Note that here an exhaustive search over triples of edges would find the optimum in one move. However, a similar construction with four chords would require finding an exchange of four edges (and the same idea can be extended arbitrarily).

Consider the nine-vertex weighted graph in the figure (left). All edges have the same weight in either direction. Edges not shown are given a high weight, say, $10^6$.

9-vertex weighted graph

The minimum-weight Hamiltonian path has weight zero (shown in the middle). Connecting its ends, you obtain a Hamiltonian circuit of weight $99$. Any swap of two edges $(a,b),(c,d)$ into $(a,d),(c,b)$ would only increase the weight.

However, the minimum-weight Hamiltonian circuit has weight $3$ (on the right).

Consider the nine-vertex weighted graph in the figure (left). All edges have the same weight in either direction. Edges not shown are given a high weight, say, $10^6$.

9-vertex weighted graph

The minimum-weight Hamiltonian path has weight zero (shown in the middle). Connecting its ends, you obtain a Hamiltonian circuit of weight $99$. Any swap of two edges $(a,b),(c,d)$ into $(a,d),(c,b)$ would only increase the weight.

However, the minimum-weight Hamiltonian circuit has weight $3$ (on the right).

Note that here an exhaustive search over triples of edges would find the optimum in one move. However, a similar construction with four chords would require finding an exchange of four edges (and the same idea can be extended arbitrarily).

Source Link
Jukka Kohonen
  • 4.2k
  • 2
  • 21
  • 49

Consider the nine-vertex weighted graph in the figure (left). All edges have the same weight in either direction. Edges not shown are given a high weight, say, $10^6$.

9-vertex weighted graph

The minimum-weight Hamiltonian path has weight zero (shown in the middle). Connecting its ends, you obtain a Hamiltonian circuit of weight $99$. Any swap of two edges $(a,b),(c,d)$ into $(a,d),(c,b)$ would only increase the weight.

However, the minimum-weight Hamiltonian circuit has weight $3$ (on the right).