書(shū)本圖的BC-子樹(shù)計(jì)數(shù)及漸進(jìn)密度特性分析?

孫道強(qiáng) 劉永梅 王文虎 危 星 袁日強(qiáng) 劉淼淼

（1.平頂山學(xué)院計(jì)算機(jī)學(xué)院 平頂山 467000）（2.平頂山學(xué)院財(cái)務(wù)處 平頂山 467000）

1 引言

圖的結(jié)構(gòu)及相關(guān)拓?fù)鋮?shù)的研究具有重要的理論意義和應(yīng)用背景［1～4］，比如，網(wǎng)絡(luò)特性的分析、化合物同分異構(gòu)體的分辨、分子的物理化學(xué)性質(zhì)的預(yù)測(cè)、活性影響的定量研究、材料和藥物合成。據(jù)不完全統(tǒng)計(jì)，目前大約有四百多項(xiàng)拓?fù)渲笜?biāo)。比如，距離型的 Wiener指標(biāo)［5～6］、Harary 指標(biāo)［7］，結(jié)構(gòu)型的子樹(shù)數(shù)指標(biāo)［8］（即，一個(gè)圖的所有非空子樹(shù)的個(gè)數(shù)）、BC-子樹(shù)數(shù)指標(biāo)［9］（即，一個(gè)圖的所有BC-子樹(shù)的個(gè)數(shù)，其中BC子樹(shù)至少含兩個(gè)頂點(diǎn)，且該子樹(shù)的任意兩片葉子的距離都是偶數(shù)的子樹(shù)）、原子鍵連通度指標(biāo)［10］（ABC）等。

相對(duì)于距離型的Wiener指標(biāo)，圖的結(jié)構(gòu)型BC-子樹(shù)數(shù)指標(biāo)相對(duì)較新，BC樹(shù)的概念是由著名圖論學(xué)家Harary等在研究圖的核的時(shí)候提出的［11］，該概念提出后，引起了計(jì)算機(jī)［12～13］、化學(xué)［14～15］等領(lǐng)域國(guó)內(nèi)外學(xué)者的關(guān)注和研究。

受文獻(xiàn)［9，16］中利用生成函數(shù)解決BC-子樹(shù)的方法的啟發(fā)，本文擬利用生成函數(shù)和結(jié)構(gòu)分析的方法，解決書(shū)本圖Bn，2(n≥2)的BC-子樹(shù)生成函數(shù)，并利用邊生成函數(shù)分析它的BC-子樹(shù)密度漸進(jìn)特性。

2 符號(hào)和定義

令 G=(V(G)，E(G);f，g)是頂點(diǎn)集 ||V(G)=n ，邊集 ||E(G)=m，頂點(diǎn)和邊生成函數(shù)分別為 f，g一個(gè)加權(quán)圖。G的非空無(wú)環(huán)的子結(jié)構(gòu)叫做G的子樹(shù)；若G的一棵子樹(shù)T同時(shí)滿足如下定義：含至少兩個(gè)頂點(diǎn)，且它的任意兩片葉間的距離均為偶數(shù)，那么T也被叫做G的一棵BC-子樹(shù)。若無(wú)特殊聲明，文中我們規(guī)定 f:V(G)→?×?，g:E(G)→?，?為實(shí)數(shù)。記G-X為G的刪除集合X后的圖。

記L(G)為G的葉子集合，記SBC(G)為G的所有BC-子樹(shù)的集合，記S(G;v)為G的含頂點(diǎn)v的子樹(shù)集合。對(duì)于任一個(gè)頂點(diǎn)vk和一個(gè)子樹(shù)T1∈S(G;vk)，定義 T1的 w_vodd權(quán)重（記為w_vodd(T1)）如下：若T1是一個(gè)單獨(dú)的加權(quán)頂點(diǎn)，那么w_vodd(T1)等于vk的奇權(quán)重；否則，w_vodd(T1)等于SO(T1)中每個(gè)頂點(diǎn)的偶權(quán)重，SE(T1)中每個(gè)葉子（非子葉）頂點(diǎn)的奇權(quán)重（（1+奇權(quán)重）），以及T1中每條邊的權(quán)重的乘積。

同樣地，定義 T1的 w_veven權(quán)重（記為w_veven(T1)）如下：若T1是一個(gè)單獨(dú)的加權(quán)頂點(diǎn)，那么w_veven(T1)等于vk的偶權(quán)重；否則，Pn=(V(Pn)，E(Pn);f，g)等于 SE(T1)中每個(gè)頂點(diǎn)的偶權(quán)重；SO(T1)中每個(gè)葉子（非葉子）頂點(diǎn)的奇權(quán)重（（1+奇權(quán)重）），以及T1中的每條邊的權(quán)重的乘積。這里

SO(T1)={v|v∈V(T1)∧dT1(v，vk)≡1(mod 2)}

SE(T1)={v|v∈V(T1)∧dT1(v，vk)≡0(mod 2)}。

S(G;vk)的子樹(shù)的奇，偶生成函數(shù)，分別記做F(G;f，g，vk，odd)，F(xiàn)(G;f，g，vk，even)，為

同樣地，對(duì)于加權(quán)圖G的一棵BC-子樹(shù)T2，定義

BES(T2)={v|v∈V(T2)∧dT2(v，vl)≡0(mod 2)}

和

BOS(T2)={v|v∈V(T2)∧dT2(v，vl)=1(mod 2)}

其中vl∈L(T2)。定義T2的BC-權(quán)重wbc(T2)，為BES(T2)中頂點(diǎn)的偶權(quán)重和T2的所有邊的權(quán)重的乘積。定義加權(quán)圖G的BC-子樹(shù)生成函數(shù)，記作

由上面的符號(hào)定義，可知 ηBC(G)=F(G;(0，1)，1)為G的BC-子樹(shù)數(shù)。

為方便敘述，我們引入以下引理，令T=(V(T)，E(T);f，g)為n(n＞1)個(gè)頂點(diǎn)的加權(quán)樹(shù)，vi是T的一個(gè)頂點(diǎn)，u≠vi是T的葉子且e=(u，v)為對(duì)應(yīng)的懸掛邊。構(gòu)造加權(quán)樹(shù) T′=(V(T′)，E(T′);f′，g′)如下：V(T′)=V(T){u}，E(T′)=E(T){e}，且

對(duì)任意 vs∈V(T′) ，g′(e)=g(e)(e∈E(T′))，這里，f(v)o(f′(vs)o) 和 f(v)e(f′(vs)e) 分別代表頂點(diǎn)v(vs)的奇權(quán)重和偶權(quán)重。

引理 1［9］：由上述定義和符號(hào)，可得

引理2［9］：令T為一棵加權(quán)樹(shù)，u和v為它的兩個(gè)不同的頂點(diǎn)，記Puv=ux1x2…xl-1v為T(mén)的連接u和 v 的路徑，長(zhǎng)度為 l，此外，記 Tu， Tv， Txi(i=1，2，…l-1)為T(mén)的刪除路徑 Puv上的所有邊后含u， v， xi的加權(quán)圖。則當(dāng)l為奇數(shù)時(shí)

當(dāng)l為偶數(shù)時(shí)

這 里 f*(vˉ)o=F(Tvˉ;f， g;vˉ， odd) ，f*(vˉ)e=F(Tvˉ;f，g;vˉ，even)，對(duì)于 vˉ∈{u，v，xi(i=1，2，…，l-1)}。

由引理1和2，及BC-子樹(shù)的定義，對(duì)于樹(shù)T=(V(T)，E(T);f，g)的一棵子樹(shù) Ts，按照引理 1 的方式迭代的收縮加權(quán)樹(shù)T的葉子節(jié)點(diǎn)到子樹(shù)Ts的某個(gè)頂點(diǎn)，直到收縮為樹(shù)Ts為止，此時(shí)，我們得到一 棵 加 權(quán) 樹(shù)，其 中?？傻煤琓s的BC子樹(shù)的生成函數(shù)如下。

定理 1：令 Ts為加權(quán)樹(shù) T=(V(T)，E(T);f，g)的一棵子樹(shù)，加權(quán)樹(shù)為按引理1的方式迭代T的葉子節(jié)點(diǎn)變成的樹(shù)，則T的含子樹(shù)Ts的BC-子樹(shù)的生成函數(shù)為

其中vl為T(mén)s的某一個(gè)葉子頂點(diǎn)，且Vo(Ts)={v|v∈V(Ts)∧dTs(v，vl)≡1(mod 2)} ， Ve(Ts)={v|v∈V(Ts)∧dTs(v，vl)≡0(mod 2)}。

接下來(lái)研究書(shū)本圖的BC-子樹(shù)問(wèn)題，書(shū)本圖的定義如下。

圖1 書(shū)本圖 Bn，2(n≥2)

定義1：將長(zhǎng)度為3的n條路徑的首尾頂點(diǎn)用一條邊進(jìn)行連接，由此產(chǎn)生的圖我們稱之為書(shū)本圖，記為 Bn，2(n≥2)，如圖1所示，易知，n頁(yè)書(shū)本圖有2n+2個(gè)頂點(diǎn)和3n+1條邊。

3 書(shū)本圖 Bn，2(n≥2)的BC-子樹(shù)

定理 2：令 Bn，2=(V(Bn，2)，E(Bn，2);f，g) 為 n 頁(yè)加權(quán)書(shū)本圖（見(jiàn)定義2.4和圖1），頂點(diǎn)和邊的權(quán)重函 數(shù) 分 別 為 f(v)=(0 ，y)(v∈V(Bn，2)) 和 g(e)=z(e∈E(Bn，2))，則

證明：將 Bn，2的BC-子樹(shù)分為如下兩種情況。

1）含公共邊 (u，v)；

2）不含公共邊 (u，v)。

對(duì)于第1）種情況，根據(jù)BC-子樹(shù)的結(jié)構(gòu)特性，我們繼續(xù)將它分為三類。

對(duì)于類（2）的情況，根據(jù)定理1，可得其BC-子樹(shù)的生成函數(shù)為

同類（2）的情況一樣，可得類（3）對(duì)應(yīng)的BC-子樹(shù)生成函數(shù)為

對(duì)于第2）種情況，將它的BC-子樹(shù)也分為四類：

（4）含u點(diǎn)但不含v點(diǎn)的BC-子樹(shù)；

（5）含v點(diǎn)但不含u點(diǎn)的BC-子樹(shù)；

（6）u和v兩點(diǎn)都不含的BC-子樹(shù)；

（7）u和v兩點(diǎn)都含的BC-子樹(shù)；

由文獻(xiàn)［9］算法4可知類（4）和類（5）的BC-子樹(shù)生成函數(shù)

易知類（6）是n個(gè)路徑樹(shù)P2所對(duì)應(yīng)的BC-子樹(shù)生成函數(shù)，由文獻(xiàn)［9］可知，它的值為0。

類似于第1）種情況的證明，可得類（7）的BC-子樹(shù)生成函數(shù)為

綜合式（6）～（10），定理得證。

將權(quán)重函數(shù)y，z分別替換為1，可得

推論1：書(shū)本圖 Bn，2(n≥2)的BC-子樹(shù)數(shù)為

4 書(shū)本圖的BC-子樹(shù)密度

將頂點(diǎn)和邊的權(quán)重分別初始化為(0，1)和z，由定理2，可得書(shū)本圖Bn，2的BC-子樹(shù)邊生成函數(shù)為

根據(jù)BC-子樹(shù)密度的定義，可得書(shū)本圖Bn，2的BC-子樹(shù)密度為

觀察圖2可知，書(shū)本圖 Bn，2(n≤100)的書(shū)本圖Bn，2(n≤100)的BC子樹(shù)密度隨著n的增大不斷減小。

圖2 書(shū)本圖Bn，2(n≤100)的BC-子樹(shù)密度

5 結(jié)語(yǔ)

本文利用生成函數(shù)和結(jié)構(gòu)分析的方法，給出了書(shū)本圖Bn，2(n≥2)的BC-子樹(shù)生成函數(shù)，并簡(jiǎn)要分析了Bn，2(n≥2)的BC-子樹(shù)密度的漸進(jìn)特性，研究為探索復(fù)雜圈圖和分子的新的結(jié)構(gòu)特性提供了理論基礎(chǔ)。