孫道強 劉永梅 王文虎 危 星 袁日強 劉淼淼

（1.平頂山學(xué)院計算機學(xué)院 平頂山 467000）（2.平頂山學(xué)院財務(wù)處 平頂山 467000）

1 引言

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

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

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

2 符號和定義

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

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

同樣地，定義 T1的 w_veven權(quán)重（記為w_veven(T1)）如下：若T1是一個單獨的加權(quán)頂點，那么w_veven(T1)等于vk的偶權(quán)重；否則，Pn=(V(Pn)，E(Pn);f，g)等于 SE(T1)中每個頂點的偶權(quán)重；SO(T1)中每個葉子（非葉子）頂點的奇權(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ù)，分別記做F(G;f，g，vk，odd)，F(xiàn)(G;f，g，vk，even)，為

同樣地，對于加權(quán)圖G的一棵BC-子樹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)中頂點的偶權(quán)重和T2的所有邊的權(quán)重的乘積。定義加權(quán)圖G的BC-子樹生成函數(shù)，記作

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

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

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

引理 1［9］：由上述定義和符號，可得

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

當l為偶數(shù)時

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

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

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

其中vl為Ts的某一個葉子頂點，且Vo(Ts)={v|v∈V(Ts)∧dTs(v，vl)≡1(mod 2)} ， Ve(Ts)={v|v∈V(Ts)∧dTs(v，vl)≡0(mod 2)}。

接下來研究書本圖的BC-子樹問題，書本圖的定義如下。

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

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

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

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

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

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

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

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

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

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

對于第2）種情況，將它的BC-子樹也分為四類：

（4）含u點但不含v點的BC-子樹；

（5）含v點但不含u點的BC-子樹；

（6）u和v兩點都不含的BC-子樹；

（7）u和v兩點都含的BC-子樹；

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

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

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

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

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

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

4 書本圖的BC-子樹密度

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

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

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

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

5 結(jié)語

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