= Weighted Hamilton cycle
{title2=$L(C)=\sum_{e\in E(C)}w_e$}
A <weighted Hamilton cycle> is a <Hamilton cycle> in a <weighted graph>, with cost equal to the sum of its traversed <edge> weights. Here weights represent symmetric nonnegative costs, rather than conductances. Asking whether a <Hamilton cycle> exists is a feasibility question; asking for the cheapest one is an instance of the <travelling salesman problem>. A <complete graph> supplies every possible connection between distinct <vertices>, making feasibility automatic for $n\geq3$, while choosing the cheapest visiting order remains a separate <mathematical optimization> problem.
\Image[/weighted-hamilton-cycle-four-vertex-tours.png]
{title=A fictitious <weighted graph> on four <vertices>: its three <Hamilton cycles>, identified under reversal and cyclic rotation, have costs 14, 19 and 21}
{id=weighted-hamilton-cycle-four-vertex-tours}
Assign the <complete graph> $K_4$ the symmetric <edge> costs $w_{AB}=2$, $w_{BC}=3$, $w_{CD}=4$, $w_{AD}=5$, $w_{AC}=6$ and $w_{BD}=7$, in arbitrary units. Fix the start at $A$ and identify each <Hamilton cycle> with its reverse. The three possibilities are
$$
\begin{aligned}
A,B,C,D,A &: 2+3+4+5=14,\\
A,B,D,C,A &: 2+7+4+6=19,\\
A,C,B,D,A &: 6+3+7+5=21.
\end{aligned}
$$
These exhaust the possibilities: the <permutations> of the other three <vertices> give $3!=6$ orders, paired into three reversals. Hence the perimeter tour really is optimal for this toy instance. The diagram's geometric lengths are not costs, and no <triangle inequality> is assumed.
The usefulness of this model is to distinguish visiting required sites from covering required connections. If tasks are assigned to <vertices> and the route must return after one visit to each, a <weighted Hamilton cycle> captures the ordering requirement. If the job instead requires each <edge> once, the relevant object is an <Euler circuit>. The <shortest path problem> asks only for a cheapest route between specified endpoints. A 1954 primary research paper gave a concrete motivation for the <travelling salesman problem>: certify that a particular tour through 49 cities has minimum road-distance cost.<Solution of a Large-Scale Traveling-Salesman Problem by George B. Dantzig and others>[Solution of a Large-Scale Traveling-Salesman Problem by G. Dantzig, R. Fulkerson and S. Johnson, abstract; Journal of the Operations Research Society of America 2(4), pp. 393–410 (1954)]{ref}
These are abstract route models. If a cost stands for a whole <graph path> through an underlying network, travelling between consecutive task <vertices> can pass through intermediate network <vertices> more than once. One visit per task therefore does not imply one visit per physical junction. One-way connections require a <directed graph>; changing costs or extra timing constraints require a richer model than the fixed symmetric toy instance.
Back to article page
