王艷春，孫偉剛，許文豪

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

計(jì)算多重邊樹圖的Hosoya指標(biāo)

王艷春，孫偉剛，許文豪

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

提出一種計(jì)算多重邊樹圖的Hosoya指標(biāo)的算法.通過(guò)逐個(gè)刪除樹的葉子節(jié)點(diǎn)，并給相應(yīng)父節(jié)點(diǎn)權(quán)重增加兩節(jié)點(diǎn)間邊重?cái)?shù)與葉子節(jié)點(diǎn)權(quán)重的比值的方法來(lái)計(jì)算其Hosoya指標(biāo)，證明了新算法在理論上的可行性，最后用一個(gè)多重邊樹圖驗(yàn)證該方法的有效性.

多重邊樹圖；Hosoya指標(biāo)；匹配

0 引 言

Hosoya指標(biāo)是由日本化學(xué)家Haruo Hosoya于1971年提出[1]，自提出后得到了諸多關(guān)注.作為一種與分子圖的特征多項(xiàng)式緊密相關(guān)的指標(biāo)，它與分子的沸點(diǎn)、總π-電子能等物理化學(xué)性質(zhì)密切相關(guān)，是分子拓?fù)鋵W(xué)中的一個(gè)重要指標(biāo).文獻(xiàn)[2-3]給出了n階棒棒糖圖和雙星樹的Hosoya指標(biāo)序；文獻(xiàn)[4]推導(dǎo)出了直徑是3和4的n階樹的Hosoya指標(biāo)的最大值；文獻(xiàn)[5]得到了Hosoya指標(biāo)第二小，第三小的雙圈圖；文獻(xiàn)[6]提出了基于權(quán)重方法計(jì)算任意樹Hosoya指標(biāo)的線性算法.上述文獻(xiàn)并沒(méi)有涉及到含有多重邊圖的Hosoya指標(biāo)的計(jì)算，為此本文提出了一種計(jì)算多重邊樹圖的Hosoya指標(biāo)的新方法，將矩陣的計(jì)算過(guò)程轉(zhuǎn)化為對(duì)樹的節(jié)點(diǎn)的操作，即逐個(gè)刪除葉子節(jié)點(diǎn)同時(shí)增加相應(yīng)父節(jié)點(diǎn)權(quán)重，從而得到指標(biāo)的計(jì)算公式.

1 含多重邊樹圖的Hosoya指標(biāo)

在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于一條，稱這些邊為平行邊或重邊，平行邊的條數(shù)稱為重?cái)?shù)，通常稱含有多重邊的圖為多重圖[7].設(shè)G=(V,E)是一個(gè)多重邊圖，邊ei的重?cái)?shù)為wi，如果M?E，且M中不含環(huán)且任意兩邊都不相鄰，則稱M為G的一個(gè)匹配.Z(G)表示所有匹配的數(shù)目，即

(1)

|M(G,k)|表示含圖G中k條獨(dú)立邊的匹配的數(shù)目，令|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個(gè)節(jié)點(diǎn)的多重邊圖，Gw的邊(vi,vj)的重?cái)?shù)為wij，節(jié)點(diǎn)vi的權(quán)重為wi，由文獻(xiàn)[6-7]知，

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

(2)

其中，

(3)

In表示n階單位矩陣.

2 含多重邊樹圖的Hosoya指標(biāo)計(jì)算

記多重邊樹圖Tw的節(jié)點(diǎn)集為V(Tw)={v1,v2,…,vn}，如果vi是它的葉子節(jié)點(diǎn)(無(wú)孩子節(jié)點(diǎn))，eij=(vi,vj)是它的一條邊，則由式(2)得

(4)

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

(5)

其中，B是刪除第i行第i列得到的n-1階矩陣.繼續(xù)對(duì)Z(Tw)作以上變換，直到矩陣B的階數(shù)降為1為止.此時(shí)得到

由上述過(guò)程可得如下定理,

1)若v是Tw的葉子節(jié)點(diǎn)，則wv=1；

圖2 權(quán)值變化過(guò)程圖

3 結(jié)束語(yǔ)

本文提出了一種計(jì)算含多重邊樹圖的Hosoya指標(biāo)的新方法.通過(guò)刪除葉子節(jié)點(diǎn)并給相應(yīng)父節(jié)點(diǎn)賦予相應(yīng)的邊權(quán)重，準(zhǔn)確快速地計(jì)算了含多重邊樹圖的Hosoya指標(biāo)，對(duì)計(jì)算含多重邊的一般網(wǎng)絡(luò)的Hosoya指標(biāo)具有借鑒意義.

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

[2]陳暑波,夏方禮,龍韜,等.棒棒糖圖的Merrifield-Simmons和Hosoya指數(shù)[J].湖南城市學(xué)院學(xué)報(bào)(自然科學(xué)版),2008,17(3):39-41.

[3]肖正明.雙星樹的Merrifield-Simmons和Hosoya指數(shù)序[J].湖南城市學(xué)院學(xué)報(bào)(自然科學(xué)版),2007,16(4):50-51.

[4]曹慶信,陳祥恩,劉信生.直徑是3和4的n階樹的Hosoya指數(shù)的最大值[J].甘肅聯(lián)合大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,23(3):31-34.

[5]李莎,卓瑪措,王微.Hosoya指數(shù)第二小、第三小的雙圈圖[J].東北師大學(xué)報(bào)(自然科學(xué)版),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].重慶大學(xué)學(xué)報(bào)(自然科學(xué)版),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

浙江省自然科學(xué)基金資助項(xiàng)目(LY16A010014)

王艷春，女，河南信陽(yáng)人，碩士研究生，應(yīng)用數(shù)學(xué).通信作者：孫偉剛副教授，E-mail:wgsun@hdu.edu.cn.

O157.5

A

1001-9146(2017)01-0099-04