Change ringing and Hamiltonian cycles: The search for Erin and Stedman triples
Change ringing and Hamiltonian cycles: The search for Erin and Stedman triples
复制标题
改变振铃和哈密顿循环：寻找艾琳和斯特德曼三元组
DOI：
10.5614/ejgta.2019.7.1.5
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Andrew Johnson
中科院分区：
文献类型：
--
作者：
M. Haythorpe;Andrew Johnson
钟声学中一个非常古老的问题是寻找珍珠。后者可以被认为是给定大小的所有可能排列的严格约束序列，其中约束的确切性质取决于所需的振铃方法。特别是，我们考虑仅 bobs Stedman Triples 和 Erin Triples 的方法；后者的存在仍然是一个悬而未决的问题。我们证明这个问题可以被视为哈密顿循环问题（HCP）的类似约束形式。通过使用特殊的子图，我们将其转换为 HCP 的标准实例。原始问题可以划分为更小的实例，因此我们也使用这种技术来生成更小的 HCP 实例。我们注意到，已知有解决方案的实例提供了异常困难的 HCP 实例。
A very old problem in campanology is the search for peals. The latter can be thought of as a heavily constrained sequence of all possible permutations of a given size, where the exact nature of the constraints depends on which method of ringing is desired. In particular, we consider the methods of bobs-only Stedman Triples and Erin Triples; the existence of the latter is still an open problem. We show that this problem can be viewed as a similarly constrained form of the Hamiltonian cycle problem (HCP). Through the use of special subgraphs, we convert this to a standard instance of HCP. The original problem can be partitioned into smaller instances, and so we use this technique to produce smaller instances of HCP as well. We note that the instances known to have solutions provide exceptionally difficult instances of HCP.