書本圖的BC-子樹計數及漸進密度特性分析?

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

（1.平頂山學院計算機學院 平頂山 467000）（2.平頂山學院財務處 平頂山 467000）

1 引言

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

相對于距離型的Wiener指標，圖的結構型BC-子樹數指標相對較新，BC樹的概念是由著名圖論學家Harary等在研究圖的核的時候提出的［11］，該概念提出后，引起了計算機［12～13］、化學［14～15］等領域國內外學者的關注和研究。

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

2 符號和定義

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

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

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

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)的子樹的奇，偶生成函數，分別記做F(G;f，g，vk，odd)，F(G;f，g，vk，even)，為

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

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

為方便敘述，我們引入以下引理，令T=(V(T)，E(T);f，g)為n(n＞1)個頂點的加權樹，vi是T的一個頂點，u≠vi是T的葉子且e=(u，v)為對應的懸掛邊。構造加權樹 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)的奇權重和偶權重。

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

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

當l為偶數時

這 里 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 的方式迭代的收縮加權樹T的葉子節點到子樹Ts的某個頂點，直到收縮為樹Ts為止，此時，我們得到一 棵 加 權 樹，其 中?？傻煤琓s的BC子樹的生成函數如下。

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

其中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條路徑的首尾頂點用一條邊進行連接，由此產生的圖我們稱之為書本圖，記為 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 頁加權書本圖（見定義2.4和圖1），頂點和邊的權重函 數 分 別 為 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）種情況，根據BC-子樹的結構特性，我們繼續將它分為三類。

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

同類（2）的情況一樣，可得類（3）對應的BC-子樹生成函數為

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

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

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

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

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

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

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

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

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

將權重函數y，z分別替換為1，可得

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

4 書本圖的BC-子樹密度

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

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

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

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

5 結語

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