哈密顿路径猜想（BHR 猜想 2007）的计算验证，对于每个频率划分至多一个多重集的整数到 p = 31-计算机科学-机器学习-哈密顿路径-完全图-算法.pdf

哈密顿路径猜想（BHR猜想2007）的计算验证，对于每个频率

划分至多一个多重集的整数到

[RanjanNNaik,DepartmentofMathematics,LincolnUniversity,PA,USA]

摘要

本文提出了一种计算方法来验证关于具有指定边长的完整图中哈密顿路径的一个特定猜想，

该猜想通常被称为BurattiHorak-Rosa猜想。基于MariuszMeszka之前的工作，他验证了所

本有不超过23的素数上的猜想，我们的Python程序以不同的方式验证了BHR猜想对于复合数

译和素数直到p=32的情况，具体来说是通过考虑每个频率分区（FP）的一个多重集来实现的。我

中们报告了对整数的所有频率分区的成功计算验证，并特别展示了的结果。对于复

合数，Python代码在联想笔记本电脑上大约花了11个小时进行验证。该方法系统地生

3

v成边长的频率分区，并使用递归回溯算法来构造相应的哈密顿路径。所提出的程序经过了效率

9优化并设计为可扩展性，允许其在更强大的计算资源上运行以探索更大的整数值，从而进一步

5

0证明猜想的有效性。

0彼得·霍拉克和亚历克斯·罗萨的猜想（推广了马尔科·布拉蒂的猜想）指出，一个由(p-1)

0

.个不超过的正整数组成的多重集L是具有顶点集为1,2,...,[p-1]的完全图中某个合适的

7

0哈密顿路径的边长列表，当且仅当对于p的每个除数d，在L中出现的d的倍数的数量最多为

5[p-d]。

2

:对于p=16，生成了170,544个多重集，其中一些可能具有相同的频率划分。随后应用BHR

v

i必要条件导致需要进一步验证的多重集数量减少了数千个。验证过程在联想Thinkpad上执行，

x

r其特点是高内存消耗而非高强度CPU使用，并且通常处理所有有效多重集的时间略多于一天。

a

主题分类：05C07,05C38,05C50,05C62,05C75,68R10,68W30

关键词：哈密顿路径，完全图，边长，频率划分，计算验证，回溯算法，Buratti-Horak-Rosa

猜想，除数，tsp

1介绍

哈密顿路径和圈在图中的研究是组合数学和图论中的一个基本领域。一类特别具有挑战性的问

题涉及构造具有特定属性的哈密顿路径，例如在定义于循环群上的图中具有特定边长或连续顶点之

间的差异。Buratti-Horak-Rosa猜想指出，在其顶点为{0,1,2,...(p-1)}（对于整数）的完全图中

存在的具有特定长度序列的哈密顿路径，是一个引起广泛关注的著名问题[1,3,2]。

1

之前为解决这一猜想所做的努力包括理论构造和计算有哪些信誉好的足球投注网站。MariuszMeszka在[1]中报告称，

通过计算验证了该猜想对于所有小于等于的素数的有效性，取得了重大进展。本文旨在进

一步推进这些计算结果。我们描述了一个设计用于系统地有哪些信誉好的足球投注网站此类哈密顿路径的Python程序，并

展示了新的计算证据，将猜想的验证范围扩展到所有数字，特别确认了其对于的有

效性。我们的程序设计也便于利用现代计算能力对未来更大整数值的研究。

2方法论

我们计算方法的核心是一个Python程序，旨在根据指定的“频率划分”（FP）构造哈密顿路

径。对于给定的整数，完全图的顶点由的元素表示。“边长”（或“跳跃”）定义

为连接顶点之间的绝对差值模。这些长度通常取自集合。

频率划分（FP）表示这些边长的多重集，其和等于。每个FP对应可能形成长度为

的哈密顿路径的一组“跳跃”（连接个顶点）。程序如下进行：

1.频率划分生成：生成_f