王艳春，孙伟刚，许文豪

(杭州电子科技大学理学院，浙江 杭州 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的重数为……