骑士图

骑士图是 个顶点上的图，其中每个顶点代表一个 棋盘上的一个方格，每条边对应于骑士的合法移动（骑士的移动方式为沿一个轴移动一格，同时沿另一个轴移动两格）。因此，它是一个 -跳跃者图。

上面展示了从棋盘抽象出来的 骑士图，其中 , ..., 6。 骑士图是 单例图 ，而 骑士图与空图 同构（因为骑士无法从任何一个方格到达另一个方格）。

骑士图由一个 8-环 以及一个（与其他所有方格无法到达的）孤立中心顶点组成。

骑士图中的边数为 （是 三角形数的 8 倍），因此对于 , 2, ..., 前几个值为 0, 0, 8, 24, 48, 80, 120, ... (OEIS A033996)。

骑士图是 二分图，因此也是 完美图。

下表总结了一些命名的骑士图的补图。

-骑士图	-皇后图
-骑士图	-皇后图

骑士图在 Wolfram 语言中实现为KnightTourGraph[m, n]，并且可以使用以下方式获得预先计算的属性GraphData["Knight", m, n].

对于 ，-图环的数量的闭合公式， 骑士图由 给出，对于 为奇数，以及

(1)

（E. Weisstein，2014 年 11 月 16 日）。

骑士路径是骑士的一系列移动，使得棋盘上的每个方格恰好访问一次。因此，它是相应骑士图上的 哈密顿路径。Conrad et al. (1994) 表明， 棋盘上存在骑士路径 当且仅当 。

以上图示显示了 棋盘上的六条骑士路径，除了第一条之外，其余都是重入的。最后一条路径还具有额外的属性，即它是一个 半魔方，其行和列之和为 260，主对角线之和为 348 和 168 (Steinhaus 1999, p. 30)。

如果路径的最终位置与骑士的初始位置相隔一个骑士步，则该路径称为重入或封闭路径，并对应于底层骑士图上的 哈密顿环。Conrad et al. (1994) 表明， 棋盘上存在骑士巡游 当且仅当 且 为偶数。

回溯算法（其中允许骑士尽可能远地移动，直到遇到死胡同，此时它会后退若干步，然后尝试不同的路径）可用于查找骑士巡游，但这种方法可能非常慢。Warnsdorff (1823) 提出了一种算法，该算法通过计算每个位置的“后继”步骤的评分来找到路径，而无需任何回溯。在这里，一个位置的后继是那些尚未访问过且可以通过从给定位置一步到达的方格。对于后继数最少的后继，评分最高。通过这种方式，倾向于孤立的方格首先被访问，因此防止了被孤立（Roth）。此算法所需的时间大致与棋盘的方格数成线性增长，但不幸的是，计算机实现表明，对于大于 的棋盘，此算法会遇到死胡同，尽管它在较小的棋盘上效果良好（Roth）。

Conrad et al. (1994) 发现了另一种线性时间算法，并证明它解决了所有 的哈密顿路径问题。Conrad et al. 算法通过将棋盘分解为更小的棋盘（不一定是正方形）来工作，对于这些棋盘，显式解是已知的。该算法相当复杂，因为它必须处理许多特殊情况，但 A. Roth 已在 Wolfram 语言中实现了该算法。上面的示例巡游图示了 棋盘，其中 到 8。

对于 棋盘，(无向) 封闭骑士巡游（即哈密顿环）的数量，其中 , 2, ... 分别是 0, 0, 9862, 13267364410532, ... (OEIS A001230; Ball 和 Coxeter 1987; Wegener 2000, p. 369; Elkies 和 Stanley 2003)。对于 棋盘，其中 为奇数，则没有封闭巡游。Kraitchik (1942, pp. 264-265) 还指出，在 方格上共有 1728 条路径，其中 8 条是对称的，而在 方格上有 5 条双重对称路径。Wegener 和 Löbbing (1996) 计算了 棋盘的定向骑士图的环数，结果为 。他们还计算了无向巡游的数量，得到一个不正确的答案 （它不能被 4 整除，因为它必须被 4 整除）。Wegener 随后的书中给出了正确的值 (Wegener 2000)，并且也与 B. D. McKay 未发表的计算结果一致。

对于 棋盘，最长的“不交叉”骑士巡游，其中 , 4, ... 分别为 2, 5, 10, 17, 24, 35, ... (OEIS A003192)。

下表扩展并更正了 Kraitchik (1942, pp. 264-265) 给出的一些其他结果。此处，DHP 表示几何上不同的哈密顿路径，DSHP 表示几何上不同的对称路径，HP 表示总的（定向）哈密顿路径，DHC 表示几何上不同的哈密顿环，HC 表示总的（定向）哈密顿环。

尺寸	DHP	DSHP	HP	DHC	HC
Sloane			A118067		A158074
	0	0	0	0	0
	0	0	0	0	0
	3		16	0	0
	0		0	0	0
	0		0	0	0
	14	2	104	0	0
	104		792	0	0
	146	16	1120	0	0
	773		6096	8	32
	2698	58	21344	0	0
	14350		114496	28	352
	32296		257728	0	0
					3072
				0	0
					30848

令人惊讶的是， 骑士图上的哈密顿环的数量由 21 阶线性递归方程给出

(2)

具有相应的闭合形式 生成函数

			(3)
			(4)

其中

			(5)
			(6)

这个结果是由 D. E. Knuth 和 N. D. Elkies 在 1994 年 4 月独立获得的，他们都使用了所谓的传递矩阵方法 (Stanley 1999, Ch. 4.7; Elkies 和 Stanley 2003)。

对于 棋盘，可能的（定向）封闭巡游的数量，其中 , 4, ... 分别为 16, 0, 164, 1488, 12756, 62176, 379376, 2426224, ... (OEIS A123935; Kraitchik 1942, p. 263)。与 情况一样，已知此序列由具有常系数的线性递归关系给出，尽管似乎尚未显式计算出此递归关系。

骑士图是 哈密顿可编织图 当且仅当 , ，并且 , 中至少有一个是偶数 (Dupuis and Wagon 2014)。