王 健

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

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

王 健

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

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

臨界群;秩;生成元

1 引言

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

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

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

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

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

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

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

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

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

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

由簡(jiǎn)單的群理論知識(shí)有以下定理：

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

2 主要結(jié)論

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

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

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

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

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

由

可知

即

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

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

考慮到{xjk+1，xjk+2，…，xjn}能被表示成{xj1，xj2，…，xjk}的整系數(shù)線性組合的形式，將線性組合的系數(shù)排列成矩陣，記為R．那么就存在一個(gè)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)兩個(gè)頂點(diǎn)之間有連邊的時(shí)候，L(G)中就會(huì)出現(xiàn)－1，這就是一階的幺模矩陣，所以它一定包含幺模子矩陣．

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

任意兩個(gè)頂點(diǎn)之間都可以找到若干條邊將它們連起來(lái)的圖稱為連通圖．不包含圈的連通圖稱為樹．

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

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

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

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

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

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

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

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

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

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

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

證明 顯然，樹T的生成元只需要一個(gè)，圖P2有兩個(gè)頂點(diǎn)，由定理2.6，圖T×P2有一組個(gè)數(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－)，男，浙江杭州人，浙江外國(guó)語(yǔ)學(xué)院理工學(xué)院講師，理學(xué)博士．