王 健

(浙江外国语学院理工学院，浙江杭州310012)

关于图的临界群的秩

王 健

(浙江外国语学院理工学院，浙江杭州310012)

图的临界群决定了其支撑树的内部结构，因而支撑树的很多性质可以通过研究图的临界群得到．作为顶点数有限的图，其临界群是一个有限生成的群．该群的生成元的数目显示了群结构的复杂性．所需要用到的生成元的最小数目即为临界群的秩．在不引起混淆的情况下，临界群的秩也被称为图的秩．秩越小，临界群的需要的生成元的数目也就越小，研究的难度也相应越小．有一部分图的秩的下界可以通过计算直接得到．

临界群;秩;生成元

1 引言

本文涉及到的图是指顶点数目有限的简单无向图，允许有重边，但是不能有环(即两个端点是同一个顶点的边)．临界群是建立在图上的有限可交换群，它可以由有限个元来生成，也可以由图的拉普拉斯(Laplacian)矩阵确定．图的拉普拉斯矩阵定义如下：

其中d(u)表示顶点u的度数，u～v表示两顶点相连，u≁v表示两顶点不相连．L(G)的余核有如下形式：

其中n表示图G的顶点的数目，C(G)表示图G的临界群，它的阶数恰好就是图G的支撑树的数目．临界群在参考文献［1-3］中有更为详细的描述．

行列式等于±1的整数矩阵称为幺模矩阵．如果对于整数矩阵A和B，存在幺模矩阵P和Q，使得B=PAQ，则称A和B是幺模相抵的，记成A～B．换句话说，若A和B是幺模相抵的矩阵，那么矩阵B可以经由若干次的幺模变换最后变成A．幺模变换分为以下三种：

(1)交换某两……