廣義書本圖的BC-子樹計數(shù)及漸近密度特性分析*

李笑笑， 靳夢源， 孫道強， 李 昊， 楊 雨②

(①平頂山學院軟件學院，467000，河南省平頂山市；②上海交通大學數(shù)學科學學院，200240，上海市)

0 引 言

圖的結(jié)構(gòu)和相關(guān)拓撲參數(shù)是眾多交叉領(lǐng)域?qū)W科的重要研究問題[1-5]，網(wǎng)絡特性的分析、化合物同分異構(gòu)體的分辨、分子的物理化學性質(zhì)的預測、活性影響的定量研究、材料和藥物的合成等都依賴于圖的結(jié)構(gòu)和相關(guān)拓撲參數(shù).近幾十年來，不斷的有新的拓撲指標被提出并得到研究，如距離型的Wiener指標[6]、Hosoya[7]指標、ABC(原子鍵聯(lián)通度)指標[8]、Szeged指標[9]、以及結(jié)構(gòu)型的子樹數(shù)指標[10,11](一個圖的所有非空子樹的個數(shù))和BC-子樹數(shù)指標[12](一個圖的任意兩片葉子間的距離都是偶數(shù)的子樹的個數(shù))等，其中后兩個指標相對較新，但是它們可以從一個新的維度分析圖或者化合物的結(jié)構(gòu)拓撲新特性，因此引起了國內(nèi)外學者的關(guān)注和研究.2006年Mkrtchyan[13]證明了BC-樹中存在一個最大部分適當0-1染色使得染色為0的邊形成一個最大匹配，2016年Yang 等人[14]提出了一種關(guān)于樹、單圈圖和無公共邊的雙圈圖的BC-子樹計數(shù)算法，Yang[15]等人又進一步給出了化合物分子六元素環(huán)螺鏈圖和聚苯六角鏈圖的BC-子樹數(shù)的計算方法.

書本圖是由多個環(huán)經(jīng)過同一條邊而形成的圖，三角形書本圖是線完美圖的一個關(guān)鍵構(gòu)建模塊[16]，Barioli曾用書本圖表示由具有兩個共同頂點的多個子圖組成的圖[17]，它的一些拓撲特性已經(jīng)得到了研究，如書本圖的完全正矩陣問題，書本圖與堆疊書本圖的拓撲刻畫[18]，書本圖的子樹計數(shù)[19]，書本圖的BC-子樹計數(shù)[20]等.本文給出了廣義書本圖GB(n)(n≥2)的定義，并基于生成函數(shù)、結(jié)構(gòu)分析和矩陣映射的方法，研究了GB(n)(n≥2)的BC-子樹計數(shù)問題以及一類特殊書本圖Bn,k的BC-子樹密度的漸進特性.

1 符號和定義

記G=(V(G),E(G);f,g)是頂點集|V(G)|=n，邊集|E(G)|=m的一個加權(quán)圖，f為其頂點生成函數(shù)，g為其邊生成函數(shù).G的所有非空無環(huán)的子結(jié)構(gòu)叫做G的子樹，令T為G的一顆含至少兩個頂點的子樹，若T的任意兩片葉子間的距離都是偶數(shù)，則T被稱為G的一顆BC-子樹.本文規(guī)定f:V(G)→R×R，g:E(G)→R(其中R是一個單位元為1的交換環(huán))，即，對于任何的v∈V(G)，有f(v)=(f(v)o,f(v)e)，這里，f(v)o和f(v)e分別代表頂點v的奇權(quán)重和偶權(quán)重.

另記L(G)為G的葉子集合，SBC(G)為G的所有BC-子樹的集合，S(G;v)為G的含頂點v的子樹集合，ηBC(G)為G的BC-子樹的個數(shù)，并記dG(u,v)(或d(u,v)，若無歧義)為G的頂點對u和v間的距離.對于任意一個頂點v和一顆子樹T1∈S(G;v)，記

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

SE(T1)={u|u∈V(T1)∧dT1(v,u)≡0(mod 2)}.

則對于加權(quán)圖G的一顆BC-子樹T2，定義

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

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

為了方便敘述，令T=(V(T),E(T);f,g)是一顆含n(n>1)個頂點的加權(quán)樹，vi是T的根節(jié)點，u≠vi是T的葉子節(jié)點且e=(u,v)為對應的懸掛邊.構(gòu)造頂點數(shù)為n-1的加權(quán)樹T′=(V(T′),E(T′);f′,g′)如下

其中V(T′)=V(T){u},E(T′)=E(T){e}，且對于任意vk∈V(T′)，g′(e)=g(e)(e∈E(T′)).

引理1.1[21]由上述符號定義，可知

(1)

引理1.2[14]由上述符號定義，可得加權(quán)樹T的含頂點u,v的BC-子樹生成函數(shù).

當l為奇數(shù)時,

(2)

當l為偶數(shù)時,

(3)

(4)

其中vl為Ts的一個葉子節(jié)點，且Vo(Ts)={v|v∈V(Ts)∧dTs(v,vl)≡1(mod 2)},Ve(Ts)={v|v∈V(Ts)∧dTs(v,vl)≡0(mod 2)}.

圖1 廣義星形樹 圖2 廣義書本圖GB(n)(n≥2)

定義1.6 將n+1條頂點個數(shù)均為k+2(k≥0)的路徑的兩個端點分別相連到一起，則由此形成的圖稱之為正則書本圖，記為Bn,k(n≥2;k≥0).易知，正則書本圖有k(n+1)+2個頂點和(n+1)(k+1)條邊.

2 廣義書本圖GB(n)(n≥2)的BC-子樹

引理2.1[21]令Pn=(V(Pn),E(Pn);f,g)為含n(n≥3)個頂點的路徑樹，頂點和邊的權(quán)重函數(shù)分別為f(v)=(0,y)(v∈V(Pn))和g(e)=z(e∈E(Pn))，則有

(5)

由引理2.1，不難得出如下定理.

(6)

(7)

因此廣義星形樹的BC-子樹生成函數(shù)為

(8)

定理2.3 令GB(n)=(V(GB(n)),E(GB(n));f,g)為定義1.5所述的加權(quán)廣義書本圖，頂點和邊的權(quán)重函數(shù)分別為f(v)=(0,y)(v∈V(GB(n)))和g(e)=z(e∈E(GB(n)))，則廣義書本圖的BC-子樹生成函數(shù)為

(9)

其中

(10)

(11)

(12)

(13)

證明將廣義書本圖GB(n)(n≥2)的BC-子樹分為以下4類：

(1)含u點但不含v點的BC-子樹；

(2)含v點但不含u點的BC-子樹；

(3)u和v兩點都含的BC-子樹；

(4)u和v兩點都不含的BC-子樹.

易知類(1)和類(2)，即廣義星形樹含中心點vs的BC-子樹，根據(jù)公式(8)，則類(1)和類(2)的BC-子樹生成函數(shù)為

(14)

圖4 廣義書本圖GB(2)的一個組合S0所對應的情況

圖5 廣義書本圖GB(2)的一個組合S0所對應情況的BK×I×J的存儲

根據(jù)上述分析，再結(jié)合公式(10)～(13)可得類(3)的BC-子樹生成函數(shù)為

(15)

對于類(4)，易知它是n+1條路徑，則通過公式(5)可得它的BC-子樹生成函數(shù)為

(16)

綜合公式(14)～(16)，定理得證.

將y=1,z=1代入公式(9)～(13)可得推論1.

推論1 廣義書本圖GB(n)(n≥2)的BC-子樹數(shù)為

ηBC(GB(n))=FBC(GB(n);(0,1),1)=

結(jié)合定義1.6以及公式(9)～(13)可得推論2.

推論2 正則書本圖Bn,k的BC-子樹數(shù)為

ηBC(Bn,k)=FBC(Bn,k;(0,1),1)=

(17)

根據(jù)推論2正則書本圖Bn,k(n=2,3,…,17;k=1,2)的BC-子樹數(shù)如表1所示.

表1 正則書本圖Bn,k(n=2,3,…,17;k=1,2)的BC-子樹數(shù)

3 正則書本圖Bn,k(n≥2;k≥0)的BC-子樹密度

這里我們分析正則書本圖Bn,k的BC-子樹密度.易知Bn,k的頂點個數(shù)為n(Bn,k)=k(n+1)+2.給每個頂點和邊分別賦權(quán)重(0,1)和z，由定理2.3可得Bn,k的BC-子樹的邊生成函數(shù)為

根據(jù)BC-子樹的密度定義及公式(9)～(13)與(17)，可知Bn,k的BC-子樹密度為

因此可得表2和圖6.

表2 正則書本圖Bn,k(n=2,3,…,7;k=1,2,3,4)的BC-子樹密度

圖6 正則書本圖Bn,k(n=2,3,…,7;k=1,2,…,6)的BC-子樹密度DBC(Bn,k)

由表2和圖6，可以觀察出來，對于任意n∈[2,7],Bn,k的BC-子樹密度DBC(Bn,k)在k=1時取得最大值；當n∈[2,7]且取定值時，DBC(Bn,k)隨著k的增大先驟然下降，然后整體呈現(xiàn)緩增趨勢.

4 結(jié) 論

本文利用生成函數(shù)、結(jié)構(gòu)分析及矩陣映射的方法，得到了廣義書本圖GB(n)(n≥2)的BC-子樹生成函數(shù)和BC-子樹數(shù)的公式，并簡要分析了正則書本圖Bn,k的BC-子樹密度DBC(Bn,k)的漸進特性.此研究為探索復雜圈圖和分子的新結(jié)構(gòu)特性提供了理論基礎(chǔ).