王 健

(浙江外国语学院理工学院，浙江杭州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)交换某两行(或列);

(2)某一行(或列)乘以－1;

(3)某一行(或列)的整数倍加到另一行(或列)．

容易验证，如果A～B，那么必定有coker(A)≅coker(B)．从而我们可以通过幺模变换来寻找C(G)的生成元．

我们用r(G)来表示生成C(G)所需要的最少的生成元的数目，即为C(G)的秩［4］，在不引起混淆的情况下，简记为r．将第i个位置上取值为1，其他取值为0的行向量(0，…，0，1，0，…，0)∈Zn记为xi．记X=用这样的xi来表示C(G)的元素，由(1.2)可知，临界群C(G)可由关系式L(G)X=0确定．在这个关系式中，用 j1，j2，…，jn表示 1，2，…，n 的一个排列，如果{xjk+1，xjk+2，…，xjn}能被表示成{xj1，xj2，…，xjk}的整系数线性组合的形式，那么显然{xj1，xj2，…，xjk}是 C(G)的一组生成元．

一般的有限生成群在讨论生成元时，是不包含零元的;但本文为了形式上的简便，在讨论的C(G)的生成元{xj1，xj2，…，xjk}(也称为图G的生成元)时是包含着零元的，所以会有

由简单的群理论知识有以下定理：

定理1.1 一个群为循环群当且仅当其秩为1．

2 主要结论

用M表示一个k阶的整数方阵，且令X1=(xj1，xj2，…，xjk)t，于是我们可以对L(G)X=0进行化简，得到一个新的关系式 MX1=0．考虑到{xj1，xj2，…，xjk}是包含零元的，或者说{xj1，xj2，…，xjk}是线性相关的，所以有以下引理．

引理2.1 方阵M的秩为k－1．

定理2.2 n阶图G有一组个数为k的生成元当且仅当图G的拉普拉斯矩阵L(G)里有一个n－k阶子行列式值为1或－1．

证明：只需要证明“G有一组个数为k的生成元”等价于“L(G)里有一个n－k阶子矩阵为幺模矩阵”即可．

充分性：若L(G)有一个n－k阶的子阵L0，其为幺模矩阵，那么显然它的逆L－10也是幺模矩阵．令L(G)由定义可知，显然A也是幺模矩阵．

由

可知

即

可知{xj1，xj2，…，xjk}是图G的一组生成元．

必要性：图G有一组个数为 的生成元，不妨假设为{xj1，xj2，…，xjk}．

考虑到{xjk+1，xjk+2，…，xjn}能被表示成{xj1，xj2，…，xjk}的整系数线性组合的形式，将线性组合的系数排列成矩阵，记为R．那么就存在一个n－k行，k列的整数矩阵R，使得

从而有

从而必定存在n－k阶幺模矩阵A，使得

从而L0=A为幺模矩阵．

推论2.3 图G的秩为r当且仅当L(G)中存在的最大的子幺模矩阵的阶数为n－r－1．

由L(G)的定义可以知道，当两个顶点之间有连边的时候，L(G)中就会出现－1，这就是一阶的幺模矩阵，所以它一定包含幺模子矩阵．

推论2.4 图T为树当且仅当则T的秩为0．

任意两个顶点之间都可以找到若干条边将它们连起来的图称为连通图．不包含圈的连通图称为树．

定义2.5 设图G1(V1，E1)和G2(V2，E2)为两个互不相交的图，定义它们的笛卡尔乘积图G1×G2如下：

(1)顶点集合 V1× V2={(ui，vj)|ui∈V1，vj∈V2};

(2)顶点(u1，v1)和(u2，v2)之间存在连边当且仅当以下两个条件之一成立：

①u1=u2且(v1，v2)是 G2的边;

②v1=v2且(u1，u2)是 G1的边．

在此定义之上，如果用n1，n2来分别表示G1和G2的顶点数目，e1，e2分别表示G1和G2的边数，容易发现，G1×G2共有n1n2个顶点，n1e2+n2e1条边．

可以这样来理解G1×G2：将G2的每一个顶点都替换成G1;G2的两个顶点之间原来如果存在边相连，那么现在就用n1条边，分别连接两个G1之间对应的顶点，这两个G1就是替换了两个顶点而来的．

接下去要讨论的是笛卡尔乘积图的秩：

定理2.6 设图G1有n1个顶点，有一组个数为k的生成元，图G2有n2个顶点，则图G1×G2有一组个数为kn2的生成元．

证明 G1有一组个数为 的生成元，由定理2.2知，L(G1)存在一个n1－k阶的子幺模矩阵L0．此时考虑L(G1×G2)，它有一个n2(n1－k)阶的子矩阵L0×In2为幺模矩阵，于是再次应用定理2.2，图G1×G2有一组个数为n1n2－n2(n1－k)=kn2的生成元．

推论2.7 图T是树，P2是长为1的路．笛卡尔乘积图T×P2的临界群是循环群．

证明 显然，树T的生成元只需要一个，图P2有两个顶点，由定理2.6，图T×P2有一组个数为2的生成元，所以它的秩只能为0或1．若它的秩为0，由推论2.4，T×P2是树，不可能;所以它的秩必为1．由定理1.1，图T×P2的临界群一定是循环群．

［1］Bacher R，De la Harpe P，Nagnibeda T．The lattices of integral flows and the lattices of integral cuts of a finite graph［J］．Bull Soc Math，1997，125：167-198．

［2］Cori R，Rossin D．On the sanpile group of the dual graph［J］．Europ J Combinatorics，2000，21(4)：447-459．

［3］Cori R，Le Borgne R．The sand-pile model and Tutte polynomials［J］．Advances in Applied Mathematics，2003，30(1-2)：44-52．

［4］Hou Y P．Graphs whose critical groups have larger rank［J］．Acta Mathematica Sinica，2011，27(9)：1663-1670．

On the Rank of the Critical Group

WANG Jian
(School of Science and Technology，Zhejiang International Studies University，Hangzhou 310012，China)

The construct of the spanning tree of a graph depends on the corresponding critical group，so many properties of the spanning tree can be learned by studying the critical group．For a finite graph，the critical group is finitely generated．The number of the generators shows the complexity of a group．The minimum number of the generators is called rank．The rank of a critical group sometimes is also considered as the rank of a graph．Usually，a less rank will lead to a easier research．Some lower bound of a graph’s rank is determined．

critical group;rank;generator

O175.5

A

2095－2074(2011)05－0096－03

2011－06－10

王健(1982－)，男，浙江杭州人，浙江外国语学院理工学院讲师，理学博士．