有關(guān)對稱無權(quán)圖生成樹數(shù)目的拆分定理

龔和林，王　偉

(1.廈門大學(xué)數(shù)學(xué)科學(xué)學(xué)院,福建廈門361005；2.塔里木大學(xué)信息工程學(xué)院,新疆阿拉爾843300)

?

有關(guān)對稱無權(quán)圖生成樹數(shù)目的拆分定理

龔和林1*，王偉1，2

(1.廈門大學(xué)數(shù)學(xué)科學(xué)學(xué)院,福建廈門361005；2.塔里木大學(xué)信息工程學(xué)院,新疆阿拉爾843300)

摘要：設(shè)G是一個對稱平面圖.Ciucu等證明了一個有關(guān)G的生成樹數(shù)目的拆分定理,也就是G的生成樹數(shù)目可用兩個小圖的生成樹數(shù)目乘積來表示.在此基礎(chǔ)上，提出了一種圖變換,給出了圖在這種變換下生成樹數(shù)目的變化關(guān)系式,再結(jié)合矩陣-樹定理給出了該拆分定理的一個簡短證明.同時,受 Zhang等證明的賦權(quán)圖生成樹權(quán)和的拆分定理啟發(fā),還給出了一個關(guān)于對稱無權(quán)圖生成樹數(shù)目的等價拆分公式.

關(guān)鍵詞：生成樹數(shù)目;矩陣-樹定理;對稱性;平面圖

給定圖G=(V(G),E(G)).若v∈V(G),記dG(v)為v在G中的度.若U?V(G),記G[U]為U的導(dǎo)出子圖.在頂點標(biāo)號下,連通無權(quán)圖G的不同生成樹的個數(shù)記為t(G).其他圖論術(shù)語及符號參考文獻[1-2].

對平面圖G,稱G是反射對稱,如果存在某直線l(對稱軸)使G在關(guān)于l反射作用下分為互為鏡像的兩個部分.有關(guān)反射對稱平面圖的結(jié)果,可參見文獻[3-6].設(shè)G是一個關(guān)于軸l反射對稱的平面圖,且G存在一個頂點劃分{VL,VC,VR},滿足V(G)=VL∪VC∪VR,{VL,VC,VR}兩兩不交,這里,VC={v1,v2,…,vn}在軸l上,VL和VR在軸l的左右兩側(cè),且VL和VR之間不存在跨過l的邊.記GL=G[VL∪VC],GR=G[VC∪VR],GC=G[VC],則GL?GR(同構(gòu)).定義G1為在圖GL基礎(chǔ)對子圖GC的每條邊插入一個新頂點(邊剖分運算)后得到的圖,G2為在圖GR基礎(chǔ)上對VC中頂點黏合成一個頂點u后得到的圖(刪去產(chǎn)生的自環(huán),可能產(chǎn)生重邊).Ciucu等[4]證明了

t(G)=2ω(G)t(G1)t(G2)，

(1)

這里,ω(G)為G中交于對稱軸l的有界面的個數(shù),見文獻[4]示例圖2(a).

定義1[7]稱連通圖G具有對合性質(zhì)的,也說G是左右對稱的,如果G滿足下列條件:

(i)V(G)=VL∪VC∪VR,這里,VL,VC,VR非空且兩兩不交,VL,VR在VC的左右兩側(cè).

(ii) 記GL=G[VL∪VC],GR=G[VC∪VR],GC=G[VC].則E(G)=E(GL)∪E(GC)∪E(GR)∪E(VL,VR),這里,E(VL,VR)為連接VL與VR中頂點的邊集合.

(iii) 如果VL={x1,x2,…,xs},VR={y1,y2,…,ys},VC={v1,v2,…,vn},那么G存在一個自同構(gòu)映射f,使得f(xi)=yi,f(yi)=xi(i∈{1,2,…,s}),f(v)=v(v∈VC).這樣的映射f稱為G的對合映射.也就是說,f∈Aut(G)(G的自同構(gòu)群),且f≠id(恒同映射),但f2=id.

對左右對稱圖G,記G1為在圖GL基礎(chǔ)上對子圖GC的每條邊插入一新頂點(邊剖分運算)后得到的圖,當(dāng)E(GC)=?,規(guī)定G1=GL;G2為在圖GR基礎(chǔ)上將VC中頂點黏合成一個頂點u后得到的圖(刪去產(chǎn)生的自環(huán)).對左右對稱圖G,在滿足條件E(VL,VR)?{xiyi∈E(G)，i=1,2,…,s}下,假設(shè)|VC|=n≥1,|E(GC)|=m≥0,且G3是由G2添加一些平行邊得到的圖:只要ei=xiyi∈E(VL,VR),就在G2上用一對平行邊連接u與yi.在本文中將證明

t(G)=2n-m-1t(G1)t(G3).

(2)

特別地,當(dāng)E(VL,VR)=? 時,G3=G2,因此,式(2) 即為

t(G)=2n-m-1t(G1)t(G2).

(3)

下面將說明式(3)可直接推出式(1).

給定一個賦權(quán)圖 G,用 ω(e) 表示 e 的權(quán),T(G) 表示G的基礎(chǔ)無權(quán)圖所有生成樹組成的集合.若T∈T(G),則T的權(quán)記為W(T)=∏e∈E(T)ω(e)，進一步,G的生成樹權(quán)和定義為τ(G)=∑T∈T(G)W(T).特別地,賦權(quán)圖G具有對合映射f,意味著f保持權(quán)不變,即 ?e∈E(G),ω(e)=ω(f(e)).

在上述權(quán)和的定義和特定賦權(quán)下,Zhang等[7]證明了下面定理.

定理1[7]設(shè)G是一個具有對合映射 f 的賦權(quán)圖.若 |VC|=n≥1,則

(4)

(ii) 若 xiyj,xjyi(i≠j.對合映射 f 保證這兩條邊必須成對出現(xiàn),且它們權(quán)一樣,記為 α) 是 G 的一對交錯邊,則 xi和 xj增加一條邊 xixj(允許重邊),并賦權(quán) α.

(i) 在 GR基礎(chǔ)上將頂點子集 VC頂點黏合成一個頂點 u (去掉產(chǎn)生的環(huán));

(ii) 只要邊 xiyj∈E(VL,VR) (i 和 j 可相等或也可不等),且 ω(xiyj)=β,則增加邊 uyj,并賦權(quán) 2β；

(iii) 若 xiyj,xjyi(i≠j.對合映射 f 保證這兩條邊必須成對出現(xiàn),且它們權(quán)一樣,記為 γ) 是 G 的一對交錯邊,則 yi和 yj增加一條邊 yiyj(允許重邊),并賦負權(quán)-γ.

1幾個預(yù)備引理

設(shè)G是一個圖,e是G的一條非環(huán)邊且u和v為e的兩個端點.記G-e為圖G刪去邊e后得到的子圖,G/e為圖G的收縮邊e后得到的圖.此外,從G到Ge的變換過程稱為G的關(guān)于e的雙剖分變換,這里Ge是在圖G的基礎(chǔ)上把邊e替換為兩條內(nèi)不交的長為 2 的路得到的圖，如圖1表示.

圖1　邊e的雙剖分變換Fig.1Double subdivision on the edge e

引理1設(shè)G是一個連通圖,Ge是在G基礎(chǔ)上對非環(huán)邊e作雙剖分變換得到的圖，則t(Ge)=4t(G).

證明因為Ge中邊導(dǎo)出子圖G[e1,e2,e3,e4] 恰有 4 棵不同的生成樹,也恰有 4 棵含 2 個分支的生成森林 (u和v在不同的連通分支),所以G的 1 棵(含或不含e) 的生成樹可構(gòu)造Ge的 4 棵不同生成樹.

引理2[1,8](矩陣-樹定理) 設(shè)G是一個連通圖，記L(G)=D(G)-A(G),其中,D(G)為G 的度矩陣,A(G) 為 G 的鄰接矩陣，則t(G)=det(Li(G)).這里,Li(G) 為 L(G) 刪去第 i 行第 i 列所得的子矩陣.

引理3是文獻[7]中定理 2.1 的特例,區(qū)別于文獻[9] 中的圖譜方法[9],用矩陣-樹定理給出一種簡潔證明.

引理3[7]如果 G=(V(G),E(G)) 是左右對稱圖,且 |VC|=n≥1,E(GC)=E(VL,VR)=?,那么

t(G)=2n-1t(G1)t(G2)=

2n-1t(GL)t(G2)(G1=GL).

證明用AL(或AR) 表示G[VL] (或G[VR]) 的鄰接矩陣,B表示 VL和 VC的關(guān)聯(lián)矩陣,DL(或DR) 分別為以 dG(x1),dG(x2),…,dG(xs) (或 dG(y1),dG(y2),…,dG(ys)) 為對角元素的對角矩陣,DC為以 VC中頂點度 dG(v1),dG(v2),…,dG(vn) 為對角元素的對角矩陣.容易看出,

Lv(G)=

(DL=DR,AL=AR).

注意到

t(G1)=det(Lu(G1))=

其中,u 是 G2中由 VC中頂點黏和得到的新頂點,du是 u 在 G2中的度,且 u 與 VR的鄰接關(guān)系為向量X∈R1×|VR|.顯然,t(G2)=det(Lu(G2))=det(DR-AR).因此,

t(G)=det(Lv(G))=

2n-1det(Lv(G1))det(Lu(G2))=

2n-1t(G1)t(G2).

2對稱無權(quán)圖生成樹數(shù)目的兩個拆分定理

對具有對合性質(zhì)的賦權(quán)圖,Zhang等[4]給出了一個有關(guān)生成樹權(quán)和的拆分定理.受之啟發(fā),下面將證明公式 (2) (見定理 3).為清晰起見,逐步歸納證明,盡管定理 3 蘊含定理 2.

定理2設(shè)G 是一個左右對稱圖.若 |VC|=n≥1,|E(GC)|=m≥0,E(VL,VR)=?，則

t(G)=2n-m-1t(G1)t(G2).

2n-k-3t((Ge)1)t((Ge)2)=

2n-(k+1)-1t(G1)t(G2).

推論1[9]設(shè) G 是一個關(guān)于軸 l 反射對稱平面圖,且 ω(G) 為 G 中交于軸的有界面的個數(shù).若 |VC|=n≥1,E(VL,VR)=?，則 t(G)=2ω(G)t(G1)t(G2).

證明不失一般性,不妨設(shè) v1,v2,…,vn自上而下排列在軸 l 上,且邊集 E(GC)?{vivi+1，i=1,2,…,n-1}(既然 G 是反射對稱的平面圖,合理排序 VC上的頂點可滿足要求).注意到 n-1-|E(GC)|=n-1-m=ω(G).因此,根據(jù)定理 2 得 t(G)=2ω(G)t(G1)t(G2).

定理3設(shè) G 是一個左右對稱圖.若 |VC|=n≥1,|E(GC)|=m≥0,且 E(VL,VR)={e1,e2,…,ek}?{xiyi∈E(G)，i=1,2,…,s} (無交錯邊對),則

t(G)=2n-m-1t(G1)t(G3).

這里,G3由 G2添加一些平行邊得到:只要 ei=xiyi∈E(VL,VR),就在 G2上用一對平行邊連接 u 與 yi.

參考文獻：

[1]BIGGSNL.Algebraicgraphtheory[M].2nded.Cambridge:CambridgeUniversityPress,1993:9-33.

[2]BONDYJA,MURTYUSR.Graphtheorywithapplications[M].NewYork:Elsevier,1976:7,218-219.

[3]CIUCUM.Enumerationofperfectmatchingsingraphswithreflectivesymmetry[J].JCombinTheorySerA,1997,77:67-97.

[4]CIUCUM,YANW,ZHANGF.Thenumberofspanningtreesofplanegraphswithreflectivesymmetry[J].JCombinTheorySerA,2005,112:105-116.

[5]JINX,ZHANGF.Alexanderpolynomialforevengraphswithreflectivesymmetry[J].JKnotTheorRamif,2008,17:1241-1256.

[6]NEGAMIS.Polynomialinvariantofgraphs[J].TranAmerMathSoc,1987,209:601-622.

[7]ZHANGF,YANW.Enumerationofspanningtreesofgraphswithaninvolution[J].JCombinTheorySerA,2009,116:650-662.

[8]KIRCHHOFFG.überdieaufl?sungdergleichungen,aufwelchemanbeideruntersuchungderlinearenverteilunggalvanischerstr?megeführtwird[J].AnnPhysChem,1847,72:497-508.

doi：10.6043/j.issn.0438-0479.201512026

收稿日期：2015-12-27錄用日期：2016-05-05

基金項目：國家自然科學(xué)基金(11271307,11561058)；廣西高校數(shù)學(xué)與統(tǒng)計模型重點實驗室開放課題

*通信作者：helingong@126.com

中圖分類號:O 157.5

文獻標(biāo)志碼：A

文章編號：0438-0479(2016)04-0554-04

The Factorization Theorems on the Number of Spanning Trees of Graphs with Some Symmetry

GONG Helin1*,WANG Wei1，2

(1.School of Mathematical Sciences,Xiamen University,Xiamen 361005，China；2.College of Information Engineering,Tarim University,Alar 843300，China)

Abstract:Let G be a plane graph with reflective symmetry.Ciucu,et al, proved a factorization theorem on the number of spanning trees of G.That is,the number of spanning treesof G can be expressed in terms of the product of the number of spanning trees of two smaller graphs.In this paper,we introduce a graph transformation and discuss its effect on the number of spanning trees,then by the matrix-tree theorem we give a short proof of above-mentioned factorization theorem.Motivated by a factorization theorem on the sum of weights of spanning trees of weighted graphs with some symmetry in Zhang et al,we further provide an equivalent factorization formula on the number of spanning trees of unweighted graphs with some symmetry.

Key words:spanning trees number;matrix-tree theorem;symmetry;plane graph

引文格式：龔和林，王偉.有關(guān)對稱無權(quán)圖生成樹數(shù)目的拆分定理[J].廈門大學(xué)學(xué)報(自然科學(xué)版)，2016,55(4)：554-557.

Citation：GONG H L,WANG W．The factorization theorems on the number of spanning trees of graphs with some symmetry[J].Journal of Xiamen University(Natural Science)，2016,55(4)：554-557．(in Chinese)