On the Skeleton of the Polytope of Pyramidal Tours

摘要

Abstract We consider the skeleton of the polytope of pyramidal tours. A Hamiltonian tour is called pyramidal if the salesperson starts in city 1, then visits some cities in increasing order of their numbers, reaches city n , and returns to city 1 visiting the remaining cities in decreasing order. The polytope PYR( n ) is defined as the convex hull of the characteristic vectors of all pyramidal tours in the complete graph K ~( n ). The skeleton of PYR( n ) is the graph whose vertex set is the vertex set of PYR( n ) and the edge set is the set of geometric edges or one-dimensional faces of PYR( n ). We describe the necessary and sufficient condition for the adjacency of vertices of the polytope PYR( n ). On this basis we developed an algorithm to check the vertex adjacency with linear complexity. We establish that the diameter of the skeleton of PYR( n ) equals 2, and the asymptotically exact estimate of the clique number of the skeleton of PYR( n ) is Θ( n _(2)). It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons.