= Travelling salesman tour
A <travelling salesman tour> is a cyclic visiting order that visits each required vertex exactly once before returning to its start. In a complete <graph>, it is a <Hamiltonian cycle>. For an ordering $\pi$ of $n$ vertices and costs $c_{ij}$, its length is $\sum_{k=0}^{n-1}c_{\pi(k),\pi((k+1)\bmod n)}$.
In a symmetric problem, rotations and reversal represent the same undirected tour, giving $(n-1)!/2$ tours for $n\geq3$. Thus four labeled locations have three distinct tours under this convention. Asymmetric costs generally distinguish a tour from its reversal. A closed walk allowed to revisit vertices is a different feasible object unless the problem explicitly permits that change.
Back to article page
