设 为一个 群,并设
为群元素的集合,使得 单位元
。与
关联的凯莱图被定义为 有向图,其顶点与每个群元素关联,且有有向边
,每当
时。凯莱图可能取决于生成集的选择,并且是 连通的 当且仅当
生成
(即,集合
是
的 群生成元)。
需要注意的是,术语“凯莱图”也用于 被隐式地理解为群的生成元集合时,在这种情况下,图总是连通的(但通常,仍然取决于生成元的选择)。群
的这种凯莱图可以使用 Wolfram 语言 计算,使用CayleyGraph[G],其中使用的生成元是那些由以下命令返回的生成元GroupGenerators[G]。
更复杂的是,适当有向凯莱图的无向版本也被称为凯莱图。
特定生成元集合的 交错群 的无向凯莱图有时被称为 交错群图。循环群
的凯莱图是 圈图
,而 二面体群
的凯莱图是 棱柱图
。其他属于凯莱图的图类包括 循环图(如果需要生成集则连通;如果不要求则可能不连通)、立方体连接环、汉明图 和 超立方体图。
有向图凯莱图的每个节点的 边重数 相同。(有向或无向)凯莱图始终是 顶点传递图,但反之不一定成立。然而,在小型 顶点传递图 中,很大一部分是凯莱图(McKay 和 Royle 1990)。
Royle 维护了一个非必要连通的顶点传递图列表,其中包含顶点数最多为 31 的凯莱图或非凯莱图的指定,尽管对于 27、28 和 30 个顶点的值尚未经过独立验证(尽管群中的错误只会影响图,如果以某种方式遗漏了最小传递群,因此不太可能出现错误)。顶点数为 , 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, ....
最小的顶点传递非凯莱图是 彼得森图 (McKay 和 Praeger 1994),而最小的非连通顶点传递非凯莱图是两个
的副本。
凯莱图可以通过从生成元排列集合 (不包括单位排列)开始生成,并相互排列元素直到不再有新的排列产生。这会产生一个在元素排列下闭合的集合
。如果对于某些
,
成立,则连接每对排列
与一条边,然后得到一个凯莱图。
唯一可以给出平面凯莱图的群恰好是 、
、
、
、
和
,正如 Maschke (1896) 所证明的那样。
下表列出了一些由少量小排列生成的凯莱图的无向版本。
图 | 生成元 |
16-胞 图 | |
循环图 | |
完全二分图 | |
完全图 | |
立方图 | |
立方对称图 | |
立方对称图 | |
立方顶点传递图 Ct19 | |
立方顶点传递图 Ct23 | |
立方顶点传递图 Ct28 | |
立方顶点传递图 Ct37 | |
立方顶点传递图 Ct38 | |
立方顶点传递图 Ct41 | |
立方顶点传递图 Ct42 | |
立方八面体图 | |
5-圈图 | |
6-圈图 | |
8-圈图 | |
10-圈图 | |
12-圈图 | |
富兰克林图 | |
大斜方立方八面体图 | |
二十面体图 | |
4-莫比乌斯梯子 | |
八面体图 | |
帕普斯图 | |
2-路径图 | |
五胞体 图 | |
5-棱柱图 | |
6-棱柱图 | |
小斜方二十面十二面体图 | |
小斜方立方八面体图 | |
扭棱立方图 | |
正方形 反棱柱图 | |
正方图 | |
超立方体图 | |
四面体图 | |
三角形图 | |
三角 棱柱图 | |
截角立方体图 | |
截角十二面体图 | |
截角二十面体图 | |
截角八面体图 | |
截角四面体图 | |
效用图 | |
例如,二面体群 是一个 14 个元素的 置换群,它可以由分别对应于反转和旋转的两个元素生成。因此,任何两个这样的元素都会给出一个具有 14 个节点和 28 条边的连通凯莱图。上面的左图显示了生成器选择为 (7, 1, 2, 3, 4, 5, 6) 和 (7, 6, 5, 4, 3, 2, 1) 的凯莱图,其中反转以红色显示,旋转以蓝色显示。任何两个仅对应于旋转的元素将给出一个不连通的图,并且恰好有 15 对这样的元素,因为有
种方法从六个可能的旋转中选取两个元素。(这里,数字 6 而不是 7 出现,因为单位元素可能不是给出凯莱图的子集的成员。)右图显示了由元素 (7, 1, 2, 3, 4, 5, 6) 和 (6, 7, 1, 2, 3, 4, 5) 生成的
的凯莱图,该图是不连通的,因为这些元素不生成该群(特别是,在没有翻转的情况下,正阶排列无法切换到负阶;因此获得两个独立的环)。
上图显示了使用元素 (2, 1, 4, 3) 和 (2, 3, 1, 4) 作为生成元的 交错群 的凯莱图,它是 截角四面体图 的有向形式。
如果 完全图 的三个顶点被不同颜色的石头覆盖,并且任何石头都可以移动到空顶点,则所有位置的图形成一个凯莱图,边表示相邻位置(左图)。这对应于 对称群
的凯莱图,使用元素 (2, 1, 3, 4)、(3, 2, 1, 4) 和 (4, 2, 3, 1) 作为生成元。结果证明,该图是唯一具有 24 个顶点的 立方对称图 的有向版本(右图)。
Royle 构建了顶点数不超过 1000 的所有立方凯莱图,但不包括顶点数为 512 和 768 的图。

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