跳转到内容

凯莱图

维基百科,自由的百科全书
在两个生成元ab上的自由群的凯莱图

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

定义

[编辑]

假设,而G的生成集。凯莱图,是如下构造的著色的有向图

  • 的每个元素对应一个顶点。换言之,图的顶点集合视为与等同;
  • 中每个生成元,对应一种颜色
  • 对于任何,画一条由元素有向边,染成色。换言之,边集合由形如的有序对构成,边的颜色由确定。

在几何群论中,集合通常取为有限、对称(即满足),并且不包含这个群的单位元。在这种情况下,凯莱图是简单无向图:它的边没有方向(由对称性),并且不包含自环(因为)。

例子

[编辑]
  • 假设是无限循环群(即整数的加法群),而集合由标准生成元和它的逆元(用加法符号为)构成,则它的凯莱图是无穷链英语Path graph
  • 类似地,如果循环群(模的加法群),而仍由的标准生成元与逆元构成,则凯莱图是环图
  • 群的直积的凯莱图(新生成集取为原生成集之笛卡尔积),是对应的凯莱图的笛卡尔积英语Cartesian product of graphs。因此阿贝尔群,关于四个元素组成的生成集的凯莱图,是平面上的无穷网格,而带有类似的生成集的直积的凯莱图,是环面上的有限网格。
  • 二面体群群展示左图是关于两个生成元的凯莱图,其中红色箭头表示左乘元素(顺时针旋转)。而因为元素(左右反射)自反,所以表示左乘元素的蓝色线是无方向的,故左图混合了有向边与无向边:它有个顶点、有向边条无向边。
    二面体群关于两个生成元的凯莱图。
    关于两个自反生成元的凯莱图
    同一个群,亦可画出不同的凯莱图,如右图。仍表示左右反射,而则是关于主对角线的反射,以粉红色线表示。由于两个反射皆自反,右边的凯莱图完全无向。对应的群展示是
  • 条目开头的图,是两个生成元上的自由群,关于生成集合的凯莱图,而正中央的黑点,是单位元。沿著边向右走表示右乘,而沿著边向上走表示乘以。因为自由群没有关系,它的凯莱图中没有。这个凯莱图是证明巴拿赫-塔斯基悖论的关键。
  • 右边有离散海森堡群
    海森堡群的一部分(颜色仅为方便看清分层)

的凯莱图。所用的三个生成元,分别对应。其关系为,亦可从图中看出。本群为非交换无穷群。虽然是三维空间,其凯莱图的增长英语Growth rate (group theory)却是阶的。[来源请求]

特征

[编辑]

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

(无标记又无着色)有向图是群的某个凯莱图,当且仅当可作为图自同构(就是要保存边的集合)作用在上,且该作用简单传递。[1]

要从一个凯莱图找回群和生成集,先选择一个顶点,标上群的单位元。接著,对的每个顶点中有唯一元素将变换到,于是可以在处标记该唯一元素。最后要确定的哪个生成集,产生凯莱图,而所求的就是毗连的顶点标记的集合。生成集合是有限(这是凯莱图的共同假定)当且仅当这个图是局部有限的(就是说每个顶点仅毗连于有限多条边)。

基本性质

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

Schreier陪集图

[编辑]

如果转而把顶点作为固定子群的右陪集,就得到了一个有关的构造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).