王艷春，孫偉剛，許文豪

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

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

王艷春，孫偉剛，許文豪

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

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

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

0 引 言

Hosoya指標(biāo)是由日本化學(xué)家Haruo Hosoya于1971年提出[1]，自提出后得到了諸多關(guān)注.作為一種與分子圖的特征多項式緊密相關(guān)的指標(biāo)，它與分子的沸點、總π-電子能等物理化學(xué)性質(zhì)密切相關(guān)，是分子拓?fù)鋵W(xué)中的一個重要指標(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)重方法計算任意樹Hosoya指標(biāo)的線性算法.上述文獻(xiàn)并沒有涉及到含有多重邊圖的Hosoya指標(biāo)的計算，為此本文提出了一種計算多重邊樹圖的Hosoya指標(biāo)的新方法，將矩陣的計算過程轉(zhuǎn)化為對樹的節(jié)點的操作，即逐個刪除葉子節(jié)點同時增加相應(yīng)父節(jié)點權(quán)重，從而得到指標(biāo)的計算公式.

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

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

(1)

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

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

(2)

其中，

(3)

In表示n階單位矩陣.

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

記多重邊樹圖Tw的節(jié)點集為V(Tw)={v1,v2,…,vn}，如果vi是它的葉子節(jié)點(無孩子節(jié)點)，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階矩陣.繼續(xù)對Z(Tw)作以上變換，直到矩陣B的階數(shù)降為1為止.此時得到

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

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

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

3 結(jié)束語

本文提出了一種計算含多重邊樹圖的Hosoya指標(biāo)的新方法.通過刪除葉子節(jié)點并給相應(yīng)父節(jié)點賦予相應(yīng)的邊權(quán)重，準(zhǔn)確快速地計算了含多重邊樹圖的Hosoya指標(biāo)，對計算含多重邊的一般網(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é)報(自然科學(xué)版),2008,17(3):39-41.

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

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

[5]李莎,卓瑪措,王微.Hosoya指數(shù)第二小、第三小的雙圈圖[J].東北師大學(xué)報(自然科學(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é)報(自然科學(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é)基金資助項目(LY16A010014)

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

O157.5

A

1001-9146(2017)01-0099-04