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

龔和林，王　偉

(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)生重邊……