凯莱图

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

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

定义

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

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

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

例子

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

  

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

  

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

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

  

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

$$\left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}$$

的凯莱图。所用的三个生成元$X,Y,Z$，分别对应$(x,y,z)=(1,0,0),\ (0,1,0),\ (0,0,1)$。其关系为$Z=XYX^{-1}Y^{-1},\ XZ=ZX,\ YZ=ZY$，亦可从图中看出。本群为非交换无穷群。虽然是三维空间，其凯莱图的增长却是$4$阶的。

特征

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

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

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

基本性质

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

Schreier陪集图

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

与群论的关系

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

参见

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