凯莱图

凯莱图（英语：Cayley graph），也叫做凯莱着色图，是将离散群的抽象结构画出的一种图。它的定义是凯莱定理（以阿瑟·凯莱命名）所暗含的。画凯莱图时，要选定群的一个生成元集合（通常有限），不同选法可能得到不同的凯莱图。凯莱图是组合群论（英语：Combinatorial group theory）与几何群论（英语：Geometric group theory）的中心工具。

在两个生成元a和b上的自由群的凯莱图

定义

假设${\displaystyle G}$是群，而${\displaystyle S}$是G的生成集。凯莱图${\displaystyle \Gamma =\Gamma (G,S)}$，是如下构造的着色的有向图：

• ${\displaystyle G}$的每个元素${\displaystyle g}$对应一个顶点。换言之，图${\displaystyle \Gamma }$的顶点集合${\displaystyle V(\Gamma )}$视为与${\displaystyle G}$等同；
• ${\displaystyle S}$中每个生成元${\displaystyle s}$，对应一种颜色${\displaystyle c_{s}}$；
• 对于任何${\displaystyle g\in G,s\in S}$，画一条由元素${\displaystyle g}$至${\displaystyle gs}$的有向边，染成${\displaystyle c_{s}}$色。换言之，边集合${\displaystyle E(\Gamma )}$由形如${\displaystyle (g,gs)}$的有序对构成，边的颜色由${\displaystyle s\in S}$确定。

在几何群论中，集合${\displaystyle S}$通常取为有限、对称（即满足${\displaystyle S=S^{-1}}$），并且不包含这个群的单位元${\displaystyle e}$。在这种情况下，凯莱图是简单无向图：它的边没有方向（由对称性），并且不包含自环（因为${\displaystyle e\notin S}$）。

例子

• 假设${\displaystyle G=\mathbb {Z} }$是无限循环群（即整数的加法群），而集合${\displaystyle S}$由标准生成元${\displaystyle 1}$和它的逆元（用加法符号为${\displaystyle -1}$）构成，则它的凯莱图是无穷链（英语：Path graph）。
• 类似地，如果${\displaystyle G=\mathbb {Z} _{n}}$是${\displaystyle n}$阶循环群（模${\displaystyle n}$的加法群），而${\displaystyle S}$仍由${\displaystyle G}$的标准生成元${\displaystyle 1}$与逆元${\displaystyle -1}$构成，则凯莱图是环图${\displaystyle C_{n}}$。
• 群的直积的凯莱图（新生成集取为原生成集之笛卡尔积），是对应的凯莱图的笛卡尔积（英语：Cartesian product of graphs）。因此阿贝尔群${\displaystyle \mathbb {Z} ^{2}}$，关于四个元素${\displaystyle (\pm 1,\pm 1)}$组成的生成集的凯莱图，是平面${\displaystyle \mathbb {R} ^{2}}$上的无穷网格，而带有类似的生成集的直积${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{m}}$的凯莱图，是环面上的${\displaystyle n}$乘${\displaystyle m}$有限网格。
• 二面体群${\displaystyle D_{4}}$有群展示：$${\displaystyle \langle a,b|a^{4}=b^{2}=e,ab=ba^{3}\rangle .}$$左图是关于两个生成元${\displaystyle a}$和${\displaystyle b}$的凯莱图，其中红色箭头表示左乘元素${\displaystyle a}$（顺时针旋转${\displaystyle 90^{\circ }}$）。而因为元素${\displaystyle b}$（左右反射）自反，所以表示左乘元素${\displaystyle b}$的蓝色线是无方向的，故左图混合了有向边与无向边：它有${\displaystyle 8}$个顶点、${\displaystyle 8}$条有向边、${\displaystyle 4}$条无向边。

  

  二面体群${\displaystyle D_{4}}$关于两个生成元${\displaystyle a}$和${\displaystyle b}$的凯莱图。

  

  ${\displaystyle D_{4}}$关于两个自反生成元的凯莱图

  同一个群${\displaystyle D_{4}}$，亦可画出不同的凯莱图，如右图。${\displaystyle b}$仍表示左右反射，而${\displaystyle c}$则是关于主对角线的反射，以粉红色线表示。由于两个反射皆自反，右边的凯莱图完全无向。对应的群展示是$${\displaystyle \langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle .}$$
• 条目开头的图，是两个生成元${\displaystyle a,b}$上的自由群，关于生成集合${\displaystyle S=\{a,b,a^{-1},b^{-1}\}}$的凯莱图，而正中央的黑点，是单位元${\displaystyle e}$。沿着边向右走表示右乘${\displaystyle a}$，而沿着边向上走表示乘以${\displaystyle b}$。因为自由群没有关系，它的凯莱图中没有环。这个凯莱图是证明巴拿赫-塔斯基悖论的关键。
• 右边有离散海森堡群

  

  海森堡群的一部分（颜色仅为方便看清分层）

$${\displaystyle \left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}}$$ 的凯莱图。所用的三个生成元${\displaystyle X,Y,Z}$，分别对应${\displaystyle (x,y,z)=(1,0,0),\ (0,1,0),\ (0,0,1)}$。其关系为${\displaystyle Z=XYX^{-1}Y^{-1},\ XZ=ZX,\ YZ=ZY}$，亦可从图中看出。本群为非交换无穷群。虽然是三维空间，其凯莱图的增长（英语：Growth rate (group theory)）却是${\displaystyle 4}$阶的。^{[来源请求]}

特征

群${\displaystyle G}$通过左乘作用在自身上（参见凯莱定理）。这个作用可以看作${\displaystyle G}$作用在它的凯莱图上。明确而言，一个元素${\displaystyle h\in G}$映射一个顶点${\displaystyle g\in V(\Gamma )}$到另一个顶点${\displaystyle hg\in V(\Gamma )}$。凯莱图的边集合被这个作用所保存：边${\displaystyle (g,gs)}$变换成边${\displaystyle (hg,hgs)}$。任何群在自身上的左乘作用是简单传递的，特别是凯莱图是顶点传递（英语：Vertex-transitive graph）的。事实上，反向的结论也成立，即有下列等价刻划，称为扎比杜西定理（英语：Sabidussi's Theorem）：

（无标记又无着色）有向图${\displaystyle \Gamma }$是群${\displaystyle G}$的某个凯莱图，当且仅当${\displaystyle G}$可作为图自同构（就是要保存边的集合）作用在${\displaystyle \Gamma }$上，且该作用简单传递。^[1]

要从一个凯莱图${\displaystyle \Gamma =\Gamma (G,S)}$找回群${\displaystyle G}$和生成集${\displaystyle S}$，先选择一个顶点${\displaystyle v_{1}\in V(\Gamma )}$，标上群的单位元${\displaystyle e}$。接着，对${\displaystyle \Gamma }$的每个顶点${\displaystyle v}$，${\displaystyle G}$中有唯一元素将${\displaystyle v_{1}}$变换到${\displaystyle v}$，于是可以在${\displaystyle v}$处标记该唯一元素。最后要确定${\displaystyle G}$的哪个生成集${\displaystyle S}$，产生凯莱图${\displaystyle \Gamma }$，而所求的${\displaystyle S}$就是毗连${\displaystyle v_{1}}$的顶点标记的集合。生成集合是有限（这是凯莱图的共同假定）当且仅当这个图是局部有限的（就是说每个顶点仅毗连于有限多条边）。

基本性质

• 如果生成集合的成员${\displaystyle s}$是自身的逆元，即${\displaystyle s=s^{-1}}$，则它一般被表示为无向边。
• 凯莱图${\displaystyle \Gamma (G,S)}$本质上依赖于如何选择生成集${\displaystyle S}$。例如，如果生成集合${\displaystyle S}$有${\displaystyle k}$个元素，则凯莱图的每个顶点都有${\displaystyle k}$条有向边进入，${\displaystyle k}$条有向边外出。当生成集合${\displaystyle S}$为对称集，且有${\displaystyle r}$个元素时，凯莱图是${\displaystyle r}$度的正则图。
• 在凯莱图中的环（“闭合路径”）指示${\displaystyle S}$的元素之间的关系。在群的凯莱复形此一更复杂的构造中，对应于关系的闭合路径被用多边形“填充”。
• 如果${\displaystyle f:G'\to G}$是满射群同态并且${\displaystyle G'}$的生成集合${\displaystyle S'}$的元素的像是不同的，则导出图覆叠（英语：Covering graph）映射$${\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),\quad }$$这里的${\displaystyle S=f(S')}$，特别是，如果群${\displaystyle G}$有${\displaystyle k}$个生成元，阶均不为${\displaystyle 2}$，并且这些生成元和它们的逆元构成集合${\displaystyle S}$，则该集合生成的自由群${\displaystyle F(S)}$有到${\displaystyle G}$的满同态（商映射），故${\displaystyle \Gamma (G,S)}$被自由群的凯莱图覆盖，即${\displaystyle 2k}$度的无限正则树。
• 即使集合${\displaystyle S}$不生成群${\displaystyle G}$，仍可以构造图${\displaystyle \Gamma (G,S)}$。但是，此情况下，所得的图并不连通。在这种情况下，这个图的每个连通分支对应${\displaystyle S}$所生成子群的一个陪集。
• 对于有限凯莱图（视为无向），其顶点连通性等于这个图的度的${\displaystyle 2/3}$。若生成集极小（即移除任一元素及其逆元，就不再生成整个群），则其顶点连通性等于度数。^[2]至于边连通性，则在任何情况下皆等于度数。^[3]
• 群${\displaystyle G}$的每个乘性特征标（英语：Multiplicative character）${\displaystyle \chi }$都给出${\displaystyle \Gamma (G,S)}$邻接矩阵的特征向量。若${\displaystyle G}$为交换群，则对应的特征值为${\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi (s).}$特别地，平凡特征标（将所有元素映至常数${\displaystyle 1}$）对应的特征值，等于${\displaystyle \Gamma (G,S)}$的度数，即${\displaystyle S}$的元素个数。若${\displaystyle G}$为交换群，则恰有${\displaystyle |G|}$个特征标，故已足以确定全部特征值。

Schreier陪集图

如果转而把顶点作为固定子群${\displaystyle H}$的右陪集，就得到了一个有关的构造Schreier陪集图，它是陪集枚举或Todd-Coxeter算法的基础。

与群论的关系

研究图的邻接矩阵特别是应用谱图理论的定理能洞察群的结构。

参见

• 群的生成集合
• 群的展示

注释

1. Sabidussi, Gert. On a class of fixed-point-free graphs [论一类无不动点的图]. Proceedings of the American Mathematical Society. October 1958, 9 (5): 800–4. JSTOR 2033090. doi:10.1090/s0002-9939-1958-0097068-7  （英语）.
2. Babai, L. Technical Report TR-94-10. University of Chicago. 1996.存档副本. [2010-08-29]. （原始内容存档于2010-06-11）.
3. 见定理3.7，Babai, László. 27. Automorphism groups, isomorphism, reconstruction [第27章：自同构群、同构、重构] (PDF). Graham, Ronald L.; Grötschel, Martin; Lovász, László (编). Handbook of Combinatorics [组合手册] 1. Elsevier. 1995: 1447–1540 [2021-09-29]. ISBN 9780444823465. （原始内容存档于2021-04-22）.