主题
Search

凯莱图


CayleyGraph

G 为一个 ,并设 S subset= G 为群元素的集合,使得 单位元 I not in S。与 (G,S) 关联的凯莱图被定义为 有向图,其顶点与每个群元素关联,且有有向边 (g,h),每当 gh^(-1) in S 时。凯莱图可能取决于生成集的选择,并且是 连通的 当且仅当 S 生成 G (即,集合 SG群生成元)。

需要注意的是,术语“凯莱图”也用于 S 被隐式地理解为群的生成元集合时,在这种情况下,图总是连通的(但通常,仍然取决于生成元的选择)。群 G 的这种凯莱图可以使用 Wolfram 语言 计算,使用CayleyGraph[G],其中使用的生成元是那些由以下命令返回的生成元GroupGenerators[G]。

更复杂的是,适当有向凯莱图的无向版本也被称为凯莱图。

特定生成元集合的 交错群 A_n 的无向凯莱图有时被称为 交错群图循环群 C_n 的凯莱图是 圈图 C_n,而 二面体群 D_n 的凯莱图是 棱柱图 Y_n。其他属于凯莱图的图类包括 循环图(如果需要生成集则连通;如果不要求则可能不连通)、立方体连接环汉明图超立方体图

有向图凯莱图的每个节点的 边重数 相同。(有向或无向)凯莱图始终是 顶点传递图,但反之不一定成立。然而,在小型 顶点传递图 中,很大一部分是凯莱图(McKay 和 Royle 1990)。

Royle 维护了一个非必要连通的顶点传递图列表,其中包含顶点数最多为 31 的凯莱图或非凯莱图的指定,尽管对于 27、28 和 30 个顶点的值尚未经过独立验证(尽管群中的错误只会影响图,如果以某种方式遗漏了最小传递群,因此不太可能出现错误)。顶点数为 n=1, 2, ... 的非必要连通凯莱图的数量分别为 1, 2, 2, 4, 3, 8, 4, 14, 9, 20, 8, 74, ... (OEIS A185959;McKay 和 Royle 1990,McKay 和 Praeger 1994),以及存在非凯莱顶点传递图的顶点数分别为 10, 15, 16, 18, 20, 24, 26, 28, 30, ....

最小的顶点传递非凯莱图是 彼得森图 P(McKay 和 Praeger 1994),而最小的非连通顶点传递非凯莱图是两个 P 的副本。

CayleyGraphCubical

凯莱图可以通过从生成元排列集合 {P_i}(不包括单位排列)开始生成,并相互排列元素直到不再有新的排列产生。这会产生一个在元素排列下闭合的集合 S。如果对于某些 P_k in SP_k(P_i)=P_j 成立,则连接每对排列 (P_i,P_j) 与一条边,然后得到一个凯莱图。

唯一可以给出平面凯莱图的群恰好是 Z_nZ_2×Z_nD_nS_4A_4A_5,正如 Maschke (1896) 所证明的那样。

下表列出了一些由少量小排列生成的凯莱图的无向版本。

生成元
16-胞{{1,2,4,3}, {2,1,3,4}, {2,1,4,3}, {3,4,1,2}, {3,4,2,1}}
循环图 Ci_(12)(1,3){{1,2,3,5,4}, {1,2,4,3,5}, {2,1,3,5,4}, {2,1,5,4,3}}
完全二分图 K_(4,4){{1,2,4,3}, {2,1,3,4}, {3,4,2,1}}
{{1,2,4,3}, {2,1,3,4}, {3,4,1,2}, {4,3,2,1}}
{{1,2,4,5,6,3}, {2,1,4,5,6,3}}
完全图 K_6{{1,3,2}, {2,1,3}, {2,3,1}, {3,2,1}}
{{1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,3,2}}
{{1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,2,3}, {1,4,3,2}}
立方图{{1,2,4,3}, {3,4,2,1}}
{{1,2,4,3}, {2,1,3,4}, {3,4,1,2}}
{{1,2,3,5,4}, {1,4,5,3,2}}
立方对称图 F_(24)A{{1,2,4,3}, {1,3,2,4}, {3,2,1,4}}
{{1,2,3,4,6,5}, {2,5,4,6,3,1}}
立方对称图 F_(60)A{{1,3,2,5,4}, {2,1,4,3,5}, {4,5,3,1,2}}
立方顶点传递图 Ct19{{1,2,3,4,6,5}, {1,2,4,3,6,5}, {5,6,3,4,1,2}}
立方顶点传递图 Ct23{{1,2,3,4,6,5}, {2,3,1,5,6,4}}
立方顶点传递图 Ct28{{1,3,2,5,4}, {2,3,4,1,5}}
立方顶点传递图 Ct37{{1,2,4,3}, {1,3,2,4},{3,4,1,2}}
立方顶点传递图 Ct38{{1,2,3,4,5,7,6}, {2,3,1,6,7,4,5}}
立方顶点传递图 Ct41{{1,2,4,3}, {1,3,2,4},{2,1,4,3}}
立方顶点传递图 Ct42{{1,2,3,4,5,7,6}, {2,3,4,1,6,5,7}}
立方八面体图{{1,3,4,2}, {2,3,1,4}}
{{1,3,4,2}, {1,4,2,3}, {2,3,1,4}}
{{1,3,4,2}, {1,4,2,3}, {2,3,1,4}, {3,1,2,4}}
{{1,2,4,5,3}, {1,3,4,2,5}}
5-圈图{{2,3,4,5,1}, {5,1,2,3,4}}
6-圈图{{1,3,2}, {2,1,3}}
{{1,2,4,3}, {1,3,2,4}}
{{1,2,3,5,4}, {1,2,4,3,5}}
8-圈图{{1,2,4,3}, {3,4,1,2}}
{{1,2,3,5,4}, {1,4,5,2,3}}
10-圈图{{1,3,2,5,4}, {2,1,4,3,5}}
12-圈图{{1,2,3,5,4}, {2,1,4,3,5}}
富兰克林图{{1,2,3,5,4}, {1,2,4,3,5}, {2,1,3,5,4}}
{{1,2,3,4,5,7,6}, {1,2,3,4,6,5,7}, {1,2,4,3,5,7,6}}
大斜方立方八面体图{{1,2,3,4,5,7,6}, {1,2,3,4,6,5,7}, {1,3,2,5,4,7,6}}
二十面体图{{1,3,4,2}, {2,1,4,3}, {2,3,1,4}}
{{1,3,4,2}, {1,4,2,3}, {2,1,4,3}, {2,3,1,4}}
{{1,3,4,2}, {1,4,2,3}, {2,1,4,3}, {2,3,1,4}, {3,1,2,4}}
4-莫比乌斯梯子{{1,2,4,3}, {2,1,4,3}, {3,4,1,2}}
八面体图{{1,3,2}, {2,1,3}, {2,3,1}}
{{1,2,4,3}, {1,3,2,4}, {1,3,4,2}}
{{1,2,4,3}, {1,3,2,4}, {1,3,4,2}, {1,4,2,3}}
{{1,2,4,5,3}, {2,1,4,5,3}}
{{1,2,4,5,3}, {2,1,4,5,3}}
帕普斯图{{1,2,3,4,6,5}, {2,3,1,5,4,6}}
2-路径图{{2,1}}
{{1,3,2}}
五胞体{{2,3,4,5,1}, {3,4,5,1,2}}
5-棱柱图{{1,3,2,5,4}, {2,4,1,5,3}}
{{1,3,2,5,4}, {2,4,1,5,3}}
6-棱柱图{{1,2,3,5,4}, {2,1,4,5,3}}
{{1,2,3,5,4}, {2,1,4,5,3}}
小斜方二十面十二面体图{{1,2,4,5,3}, {3,4,2,5,1}}
小斜方立方八面体图{{1,3,4,2}, {2,3,4,1}}
{{1,3,4,2}, {1,4,2,3}, {2,3,4,1}}
{{1,3,4,2}, {1,4,2,3}, {2,3,4,1}, {4,1,2,3}}
{{1,2,4,5,3}, {1,3,4,5,2}}
扭棱立方图{{1,2,4,3}, {2,3,1,4}, {2,3,4,1}}
{{1,2,4,3}, {2,3,1,4}, {2,3,4,1}, {3,1,2,4}}
{{1,2,4,3}, {2,3,1,4}, {2,3,4,1}, {3,1,2,4}, {4,1,2,3}}
正方形 反棱柱图{{1,2,4,3}, {3,4,1,2}, {3,4,2,1}}
{{1,2,4,3}, {3,4,1,2}, {3,4,2,1}, {4,3,1,2}}
正方图{{1,2,4,3}, {2,1,3,4}}
{{1,2,3,5,4}, {1,3,2,4,5}}
超立方体图{{1,2,3,4,6,5}, {1,2,4,3,5,6}, {3,4,2,1,5,6}}
四面体图{{2,1,4,3}, {3,4,2,1}}
{{1,2,4,3}, {2,1,3,4}, {2,1,4,3}}
{{1,3,2,5,4}, {1,4,5,3,2}}
三角形图{{2,3,1}}
{{1,3,4,2}, {1,4,2,3}}
{{1,2,4,5,3}, {1,2,5,3,4}}
三角 棱柱图{{1,3,2}, {2,3,1}}
{{1,2,4,3}, {1,3,4,2}}
{{1,2,4,3}, {1,3,4,2}, {1,4,2,3}}
{{1,2,3,5,4}, {1,2,4,5,3}}
截角立方体图{{1,2,4,3}, {2,3,1,4}}
{{1,2,4,3}, {2,3,1,4}, {3,1,2,4}}
{{1,2,3,5,4}, {1,3,4,2,5}}
截角十二面体图{{1,2,4,5,3}, {3,4,1,2,5}}
截角二十面体图{{1,3,2,5,4}, {2,3,4,5,1}}
截角八面体图{{1,2,4,3}, {2,3,4,1}}
{{1,2,4,3}, {1,3,2,4}, {2,1,3,4}}
{{1,2,3,5,4}, {1,3,4,5,2}}
截角四面体图{{1,3,4,2}, {2,1,4,3}}
{{1,3,4,2}, {1,4,2,3}, {2,1,4,3}}
{{1,2,4,5,3}, {1,3,2,5,4}}
效用图 K_(3,3){{1,3,2}, {2,1,3}, {3,2,1}}
{{1,2,4,3}, {1,3,2,4}, {1,4,3,2}}
{{1,2,3,5,4}, {2,3,1,5,4}}
{{1,2,3,5,4}, {2,3,1,5,4}}
CayleyGraphD7

例如,二面体群 D_7 是一个 14 个元素的 置换群,它可以由分别对应于反转和旋转的两个元素生成。因此,任何两个这样的元素都会给出一个具有 14 个节点和 28 条边的连通凯莱图。上面的左图显示了生成器选择为 (7, 1, 2, 3, 4, 5, 6) 和 (7, 6, 5, 4, 3, 2, 1) 的凯莱图,其中反转以红色显示,旋转以蓝色显示。任何两个仅对应于旋转的元素将给出一个不连通的图,并且恰好有 15 对这样的元素,因为有 (6; 2) 种方法从六个可能的旋转中选取两个元素。(这里,数字 6 而不是 7 出现,因为单位元素可能不是给出凯莱图的子集的成员。)右图显示了由元素 (7, 1, 2, 3, 4, 5, 6) 和 (6, 7, 1, 2, 3, 4, 5) 生成的 D_7 的凯莱图,该图是不连通的,因为这些元素不生成该群(特别是,在没有翻转的情况下,正阶排列无法切换到负阶;因此获得两个独立的环)。

CayleyGraphA4

上图显示了使用元素 (2, 1, 4, 3) 和 (2, 3, 1, 4) 作为生成元的 交错群 A_4 的凯莱图,它是 截角四面体图 的有向形式。

CayleyGraphK4

如果 完全图 K_4 的三个顶点被不同颜色的石头覆盖,并且任何石头都可以移动到空顶点,则所有位置的图形成一个凯莱图,边表示相邻位置(左图)。这对应于 对称群 S_4 的凯莱图,使用元素 (2, 1, 3, 4)、(3, 2, 1, 4) 和 (4, 2, 3, 1) 作为生成元。结果证明,该图是唯一具有 24 个顶点的 立方对称图 的有向版本(右图)。

Royle 构建了顶点数不超过 1000 的所有立方凯莱图,但不包括顶点数为 512 和 768 的图。

Cayley graphs

无限群的凯莱图提供了有趣的几何形状。例如,上面说明了两个生成元上的 自由群 的凯莱图(绘制到连续级别),分别表示水平和垂直位移。每个新边都以一半大小绘制,以给出 分形 图像。


另请参阅

交错群图, 笼形图, 凯莱树, 离散群, 自由群, , , 群生成元, 非凯莱图, 魔方图, 顶点传递图,

此条目的部分内容由 Todd Rowland 贡献

此条目的部分内容由 Ed Pegg, Jr. (作者链接) 贡献

使用 Wolfram|Alpha 探索

参考文献

Holton, D. A. 和 Sheehan, J. 彼得森图。 英国剑桥:剑桥大学出版社,第 292-293 页,1993 年。Maschke, H. "有限群的表示"。美国数学杂志 16, 156-194, 1896 年。McKay, B. D. 和 Praeger, C. E. "不是凯莱图的顶点传递图。I." 澳大利亚数学学会杂志 A 系列 56, 53-63, 1994 年。McKay, B. D. 和 Royle, G. "构造最多 26 个顶点和传递自同构群的所有简单图。" 组合数学 30, 161-176, 1990 年。Royle, G. "凯莱图。" http://school.maths.uwa.edu.au/~gordon/remote/cayley/.Royle, G. "传递图。" http://school.maths.uwa.edu.au/~gordon/trans/.Sloane, N. J. A. 序列 A185959,来自“整数序列在线百科全书”。Wolfram, S. 一种新的科学。 伊利诺伊州香槟市:Wolfram Media,第 938 页,2002 年。

在 Wolfram|Alpha 上引用

凯莱图

请引用本文为

Pegg, Ed Jr.; Rowland, Todd; 和 Weisstein, Eric W. "凯莱图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/CayleyGraph.html

学科分类