Cayley 图

凯莱图
术语名称	凯莱图
英语名称	Cayley graph
别名	Cayley color graph, Cayley diagram, group diagram

凯莱图(Cayley graph / Cayley diagram)是一种展示群结构的图表，将有限群中全体元素在与群生成元运算中的关系展示出来，从而抽象地刻画出群的结构。从凯莱图中可以比较容易地发现元素个数较少的群的一些性质。

凯莱图由于涉及给每个生成元分配颜色，一般仅用于有限生成群。

描述

Cayley 图是用于描述群的图表，图表内容是一张边着色的有向图。对群 [math]\displaystyle{ G }[/math] ，其 Cayley 图 [math]\displaystyle{ \Gamma=\langle G, S\rangle }[/math] 满足：

顶点集就是群的集合： [math]\displaystyle{ V(\Gamma)=G }[/math] 。
边集中每条边是有向、有颜色的边，所有有向边及其颜色的有序对构成的集合为 [math]\displaystyle{ \{\langle\langle g, gs \rangle, c_s\rangle\mid g\in G, s\in S \} }[/math] 。其中， [math]\displaystyle{ S }[/math] 是 [math]\displaystyle{ G }[/math] 的生成集，且其中每个生成元 [math]\displaystyle{ s }[/math] 都有一种被指派的颜色 [math]\displaystyle{ c_s }[/math] 。

一般假定群 [math]\displaystyle{ G }[/math] 是有限生成群，或者说生成集 [math]\displaystyle{ S }[/math] 是有限集。

特别地，在绘图时，如果生成集中存在二阶元，会在两个结点间产生同色反向的两条边，一般将其表示为一条无向边。

Cayley 图不仅取决于群本身，还一定程度上取决于生成元的选取。
图中两结点间的路径，可以确定两个元素的运算关系，通过与生成元如何运算可以得到生成元。而图中的环则表达了生成元间可以经什么样的运算得到幺元。
选择 [math]\displaystyle{ S }[/math] 中的一些生成元，从 Cayley 图中去除它们所染色的边，会使得 Cayley 图不再连通，每个连通分量都是 [math]\displaystyle{ S }[/math] 中剩余元素所生成子群的一个陪集。