主题
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 时,则不是哈密顿图。

所有主教图都是完美的。


另请参阅

主教问题, 黑色主教图, 国王图, 骑士图, 皇后图, 车图, 三角蜂窝主教图, 白色主教图

使用 Wolfram|Alpha 探索

参考文献

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. "主教图。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/BishopGraph.html

主题分类