龔和林，王　偉

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

?

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

龔和林1*，王偉1，2

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

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

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

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

對(duì)平面圖G,稱G是反射對(duì)稱,如果存在某直線l(對(duì)稱軸)使G在關(guān)于l反射作用下分為互為鏡像的兩個(gè)部分.有關(guān)反射對(duì)稱平面圖的結(jié)果,可參見文獻(xiàn)[3-6].設(shè)G是一個(gè)關(guān)于軸l反射對(duì)稱的平面圖,且G存在一個(gè)頂點(diǎn)劃分{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ǔ)對(duì)子圖GC的每條邊插入一個(gè)新頂點(diǎn)(邊剖分運(yùn)算)后得到的圖,G2為在圖GR基礎(chǔ)上對(duì)VC中頂點(diǎn)黏合成一個(gè)頂點(diǎn)u后得到的圖(刪去產(chǎn)生的自環(huán),可能產(chǎn)生重邊).Ciucu等[4]證明了

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

(1)

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

定義1[7]稱連通圖G具有對(duì)合性質(zhì)的,也說G是左右對(duì)稱的,如果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中頂點(diǎn)的邊集合.

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

對(duì)左右對(duì)稱圖G,記G1為在圖GL基礎(chǔ)上對(duì)子圖GC的每條邊插入一新頂點(diǎn)(邊剖分運(yùn)算)后得到的圖,當(dāng)E(GC)=?,規(guī)定G1=GL;G2為在圖GR基礎(chǔ)上將VC中頂點(diǎn)黏合成一個(gè)頂點(diǎn)u后得到的圖(刪去產(chǎn)生的自環(huán)).對(duì)左右對(duì)稱圖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上用一對(duì)平行邊連接u與yi.在本文中將證明

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

(2)

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

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

(3)

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

給定一個(gè)賦權(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)，進(jìn)一步,G的生成樹權(quán)和定義為τ(G)=∑T∈T(G)W(T).特別地,賦權(quán)圖G具有對(duì)合映射f,意味著f保持權(quán)不變,即 ?e∈E(G),ω(e)=ω(f(e)).

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

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

(4)

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

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

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

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

1幾個(gè)預(yù)備引理

設(shè)G是一個(gè)圖,e是G的一條非環(huán)邊且u和v為e的兩個(gè)端點(diǎn).記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是一個(gè)連通圖,Ge是在G基礎(chǔ)上對(duì)非環(huán)邊e作雙剖分變換得到的圖，則t(Ge)=4t(G).

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

引理2[1,8](矩陣-樹定理) 設(shè)G是一個(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是文獻(xiàn)[7]中定理 2.1 的特例,區(qū)別于文獻(xiàn)[9] 中的圖譜方法[9],用矩陣-樹定理給出一種簡潔證明.

引理3[7]如果 G=(V(G),E(G)) 是左右對(duì)稱圖,且 |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)) 為對(duì)角元素的對(duì)角矩陣,DC為以 VC中頂點(diǎn)度 dG(v1),dG(v2),…,dG(vn) 為對(duì)角元素的對(duì)角矩陣.容易看出,

Lv(G)=

(DL=DR,AL=AR).

注意到

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

其中,u 是 G2中由 VC中頂點(diǎn)黏和得到的新頂點(diǎn),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對(duì)稱無權(quán)圖生成樹數(shù)目的兩個(gè)拆分定理

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

定理2設(shè)G 是一個(gè)左右對(duì)稱圖.若 |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 是一個(gè)關(guān)于軸 l 反射對(duì)稱平面圖,且 ω(G) 為 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 是反射對(duì)稱的平面圖,合理排序 VC上的頂點(diǎn)可滿足要求).注意到 n-1-|E(GC)|=n-1-m=ω(G).因此,根據(jù)定理 2 得 t(G)=2ω(G)t(G1)t(G2).

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

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

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

參考文獻(xiàn)：

[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

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

*通信作者：helingong@126.com

中圖分類號(hào):O 157.5

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

文章編號(hào)：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)對(duì)稱無權(quán)圖生成樹數(shù)目的拆分定理[J].廈門大學(xué)學(xué)報(bào)(自然科學(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)