计算多重边树图的Hosoya指标

王艳春，孙伟刚，许文豪

(杭州电子科技大学理学院，浙江 杭州 310018)

计算多重边树图的Hosoya指标

王艳春，孙伟刚，许文豪

(杭州电子科技大学理学院，浙江 杭州 310018)

提出一种计算多重边树图的Hosoya指标的算法.通过逐个删除树的叶子节点，并给相应父节点权重增加两节点间边重数与叶子节点权重的比值的方法来计算其Hosoya指标，证明了新算法在理论上的可行性，最后用一个多重边树图验证该方法的有效性.

多重边树图；Hosoya指标；匹配

0 引 言

Hosoya指标是由日本化学家Haruo Hosoya于1971年提出[1]，自提出后得到了诸多关注.作为一种与分子图的特征多项式紧密相关的指标，它与分子的沸点、总π-电子能等物理化学性质密切相关，是分子拓扑学中的一个重要指标.文献[2-3]给出了n阶棒棒糖图和双星树的Hosoya指标序；文献[4]推导出了直径是3和4的n阶树的Hosoya指标的最大值；文献[5]得到了Hosoya指标第二小，第三小的双圈图；文献[6]提出了基于权重方法计算任意树Hosoya指标的线性算法.上述文献并没有涉及到含有多重边图的Hosoya指标的计算，为此本文提出了一种计算多重边树图的Hosoya指标的新方法，将矩阵的计算过程转化为对树的节点的操作，即逐个删除叶子节点同时增加相应父节点权重，从而得到指标的计算公式.

1 含多重边树图的Hosoya指标

在无向图中，关联一对顶点的无向边如果多于一条，称这些边为平行边或重边，平行边的条数称为重数，通常称含有多重边的图为多重图[7].设G=(V,E)是一个多重边图，边ei的重数为wi，如果M⊆E，且M中不含环且任意两边都不相邻，则称M为G的一个匹配.Z(G)表示所有匹配的数目，即

(1)

|M(G,k)|表示含图G中k条独立边的匹配的数目，令|M(G,0)|=1.含多重边的树图G3如图1所示.G3的匹配集合为M(G3,1)={e1,e2,e3,e4}，M(G3,2)={(e1,e3),(e1,e4)}.

图1 含多重边的树图G3

如果Gw是含n个节点的多重边图，Gw的边(vi,vj)的重数为wij，节点vi的权重为wi，由文献[6-7]知，

Z(G)=det(In+A(Gw))，

(2)

其中，

(3)

In表示n阶单位矩阵.

2 含多重边树图的Hosoya指标计算

记多重边树图Tw的节点集为V(Tw)={v1,v2,…,vn}，如果vi是它的叶子节点(无孩子节点)，eij=(vi,vj)是它的一条边，则由式(2)得

(4)

其中，wk=1，1≤k≤n，且wik=0，k∈{1,2,…,n}-{i,j}.计算式(4)得到

(5)

其中，B是删除第i行第i列得到的n-1阶矩阵.继续对Z(Tw)作以上变换，直到矩阵B的阶数降为1为止.此时得到

由上述过程可得如下定理,

1)若v是Tw的叶子节点，则wv=1；

图2 权值变化过程图

3 结束语

本文提出了一种计算含多重边树图的Hosoya指标的新方法.通过删除叶子节点并给相应父节点赋予相应的边权重，准确快速地计算了含多重边树图的Hosoya指标，对计算含多重边的一般网络的Hosoya指标具有借鉴意义.

[1]HOSOYAH.Topologicalindex.Anewlyproposedquantitycharacterizingthetopologicalnatureofstructuralisomersofsaturatedhydrocarbons[J].BulletinoftheChemicalSocietyofJapan, 1971, 44(9): 2332-2339.

[2]陈暑波,夏方礼,龙韬,等.棒棒糖图的Merrifield-Simmons和Hosoya指数[J].湖南城市学院学报(自然科学版),2008,17(3):39-41.

[3]肖正明.双星树的Merrifield-Simmons和Hosoya指数序[J].湖南城市学院学报(自然科学版),2007,16(4):50-51.

[4]曹庆信,陈祥恩,刘信生.直径是3和4的n阶树的Hosoya指数的最大值[J].甘肃联合大学学报(自然科学版),2009,23(3):31-34.

[5]李莎,卓玛措,王微.Hosoya指数第二小、第三小的双圈图[J].东北师大学报(自然科学版),2014,46(2):45-50.

[6]ZHANGJ,CHENX,SUNW.ALinear-TimeAlgorithmfortheHosoyaIndexofanArbitraryTree[J].MatchCommunicationsinMathematicalandinComputerChemistry, 2016, 75(3): 703-714.

[7]FARRELLEJ,WAHIDSA.D-graphs1:anintroductiontographswhosematchingpolynomialsaredeterminantsofmatrices[J].BulletinoftheInstituteofCombinatoricsanditsApplications, 1995, 15: 81-86.

[8]田玉芳,何中市.多重图的线图连通度[J].重庆大学学报(自然科学版),2005,28(10):94-98.

On the Hosoya Index of Trees with Multiple Edges

WANG Yanchun, SUN Weigang, XU Wenhao

(SchoolofScience,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

This paper proposes a new method for calculating the Hosoya index of trees with multiple edges and obtains its formula by deleting the leaf node and adding the ratio between the multiplicity of edges of two nodes and the weight of the leaf nodes to the weight of its parent node. The method is proved feasibly in theory and verified by a detailed graph.

multiple edges; Hosoya index; matching

10.13954/j.cnki.hdu.2017.01.022

2016-06-02

浙江省自然科学基金资助项目(LY16A010014)

王艳春，女，河南信阳人，硕士研究生，应用数学.通信作者：孙伟刚副教授，E-mail:wgsun@hdu.edu.cn.

O157.5

A

1001-9146(2017)01-0099-04