图论方法解骑士巡回问题：哈密尔顿圈与对称性的应用

Knight's Tour Problem，也被称为骑士巡游问题，是一个古老的数学谜题，源于公元前200年的印度棋手，问题的核心是寻找在一个棋盘上，通过特定的移动规则（即骑士移动，每次移动两格垂直或一格水平，或一格垂直两格水平），使得骑士能访问到每个格子恰好一次，形成一个封闭路径，同时也称为哈密尔顿圈。这个题目不仅考验了空间想象和策略规划，还涉及到了图论中的基本概念。 本文由吴英和李传文两位作者针对欧拉对 Knight's Tour Problem 的经典解法进行了深入研究，他们指出欧拉的解法实质上对应于二部图中的一条哈密尔顿圈。在这里，二部图是指图中顶点可以分为两部分，每部分内部没有边，但两部分之间有边相连。哈密尔顿圈是图论中的一个重要概念，它是一条经过图中所有顶点且仅一次的闭合路径。 文章利用了8×8棋盘的对称性和同构图特性，对欧拉解法进行了拓展，不仅提供了以任意棋格作为起点的其他解法，而且探讨了如何将这个方法推广到不同尺寸的棋盘上，如3×4、8×16和16×16。对于更大的棋盘，如8m×8n（m>2, n>2），作者提出了猜想，但并未给出明确的解法，因为随着棋盘大小的增加，问题的复杂性显著上升。 作者还提及了关键的理论背景，如无向图的定义（其中每条边没有方向）以及顶点度的概念，这些都是理解骑士巡游问题的关键。环（loop）的定义则与寻找循环路径相关，而哈密尔顿路则是指包含所有顶点但不形成环的路径。 这篇首发论文通过对 Knight's Tour Problem 的图论分析，揭示了其内在的结构规律，并探索了更广泛的应用可能性。它不仅提供了对传统问题的新见解，也为后续的研究者们提供了新的思考角度和挑战。