广义书本图的BC-子树计数及渐近密度特性分析*

李笑笑， 靳梦源， 孙道强， 李 昊， 杨 雨②

(①平顶山学院软件学院，467000，河南省平顶山市；②上海交通大学数学科学学院，200240，上海市)

0 引 言

图的结构和相关拓扑参数是众多交叉领域学科的重要研究问题[1-5]，网络特性的分析、化合物同分异构体的分辨、分子的物理化学性质的预测、活性影响的定量研究、材料和药物的合成等都依赖于图的结构和相关拓扑参数.近几十年来，不断的有新的拓扑指标被提出并得到研究，如距离型的Wiener指标[6]、Hosoya[7]指标、ABC(原子键联通度)指标[8]、Szeged指标[9]、以及结构型的子树数指标[10,11](一个图的所有非空子树的个数)和BC-子树数指标[12](一个图的任意两片叶子间的距离都是偶数的子树的个数)等，其中后两个指标相对较新，但是它们可以从一个新的维度分析图或者化合物的结构拓扑新特性，因此引起了国内外学者的关注和研究.2006年Mkrtchyan[13]证明了BC-树中存在一个最大部分适当0-1染色使得染色为0的边形成一个最大匹配，2016年Yang 等人[14]提出了一种关于树、单圈图和无公共边的双圈图的BC-子树计数算法，Yang[15]等人又进一步给出了化合物分子六元素环螺链图和聚苯六角链图的BC-子树数的计算方法.

书本图是由多个环经过同一条边而形成的图，三角形书本图是线完美图的一个关键构建模块[16]，Barioli曾用书本图表示由具有两个共同顶点的多个子图组成的图[17]，它的一些拓扑特性已经得到了研究，如书本图的完全正矩阵问题，书本图与堆叠书本图的拓扑刻画[18]，书本图的子树计数[19]，书本图的BC-子树计数[20]等.本文给出了广义书本图GB(n)(n≥2)的定义，并基于生成函数、结构分析和矩阵映射的方法，研究了GB(n)(n≥2)的BC-子树计数问题以及一类特殊书本图Bn,k的BC-子树密度的渐进特性.

1 符号和定义

记G=(V(G),E(G);f,g)是顶点集|V(G)|=n，边集|E(G)|=m的一个加权图，f为其顶点生成函数，g为其边生成函数.G的所有非空无环的子结构叫做G的子树，令T为G的一颗含至少两个顶点的子树，若T的任意两片叶子间的距离都是偶数，则T被称为G的一颗BC-子树.本文规定f:V(G)→R×R，g:E(G)→R(其中R是一个单位元为1的交换环)，即，对于任何的v∈V(G)，有f(v)=(f(v)o,f(v)e)，这里，f(v)o和f(v)e分别代表顶点v的奇权重和偶权重.

另记L(G)为G的叶子集合，SBC(G)为G的所有BC-子树的集合，S(G;v)为G的含顶点v的子树集合，ηBC(G)为G的BC-子树的个数，并记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)}.

则对于加权图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)个顶点的加权树，vi是T的根节点，u≠vi是T的叶子节点且e=(u,v)为对应的悬挂边.构造顶点数为n-1的加权树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]由上述符号定义，可得加权树T的含顶点u,v的BC-子树生成函数.

当l为奇数时,

(2)

当l为偶数时,

(3)

(4)

其中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)}.

图1 广义星形树 图2 广义书本图GB(n)(n≥2)

定义1.6 将n+1条顶点个数均为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)个顶点的路径树，顶点和边的权重函数分别为f(v)=(0,y)(v∈V(Pn))和g(e)=z(e∈E(Pn))，则有

(5)

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

(6)

(7)

因此广义星形树的BC-子树生成函数为

(8)

定理2.3 令GB(n)=(V(GB(n)),E(GB(n));f,g)为定义1.5所述的加权广义书本图，顶点和边的权重函数分别为f(v)=(0,y)(v∈V(GB(n)))和g(e)=z(e∈E(GB(n)))，则广义书本图的BC-子树生成函数为

(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-子树，根据公式(8)，则类(1)和类(2)的BC-子树生成函数为

(14)

图4 广义书本图GB(2)的一个组合S0所对应的情况

图5 广义书本图GB(2)的一个组合S0所对应情况的BK×I×J的存储

根据上述分析，再结合公式(10)～(13)可得类(3)的BC-子树生成函数为

(15)

对于类(4)，易知它是n+1条路径，则通过公式(5)可得它的BC-子树生成函数为

(16)

综合公式(14)～(16)，定理得证.

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

推论1 广义书本图GB(n)(n≥2)的BC-子树数为

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

结合定义1.6以及公式(9)～(13)可得推论2.

推论2 正则书本图Bn,k的BC-子树数为

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

(17)

根据推论2正则书本图Bn,k(n=2,3,…,17;k=1,2)的BC-子树数如表1所示.

表1 正则书本图Bn,k(n=2,3,…,17;k=1,2)的BC-子树数

3 正则书本图Bn,k(n≥2;k≥0)的BC-子树密度

这里我们分析正则书本图Bn,k的BC-子树密度.易知Bn,k的顶点个数为n(Bn,k)=k(n+1)+2.给每个顶点和边分别赋权重(0,1)和z，由定理2.3可得Bn,k的BC-子树的边生成函数为

根据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的增大先骤然下降，然后整体呈现缓增趋势.

4 结 论

本文利用生成函数、结构分析及矩阵映射的方法，得到了广义书本图GB(n)(n≥2)的BC-子树生成函数和BC-子树数的公式，并简要分析了正则书本图Bn,k的BC-子树密度DBC(Bn,k)的渐进特性.此研究为探索复杂圈图和分子的新结构特性提供了理论基础.