李笑笑， 靳夢(mèng)源， 孫道強(qiáng)， 李 昊， 楊 雨②

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

0 引 言

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

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

1 符號(hào)和定義

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

另記L(G)為G的葉子集合，SBC(G)為G的所有BC-子樹的集合，S(G;v)為G的含頂點(diǎn)v的子樹集合，ηBC(G)為G的BC-子樹的個(gè)數(shù)，并記dG(u,v)(或d(u,v)，若無歧義)為G的頂點(diǎn)對(duì)u和v間的距離.對(duì)于任意一個(gè)頂點(diǎn)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)}.

則對(duì)于加權(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)個(gè)頂點(diǎn)的加權(quán)樹，vi是T的根節(jié)點(diǎn)，u≠vi是T的葉子節(jié)點(diǎn)且e=(u,v)為對(duì)應(yīng)的懸掛邊.構(gòu)造頂點(diǎn)數(shù)為n-1的加權(quán)樹T′=(V(T′),E(T′);f′,g′)如下

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

引理1.1[21]由上述符號(hào)定義，可知

(1)

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

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

(2)

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

(3)

(4)

其中vl為Ts的一個(gè)葉子節(jié)點(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)}.

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

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

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

引理2.1[21]令Pn=(V(Pn),E(Pn);f,g)為含n(n≥3)個(gè)頂點(diǎn)的路徑樹，頂點(diǎn)和邊的權(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)廣義書本圖，頂點(diǎ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點(diǎn)但不含v點(diǎn)的BC-子樹；

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

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

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

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

(14)

圖4 廣義書本圖GB(2)的一個(gè)組合S0所對(duì)應(yīng)的情況

圖5 廣義書本圖GB(2)的一個(gè)組合S0所對(duì)應(yīng)情況的BK×I×J的存儲(chǔ)

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

(15)

對(duì)于類(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的頂點(diǎn)個(gè)數(shù)為n(Bn,k)=k(n+1)+2.給每個(gè)頂點(diǎn)和邊分別賦權(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，可以觀察出來，對(duì)于任意n∈[2,7],Bn,k的BC-子樹密度DBC(Bn,k)在k=1時(shí)取得最大值；當(dāng)n∈[2,7]且取定值時(shí)，DBC(Bn,k)隨著k的增大先驟然下降，然后整體呈現(xiàn)緩增趨勢(shì).

4 結(jié) 論

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