主題
Search

皇后圖

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook
QueenGraphsChessboard

m×n 皇后圖 Q_(m,n) 是一個具有 mn 個頂點的圖，其中每個頂點代表一個 m×n 棋盤上的一個方格，每條邊對應於皇后的一次合法移動。

QueensGraph

(2,n)-皇后圖具有良好的嵌入，如上圖所示。一般來說，頂點對應於棋盤方格的嵌入，當繪製為直線時，其邊會與其他邊重疊，唯一的非平凡例外是 (2,2)-皇后圖。

皇后圖在 Wolfram 語言中實現為GraphData[{"Queen", {m, n}}].

下表總結了皇后圖的一些特殊情況。

Q_(m,n)名稱
Q_(1,n)完全圖 K_n
Q_(2,2)四面體圖 K_4

下表總結了一些命名的皇后圖的補圖。

GG^_
(2,3)-皇后圖(2,3)-騎士圖
(2,4)-皇后圖2P_4
(3,3)-皇后圖(3,3)-騎士圖

所有皇后圖都是 哈密頓圖 和 雙連通圖。唯一 平面 且唯一 正則 皇后圖是 (2,2)-皇后圖，它與 四面體圖 K_4 同構。

唯一 完美 皇后圖是 Q_(1,n), Q_(2,n), 和 Q_(3,3)。

給出 Q(n,n) 的 4-圈數量的閉合公式為

60c_4=n(n-1)(21n^3+526n^2-1709n+996)-60(3n^2-12n+4)|_1/2n_|

(Perepechko 和 Voropaev)。

對於 (n,n)-皇后圖，當 n=2, 3, ... 時，哈密頓圈的數量分別為 6, 3920, ... (OEIS A158663)，相應的 哈密頓路徑 的數量分別為 24, 45856, ... (OEIS A158664)。

由於 (n,n)-皇后圖的每一行和每一列都是一個 n-團，因此這些圖的 色數 至少為 n。事實上，當 n=1,5 (mod 6) 時，可以證明 n 種顏色就足夠了。實際上，對於 n=2, 3, ...，色數分別為 4, 5, 5, 5, 7, 7, 9, 10, 11, 11, 12, 13, ... (OEIS A088202)。

當 Q_(m,n) 中 m 或 n 至少有一個是偶數時 (J. DeVincentis 和 S. Wagon，私人通訊，11 月 13-14 日，2011 年) 以及當 m 和 n 均為奇數且 m<=n<=2m-1 時 (S. Wagon，私人通訊，2015 年 12 月 9 日)，皇后圖 Q_(m,n) 為 1 類。另一方面，當 m,n 為奇數且 n>=(2m^3-11m+18)/3 時，皇后圖顯然為 2 類 (S. Wagon，私人通訊，2015 年 12 月 9 日)，這僅留下 m,n 為奇數且 2m-1<n<(2m^3-11m+18)/3 的情況有待研究。

另請參閱

主教圖, 黑主教圖, 國王圖, 騎士圖, 皇后問題, 車圖, 三角蜂巢皇后圖, 白主教圖

使用 探索

參考文獻

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Chandra, A. K. "Independent Permutations, as Related to a Problem of Moser and a Theorem of Pólya." J. Combin. Th. Ser. A 16, 111-120, 1974.Chvátal, V. "Coloring the Queens Graph." http://users.encs.concordia.ca/~chvatal/queengraphs.html.Finozhenok, D. and Weakley, W. D. "An Improved Lower Bound for Domination Numbers of the Queen's Graph." Australasian J. Combin. 37, 295-300, 2007.Fricke, G. H.; Hedemiemi, S. M.; Hedetniemi, S. T.; McRae. A. A.; Wallis, C. K.; Jacobsen, M. S.; Martinand, H. W.; abd Weakley, W. D. "Combinatorial Problems on Chessboards: A Brief Survey." In Graph Theory, Combinatoricsand Applications, Vol. I, Prec. Seventh QuadrennialConf.on the Theory and Application sof Graphs (Ed. Alavi and Schwenk). Western Michigan University, 1995.Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 116-118 and 124-126, 1984.Gardner, M. The Unexpected Hanging and Other Mathematical Diversions. Chicago, IL: Chicago University Press, p. 191, 1991.Gosset, T. Mess. Math. 44, 48, 1914.Hwang, F. K. and Lih, K. W. "Latin Squares and Superqueens." J. Combin. Th. Ser. A 34, 110-114, 1983.Jarnicki, W.; Myrvold, W.; Saltzman, P.; and Wagon, S. "Properties, Proved and Conjectured, of Keller, Mycielski, and Queen Graphs." To appear in Ars Math. Comtemp. 2017.Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.Östergård, P. R. J. and Weakley, W. D. "Values of Domination Numbers of the Queen's Graph." Elec. J. Combin. 8, Issue 1, No. R29, 2001. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v8i1r29.Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Sloane, N. J. A. Sequence A088202, A158663, and A158664 in "The On-Line Encyclopedia of Integer Sequences."Shapiro, H. D. "Generalized Latin Squares on the Torus," Disc. Math. 24, 63-77, 1978.Vasquez, M. "New Results on the Queens n^2 Graph Coloring Problems." J. Heuristics 10, 407-413, 2004.Wagon, S. "Graph Theory Problems from Hexagonal and Traditional Chess." College Math. J. 45, 278-287, 2014.

引用為

Weisstein, Eric W. "皇后圖。" 來自 Web 資源。 https://mathworld.tw/QueenGraph.html

主題分類