Methods to determine the existence of Hamiltonian Cycles in graphs have been extensively studied. However, little research has been done following cases when no Hamiltonian Cycle exists. Let a vertex be "unbounded" if it is visited more than once in a path. Furthermore, let a k-Unbounded Hamiltonian Cycle be a path with finite length that visits every vertex, has adjacent start and end vertices, and contains k unbounded vertices. We consider a novel variant of the Hamiltonian Cycle Problem in which the objective is to find an m-Unbounded Hamiltonian Cycle where m is the minimum value of k such that a k-Unbounded Hamiltonian Cycle exists. We first consider the task on well-known non-Hamiltonian graphs. We then provide an exponential-time brute-force algorithm for the determination of an m-Unbounded Hamiltonian Cycle and discuss approaches to solve the variant through transformations to the Hamiltonian Cycle Problem and the Asymmetric Traveling Salesman Problem. Finally, we present a polynomial-time heuristic for the determination of an m-Unbounded Hamiltonian Cycle that is also shown to be an effective heuristic for the original Hamiltonian Cycle Problem.
翻译:已经广泛研究了在图表中确定汉密尔顿周期存在的方法。然而,在没有汉密尔顿周期存在的情况下,很少研究确定汉密尔顿周期存在的方法。如果在路径中访问次数不止一次,让一个顶点“不受约束”就可以“不受约束 ” 。此外,让K-无约束的汉密尔顿周期成为一条长度有限的路径,可以访问每个顶点,可以相邻开始和结束,并包含无约束的脊椎。我们考虑汉密尔顿周期问题的一个新变式,其目标是找到一个M-无约束的汉密尔顿周期,在这个周期中,M是K-无约束的汉密尔顿周期存在的最低值。我们首先考虑关于众所周知的非汉密尔顿周期的任务。然后我们提供一个指数-时间粗力算法,用于确定一个M-无约束的汉密尔顿周期,并讨论通过汉密尔顿周期的转型和阿斯米利德·萨曼问题解决变式的方法。最后,我们提出一个多角度的时段时间超时段,用于确定一个最初的汉密尔顿周期,这个周期也显示他进入的汉密尔密尔密尔顿周期。