主題
Search

主教圖


BishopGraph

主教圖是由國際象棋主教棋子的可能移動形成的圖,主教棋子可以在棋盤(或任何其他棋盤)上沿對角線移動任意長度。為了形成該圖,每個棋盤格被視為一個頂點,而透過允許的主教移動連線的頂點被視為邊。

由於主教從一種顏色的方格開始並沿對角線移動時始終停留在相同顏色的方格上,因此所有主教圖都是斷開連線的(除了 1×1 棋盤上的平凡單例圖,它是平凡連線的)。

特殊情況總結在下表中。

(m,n)-主教圖
(1,n)n-空圖 K^__n
(2,n)2 n-路徑圖 2P_n
BishopGraphBlackWhite

對應於在白色方格和黑色方格上移動的主教的 (m,n)-主教圖的連通分量(即,白色主教圖黑色主教圖,分別在上方針對小方格棋盤進行了說明)是同構的,當且僅當 iff mn 不都為奇數。請注意,此處,“白色”和“黑色”指的是給定主教在其上移動的方格的顏色,而與主教棋子本身的顏色無關。

B(n,n) 的 c_kk-圖環的數目 B(n,n) 的閉合公式由下式給出

c_3=1/6(n-2)(n-1)^2n
(1)
c_4=1/(30)(n-2)(n-1)n(3n^2-11n+11)
(2)

 840c_6=n(n-1)(40n^5-289n^4+887n^3-2193n^2+3792n-1934)-210(n^2-12n+26)|_1/2n_|
(3)

對於 n!=3, 7, ...,其中最後一個歸功於 Perepechko 和 Voropaev。

S. Wagon(私人通訊,2012 年 8 月 17 日)表明,對於 (m,n)-白色主教圖 B(m,n) 是哈密頓圖,對於 4<=m<=n 以及當 m=3n>=4 時,而對於 (m,n)=(3,3) 和平凡情況 m=2 或 1 時,則不是哈密頓圖。

所有主教圖都是完美的。


另請參閱

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

使用 探索

參考文獻

Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Wagon, S. "Graph Theory Problems from Hexagonal and Traditional Chess." College Math. J. 45, 278-287, 2014.

請引用為

Weisstein, Eric W. "主教圖。" 來自 —— 資源。 https://mathworld.tw/BishopGraph.html

主題分類