騎士圖

騎士圖是 個頂點上的圖，其中每個頂點代表一個 棋盤上的一個方格，每條邊對應於騎士的合法移動（騎士的移動方式為沿一個軸移動一格，同時沿另一個軸移動兩格）。因此，它是一個 -跳躍者圖。

上面展示了從棋盤抽象出來的 騎士圖，其中 , ..., 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)。