王 健

(浙江外國語學(xué)院理工學(xué)院，浙江杭州310012)

關(guān)于圖的臨界群的秩

王 健

(浙江外國語學(xué)院理工學(xué)院，浙江杭州310012)

圖的臨界群決定了其支撐樹的內(nèi)部結(jié)構(gòu)，因而支撐樹的很多性質(zhì)可以通過研究圖的臨界群得到．作為頂點數(shù)有限的圖，其臨界群是一個有限生成的群．該群的生成元的數(shù)目顯示了群結(jié)構(gòu)的復(fù)雜性．所需要用到的生成元的最小數(shù)目即為臨界群的秩．在不引起混淆的情況下，臨界群的秩也被稱為圖的秩．秩越小，臨界群的需要的生成元的數(shù)目也就越小，研究的難度也相應(yīng)越小．有一部分圖的秩的下界可以通過計算直接得到．

臨界群;秩;生成元

1 引言

本文涉及到的圖是指頂點數(shù)目有限的簡單無向圖，允許有重邊，但是不能有環(huán)(即兩個端點是同一個頂點的邊)．臨界群是建立在圖上的有限可交換群，它可以由有限個元來生成，也可以由圖的拉普拉斯(Laplacian)矩陣確定．圖的拉普拉斯矩陣定義如下：

其中d(u)表示頂點u的度數(shù)，u～v表示兩頂點相連，u?v表示兩頂點不相連．L(G)的余核有如下形式：

其中n表示圖G的頂點的數(shù)目，C(G)表示圖G的臨界群，它的階數(shù)恰好就是圖G的支撐樹的數(shù)目．臨界群在參考文獻(xiàn)［1-3］中有更為詳細(xì)的描述．

行列式等于±1的整數(shù)矩陣稱為幺模矩陣．如果對于整數(shù)矩陣A和B，存在幺模矩陣P和Q，使得B=PAQ，則稱A和B是幺模相抵的，記成A～B．換句話說，若A和B是幺模相抵的矩陣，那么矩陣B可以經(jīng)由若干次的幺模變換最后變成A．幺模變換分為以下三種：

(1)交換某兩行(或列);

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

(3)某一行(或列)的整數(shù)倍加到另一行(或列)．

容易驗證，如果A～B，那么必定有coker(A)?coker(B)．從而我們可以通過幺模變換來尋找C(G)的生成元．

我們用r(G)來表示生成C(G)所需要的最少的生成元的數(shù)目，即為C(G)的秩［4］，在不引起混淆的情況下，簡記為r．將第i個位置上取值為1，其他取值為0的行向量(0，…，0，1，0，…，0)∈Zn記為xi．記X=用這樣的xi來表示C(G)的元素，由(1.2)可知，臨界群C(G)可由關(guān)系式L(G)X=0確定．在這個關(guān)系式中，用 j1，j2，…，jn表示 1，2，…，n 的一個排列，如果{xjk+1，xjk+2，…，xjn}能被表示成{xj1，xj2，…，xjk}的整系數(shù)線性組合的形式，那么顯然{xj1，xj2，…，xjk}是 C(G)的一組生成元．

一般的有限生成群在討論生成元時，是不包含零元的;但本文為了形式上的簡便，在討論的C(G)的生成元{xj1，xj2，…，xjk}(也稱為圖G的生成元)時是包含著零元的，所以會有

由簡單的群理論知識有以下定理：

定理1.1 一個群為循環(huán)群當(dāng)且僅當(dāng)其秩為1．

2 主要結(jié)論

用M表示一個k階的整數(shù)方陣，且令X1=(xj1，xj2，…，xjk)t，于是我們可以對L(G)X=0進(jìn)行化簡，得到一個新的關(guān)系式 MX1=0．考慮到{xj1，xj2，…，xjk}是包含零元的，或者說{xj1，xj2，…，xjk}是線性相關(guān)的，所以有以下引理．

引理2.1 方陣M的秩為k－1．

定理2.2 n階圖G有一組個數(shù)為k的生成元當(dāng)且僅當(dāng)圖G的拉普拉斯矩陣L(G)里有一個n－k階子行列式值為1或－1．

證明：只需要證明“G有一組個數(shù)為k的生成元”等價于“L(G)里有一個n－k階子矩陣為幺模矩陣”即可．

充分性：若L(G)有一個n－k階的子陣L0，其為幺模矩陣，那么顯然它的逆L－10也是幺模矩陣．令L(G)由定義可知，顯然A也是幺模矩陣．

由

可知

即

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

必要性：圖G有一組個數(shù)為 的生成元，不妨假設(shè)為{xj1，xj2，…，xjk}．

考慮到{xjk+1，xjk+2，…，xjn}能被表示成{xj1，xj2，…，xjk}的整系數(shù)線性組合的形式，將線性組合的系數(shù)排列成矩陣，記為R．那么就存在一個n－k行，k列的整數(shù)矩陣R，使得

從而有

從而必定存在n－k階幺模矩陣A，使得

從而L0=A為幺模矩陣．

推論2.3 圖G的秩為r當(dāng)且僅當(dāng)L(G)中存在的最大的子幺模矩陣的階數(shù)為n－r－1．

由L(G)的定義可以知道，當(dāng)兩個頂點之間有連邊的時候，L(G)中就會出現(xiàn)－1，這就是一階的幺模矩陣，所以它一定包含幺模子矩陣．

推論2.4 圖T為樹當(dāng)且僅當(dāng)則T的秩為0．

任意兩個頂點之間都可以找到若干條邊將它們連起來的圖稱為連通圖．不包含圈的連通圖稱為樹．

定義2.5 設(shè)圖G1(V1，E1)和G2(V2，E2)為兩個互不相交的圖，定義它們的笛卡爾乘積圖G1×G2如下：

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

(2)頂點(u1，v1)和(u2，v2)之間存在連邊當(dāng)且僅當(dāng)以下兩個條件之一成立：

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

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

在此定義之上，如果用n1，n2來分別表示G1和G2的頂點數(shù)目，e1，e2分別表示G1和G2的邊數(shù)，容易發(fā)現(xiàn)，G1×G2共有n1n2個頂點，n1e2+n2e1條邊．

可以這樣來理解G1×G2：將G2的每一個頂點都替換成G1;G2的兩個頂點之間原來如果存在邊相連，那么現(xiàn)在就用n1條邊，分別連接兩個G1之間對應(yīng)的頂點，這兩個G1就是替換了兩個頂點而來的．

接下去要討論的是笛卡爾乘積圖的秩：

定理2.6 設(shè)圖G1有n1個頂點，有一組個數(shù)為k的生成元，圖G2有n2個頂點，則圖G1×G2有一組個數(shù)為kn2的生成元．

證明 G1有一組個數(shù)為 的生成元，由定理2.2知，L(G1)存在一個n1－k階的子幺模矩陣L0．此時考慮L(G1×G2)，它有一個n2(n1－k)階的子矩陣L0×In2為幺模矩陣，于是再次應(yīng)用定理2.2，圖G1×G2有一組個數(shù)為n1n2－n2(n1－k)=kn2的生成元．

推論2.7 圖T是樹，P2是長為1的路．笛卡爾乘積圖T×P2的臨界群是循環(huán)群．

證明 顯然，樹T的生成元只需要一個，圖P2有兩個頂點，由定理2.6，圖T×P2有一組個數(shù)為2的生成元，所以它的秩只能為0或1．若它的秩為0，由推論2.4，T×P2是樹，不可能;所以它的秩必為1．由定理1.1，圖T×P2的臨界群一定是循環(huán)群．

［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－)，男，浙江杭州人，浙江外國語學(xué)院理工學(xué)院講師，理學(xué)博士．