凯莱图

凯莱图（Cayley graph）也叫做凯莱着色图是编码离散群的图。它的定义是凯莱定理（以阿瑟·凯莱命名）所暗含的，并使用这个群的特定的通常有限的生成元集合。它是组合群论与几何群论的中心工具。

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

在几何群论中，集合${\displaystyle S}$，通常被假定为有限的、“对称的”也就是${\displaystyle S=S^{-<!--\; -\; -->1}}$，并且不包含这个群的单位元。在这种情况下，凯莱图是正常的图：它的边没有方向并且不包含环路。

群${\displaystyle G}$通过左乘作用在自身上（参见凯莱定理）。这个作用可以看作${\displaystyle G}$作用在它的凯莱图上。明显的，一个元素${\displaystyle h\in <!--\; \in \; -->G}$映射一个顶点${\displaystyle g\in <!--\; \in \; -->V(\mathrm{\Gamma <!--\; \Gamma \; -->})}$到顶点${\displaystyle hg\in <!--\; \in \; -->V(\mathrm{\Gamma <!--\; \Gamma \; -->})}$。凯莱图的边集合被这个作用所保存：边${\displaystyle (g,gs)}$变换成边${\displaystyle (hg,hgs)}$。任何群在自身上的左乘作用是简单传递的，特别是凯莱图是顶点传递的。这导致了凯莱图的下列特征：

要从一个凯莱图${\displaystyle \mathrm{\Gamma <!--\; \Gamma \; -->}=\mathrm{\Gamma <!--\; \Gamma \; -->}(G,S)}$恢复群${\displaystyle G}$和生成集${\displaystyle S}$，选择一个顶点${\displaystyle v_1\in <!--\; \in \; -->V(\mathrm{\Gamma <!--\; \Gamma \; -->})}$并标记上这个群的单位元。接着对每个${\displaystyle \mathrm{\Gamma <!--\; \Gamma \; -->}}$的顶点${\displaystyle v}$标记上变换${\displaystyle v_1}$到${\displaystyle v}$的${\displaystyle G}$的唯一元素。产生${\displaystyle \mathrm{\Gamma <!--\; \Gamma \; -->}}$为凯莱图的${\displaystyle G}$的生成元的集合${\displaystyle S}$是毗连到选择的顶点的顶点的标记的集合。生成集合是有限（这是凯莱图的共同假定）当且仅当这个图是局部有限的（就是说每个顶点毗连与有限多个边）。

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

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