徐尚进

(广西大学,广西 南宁 530004)

1 引言

图是比较容易被人们直观理解并也容易激发人们产生丰富想像的对象.而图论研究的图,通常是经过抽象以后仅剩下一些顶点和连接这些顶点的边的几何图形.本文所涉及的图则更为特殊,即有限简单无向图,其顶点个数有限且无自环,边不重且无向,并还具有某些对称性.由于图的这些对称性需要通过其全自同构群的某些传递性来描述,因此需要运用群及其作用的理论.这方面工作属于群与图研究领域,我们称之为“传递图”研究.

我们先回顾代数结构的自同构群.

设Ω∶={α1,α2,…,αn}是一个有限集,则Ω到自身的双射(也称为“置换”)的全体关于映射的乘法构成一个n！阶有限群, 称为n次对称群, 记作Sym(Ω).

进一步,若Ω不是一个普通集合,而是一个代数结构,比如Ω是一个偏序集,或者是一个群、一个环,则我们通常会重点考虑Sym(Ω)中保持Ω的代数结构关系的置换σ：

(1) 当Ω是偏序集时,σ要能保持Ω的序,即由αiαj有其中表示αi在σ作用下的象(下同);

(3) 当Ω是一个环时,σ要能同时保持Ω的加法和乘法, 即

Sym(Ω)中能保持上述代数结构关系的置换称为Ω的自同构.容易验证,Ω的全体自同构组成一个群,称为Ω的自同构群,记作Aut(Ω).显然有

1 ≤Aut(Ω) ≤Sym(Ω).

由于自同构触及Ω的代数结构,因此研究Aut(Ω)及其作用对于了解Ω本身结构是有效的.

有限简单图作为由有限的顶点集和有限的边集决定的组合结构,也同样可以定义它的自同构群,并通过自同构群来研究图本身的性质,特别是图的对称……