论文标题
在带有阶梯式锥体之旅的多层室外的1个骨骼上
On 1-skeleton of the polytope of pyramidal tours with step-backs
论文作者
论文摘要
带有继承的金字塔游览是一种特殊形式的汉密尔顿之旅：销售人员从城市1开始，然后以升级秩序访问一些城市，到达城市$ n $，然后返回城市1，以下降的命令访问其余城市。但是，在上升和下降方向上，可以倒入相邻城市的顺序（阶梯式）。众所周知，在带有步长的金字塔之旅中，可以通过多项式时间的动态编程来解决旅行销售人员问题。 我们将带有阶级的金字塔之旅的多元化定义为$ \ permatatorname {psb}（n）$，为所有可能的金字塔旅行的特征矢量的凸壳，并在完整的有向图中带有逐步退回。 $ \ operatorname {psb}（n）$的1个骨骼是其顶点集的图形，其顶点是多层的顶点集，而边缘集是一组几何边缘或多型的一维面。我们提出了一种线性时间算法，以验证polytope $ \ operatorname {psb}（n）$的1个骨骼中的顶点邻接，并估算直径和1孔的直径数：直径的数量：上面的直径为4限制了4和集团的数字，该集团的数字在parameter上二次增长。
Pyramidal tours with step-backs are Hamiltonian tours of a special kind: the salesperson starts in city 1, then visits some cities in ascending order, reaches city $n$, and returns to city 1 visiting the remaining cities in descending order. However, in the ascending and descending direction, the order of neighboring cities can be inverted (a step-back). It is known that on pyramidal tours with step-backs the traveling salesperson problem can be solved by dynamic programming in polynomial time. We define the polytope of pyramidal tours with step-backs $\operatorname{PSB}(n)$ as the convex hull of the characteristic vectors of all possible pyramidal tours with step-backs in a complete directed graph. The 1-skeleton of $\operatorname{PSB}(n)$ is the graph whose vertex set is the vertex set of the polytope, and the edge set is the set of geometric edges or one-dimensional faces of the polytope. We present a linear-time algorithm to verify vertex adjacencies in 1-skeleton of the polytope $\operatorname{PSB}(n)$ and estimate the diameter and the clique number of 1-skeleton: the diameter is bounded above by 4 and the clique number grows quadratically in the parameter $n$.
