四正则连环图的哈密顿性质与多项式算法判定

本文主要探讨了四正则连环图的哈密顿图性质及其判定的多项式算法。四正则连环图是一种特殊的图论结构，其中所有顶点的度数均为固定值，通常为4。在文章的开始部分，作者宁安琪和宁宣熙定义了一般四正则连环图的概念，这包括了所有可能的顶点连接规则，使得每个顶点的度数恒定。 研究发现，尽管四正则连环图的特殊结构可能会引人猜测它们可能总是存在哈密顿圈（一个经过所有顶点恰好一次的闭合路径），但实际上并非如此，即并非所有的四正则连环图都具有哈密顿圈。这是一个重要的理论贡献，因为它挑战了直观的假设，并强调了在图论中深入分析的重要性。 接着，作者专注于存在哈密顿圈的四正则连环图，设计了一种多项式时间复杂度的算法来构造这些哈密顿圈。这意味着这个算法的时间效率随着问题规模的增长而线性增加，这对于解决大规模图论问题具有实际意义，因为它能够在合理的时间内找到解决方案，避免了指数级的搜索空间。 在文章的后期，作者特别关注了三角形四正则连环图，这是一种特定类型的四正则连环图，其顶点数和边数都有特定范围（n=6-3996, m=12-7992）。他们创建了一个生成器，并利用自组织算法（S-O算法）对该类图的36个实例进行了实验研究，验证了S-O算法在构造哈密顿路径上的有效性。这不仅展示了算法的实际应用，还提供了算法性能的实证证据。 总结来说，这篇论文深入研究了四正则连环图的哈密顿性质，提出并验证了一种多项式算法，对于理解和构建这类图的哈密顿结构有着重要意义。它不仅扩展了图论的知识边界，也为实际问题中的图搜索优化提供了新的方法。同时，通过实证研究，证明了算法在实际应用中的高效性和可靠性。