随机七边形链中两类拓扑指数的期望值研究.pdf

设G是n阶简单图,即所考虑的都是有限简单图,设G=（V(G),E(G)）是一个图,V(G）表示图的顶点集,E(G）表示图的边集,G的匹配数和独立集分别记作G的Hosoya指数和Merrifield-Simmons指数，记作m(G),i（G).根据不同连接方式画出的各类别的图形，结合给定的相关公式推出所有有着n个七边形的七边形链的Hosoya指数和Merrifield-Simmons指数的期望值公式.不同的连接方式有着不同的概率，结合推导出的两个不同指标的期望值公式，代入不同的概率，得到精确的不同连接方式下的两个指数的相关内容.进而探究出在随机七边形链中的Hosoya 指数和Merrifield-Simmons指数的期望值。关键词：七边形;Hosoya指数；Merrifield-Simmons指数；概率；期望；平均值中图分类号：0 157.6文献标识码：A文章编号：16 7 2-0 9 46(2 0 2 3)0 4-0 456-0 6Expected value of two kinds of topological indexes in random heptagonal chainsSUN Yushuang,GENG Xianya(School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan 232001,China)Abstract:Let G be a simple graph of order n,then,all the graphs considered were finitesimple graphs.Let G=(V(G),E(G)be a graph,V(G)represented the vertex set of thegraph,and E(G)represented the edge set of the graph.The number of matchings and thenumber of independent sets in a graph G were called the Hosoya index m(G)and theMerrifield-Simmons index i(G).According to various graphs drawn by different linkingmethods,the expected values of the two indexes of all heptagonal chains with n heptagonswere derived by combining the given relevant formulas.Different connection methods haddifferent probabilities.Combined with the expected value formula of two different indexesderived,different probabilities were substituted to obtain accurate contents of two indexesunder different connection methods.Furthermore,the expected values of the Hosoya indexand the Merrifield-Simmons index in the random heptagonal chain were explored.收稿日期:2 0 2 2-10-0 4.基金项目：安徽省自然科学基金（2 0 0 8 0 8 5MA01），安徽省高校自然科学基金（KJ2021A0451）作者简介：孙玉霜（19 9 7），女，硕士研究生，研究方向：图论研究.耿显亚（19 8 1-），男，教授，博士后，研究方向：图论与算法研究.第4期Key words:heptagon;Hosoya index;Merrifield Simmons index;probability;expectedvalue;average value孙玉霜，等：随机七边形链中两类拓扑指数的期望值研究 457本文所考虑的都是有限简单图，设G=(V(G),E(G)是一个图,V(G)表示图的顶点集，E(G)表示图的边集,对于一个顶点EV,图G-u是由V-ul给定的,对于一条边e,图 G-e是由一个图G删去一条边e给定的1-8 ,另外N(）=(uluweE表示在G中与有边相连的点，N=（U N()表示与有边连接的点且点包括在内3.1,5,图G中的边集合被记作M,M中的任何两条边都没有同一个顶点，则M是图G的匹配，用m（G)表示大小为k的图G的匹配数，显然mo(G)=1,m(G)|El,则m(G)=Zms(G)表示为C的总匹配数10-14,如果S是图G的点集合，独立集S中任何两点都没有同一条共用边，用i（G)表示图G的独立集的多少,显然i（G）=1,i(G)=V l,则i(G)=Zi(G)表示为G的总独立集数目13.在后续计算中，我们会用到如下公式：1）G u t ma n a n d Po l a n s k y 9,如果 uw 是 G中的一条边，则m(G)=m(G-w)+m(G-(u,v)(1)2）G u t ma n a n d Po l a n s k y 9,如果是 G 中的一个顶点，则i(G)=i(G-v)+i(G-Nc)3）G u t ma n a n d Po l a n s k y 9,如果 G 是由 Gj,G2,G组成,则m(G)=IIm(G),i(G)=Ili(G)4)m(p2)=2,m(p3)=3,m(p4)=5,m(ps)=8,m(pc)=13,m(C,)=29.5)i(pi)=2,i(p2)=3,i(p3)=5,i(p4)=8,i(ps)=13,i(P。)=2 1.其中：P，表示n个顶点的路,C,表示n个顶点的圈。G，可以视为具有n个七边形的链，也可以表示为末端有一个七边形的,如图1所示.G,-1图1有个七边形的链Figure 1A chain with a hexagon对于n3,最后的末端七边形有三种连接方式,这种局部排列分别表示为G，C,G,如图2所示Gn-2Figure 2 Three arrangements of heptagonal chain一个有n个七边形的随机链G,（P1,P2,Ps）在之后的每一步k=（3,4，,n）中都会有三种随机排列：1)Gk-1G,的概率表示为P1,2)Gk-1G,的概率表示为 P2,3)Gk-1G 的概率表示为 P3=1-Pl-P2.其中:P1,P2,P3是常数，与k无关.特别的，当pl=1,P2=1,P3=1时,图G,分别可记为邻链Qn，元链(2)M,对链Ln1在随机七边形链中Hosoya指数的期望值探究(3)Hosoya指数是一个随机变量，我们将得到其期望值E（m（G（Pi,P2,P），下面给出推导过程中所用到的末端连接的三类连接方式A:EA，AR,A),BBI,B,B,ChCI,C,VI(如图3所示）.1)如图2 中的G,=G,由式(1)和(3)得m(G,)=m(G,-e)+m(G,-u,vl)=m(C,)m(Gn-1)+m(P。)m(A n-2)=2 9 m(G n-1)+13m(An-2)VGi-2图2 七边形链的三种排列方式Gn-2G458.如果An-2=A,-2（如图3），由式(1）、（3)得m(An-2)=m(Pa)m(Gn-2)+m(P,)m(An-3)=13m(Gn-2)+8m(An-3)如果An-2=A-2（如图3），由式(1)、(3)得m(An-2)=m(Pa)m(Gn-2)+m(Ps)m(Bn-3)=13m(Gn-2)+8m(Bn-3)如果An-2=A-2（如图3），由式(1)、（3)得m(An-2)=m(P。)m(G n-2)+m(P,)m(Cn-3)=13m(Gn-2)+8m(Cn-3)Gn-3A12An-2Gn-3Gn-3Figure 3 Three types of end connection2)如图2 中的G,=G,由式(1)、(3)得m(G,)=m(C,)m(Gn-1)+m(P。)m(Bn-2)=29m(Gn-1)+13m(Bn-2)如果Bn-2=B,-2（如图3),由式(1)（3)得m(Bn-2)=m(pc)m(Gn-2)+m(pi)m(p4)m(An-3)=13m(Gn-2)+5m(An-3)如果B,-2=B,-2（如图3）,由式(1）（3)得m(Bn-2)=m(pc)m(Gn-2)+m(pi)m(p4)m(Bn-3)=13m(Gn-2)+5m(Bn-3)如果Bn-2=B-2（如图3）,由式(1)、（3)得m(Bn-2)=m(p)m(Gn-2)+m(pi)m(p4)m(Cn-3)=13m(Gn-2)+5m(Cn-3)3)如图2 中G,=C的,由式(1)、(3)得m(G,)=m(C,)m(Gn-1)+m(pc)m(Cn-2)=29m(Gn-1)+13m(Cn-2)哈尔滨商业大学学报（自然科学版）m(Cn-2)=m(pa)m(Gn-2)+m(p2)m(ps)m(An-3)=13m(Gn-2)+6m(An-3)如果Cn-2=C-2（如图3），由式(1)、（3)得m(Cn-2)=m(p6)m(Gn-2)+m(p2)m(p3)m(Bn-3)=13m(G,-2)+6m(Bn-3)如果C-2=C-2（如图3），由式(1）、（3)得m(Cn-2)=m(p6)m(Gn-2)+m(p2)m(p:)m(Cn-3)=13m(Gn-2)+6m(Cn-3)根据式(1）（3）且pi+p2+P3=1可以得到期望：E(m(G,)=p,E(m(C,)+pE(m(C)+GGAGGn-3B%2B%2Gn-3G.Ci图3末端连接的三类连接方式第39 卷如果Cn-2=C-2（如图3）,由式(1)、（3)得P:E(m(Gi)E(m(G,)=29E(m(Gn-1)+13pE(m(An-2)+13p2E(m(Bn-2)+13psE(m(Cn-2)=29E(m(Gn-1)+169E(m(Gn-2)+(104pi+65piP2+78piPs)E(m(An-3)+(104piP2+65p2+78p2P3)E(m(Bn-3)+(104piP3+65p2Ps+78p3)E(m(Cn-3)显然有E(m(An-3)=pIE(m(A,-3)+p2E(m(A-3)+P,E(m(A-)=13E(m(Gn-3)+8p,E(m(An-4)+8p,E(m(Bn-4)+8p,E(m(Cn-4)E(m(Bn-3)=piE(m(BH-3)+p2E(m(B-3)+p,E(m(B-3)=13E(m(Gn-3)+5p)E(m(An-4)+5p,E(m(Bn-4)+5p;E(m(Cn-4)E(m(Cn-3)=p,E(m(Ch-3)+p2E(m(C-3)+p,E(m(Cm-3)=13E(m(G,-3)+6p,E(m(An-4)+6p2E(m(Bn-4)+6p;E(m(Cn-4)根据上式，可分别得到(104pi+65piP2+78pips)E(m(An-3)=13(104pi+65piP2+78pip:)E(m(Gn-3)+8pi(104pi+65piP2+78piP3)E(m(An-4)+8pi(104piP2+65p2+78p2P)E(m(Bn-4)+8pi(104piP:+65p2P;+78p3)E(m(Cn-3)=13(104pi+65piP2+78piP:)E(m(Gn-3)+第4期8p E(m(Gn-1)-29E(m(Gn-2)-169E(m(Gn-3)(104piP2+65p2+78p2Ps)E(m(Bn-4)=13(104piP2+65p2+78p2Ps)E(m(Gn-3)+5p2E(m(G,-1)-29E(m(Gn-2)-169E(M(Gn-3)(104piP3+65p2P3+78p3)E(m(Cn-3)=13(104piPs+65paP:+78p3)E(m(Cn-3)+6psE(m(Gn-1)-29E(m(Gn-2)-169E(m(Gn-3)综上所述且根据p1+P2+P3=1即得关于Hosoya指数期望值的递推公式：E(m(G,)=(29+8pl+5p2+6p3)E(m(Gn-1)+(169-232p-145p2-174p3)E(m(Gn-2)=(2pi-P2+35)E(m(Gn-1)-(58pi-29p2-5)E(m(Gn-2)另外，期望值存在两个极限：E(m(G)=m(C)=29 E(m(G)=1 010利用上述递推关系和边界条件，我们可以得到：定理2.1在随机七边形链中Hosoya指数的期望值E(m(G,)=2p1-P2-23+(-2pi+p2+23)+676X2(2p1+P2+23)+6762p1-P2+35+(-2p;+p,+23)+676)-2p1+P2+23+(-2pi+p2+23)+6762/(2p1+P2+23)+676(2p1-P2+35-(-2p1+p,+23)+676)分别令P1=1,P2=1,P3=1我们可以从定理2.1中得到O,M,L,的Hosoya指数的推论.推论2.2m(0.)=-21+/L117)2/111721+/1 117(37-/1117)2/1 1172m(M,)=12+V313(17+/313)+2313孙玉霜，等：随机七边形链中两类拓扑指数的期望值研究m(L.)=-23+/1 205,2/120523+/1 20535-V12052/1 20522在随机七边形链中Merrifield-Simmons 指数的期望值探究Merrifield-Simmons指数是一个随机变量，我们将得到其期望值E（G，（P1,P2,Ps），下面给出推导过程中所涉及的末端连接的三类连接方式Ae(Al,Ar,ARI,B(Bl,Be,BiI,Che ICh,Ce,Ch!(如图3 所示).1)如图2 中的G,=G,由式(2)、(3)得i(Gh)=i(Gn-v)+i(Gn-Ncu)=i(P。)i(G n-1)+i(P4)i(A n-2)=21i(G,-1)+8i(An-2)如果An-2=A,-2（如图3）,由式(2）、（3)得i(An-2)=i(P,)i(Gn-2)+i(P4)i(An-3)=13i(G,-2)+8i(An-3)如果An-2=A-2（如图3)由式(2）、(3)得i(An-2)=i(P,)i(Gn-2)+i(P4)i(Bn-3)=13i(Gn-2)+8i(Bn-3)如果An-2=Az-2（如图3）,由式(2）、（3)得i(An-2)=i(P,)i(Gn-2)+i(P4)i(Cn-3)=+22(37+V1117+2459.12+/313(17-/313)2/313(35+/1 205)213i(Gn-2)+8i(Cn-3)2)如图2 中的G,=G,由式(2)、(3)得i(Gh)=i(P。)i(G n-1)+i(P4)i(Bn-2)=21i(Gn-1)+8i(Bn-2)如果B,-2=B-2（如图3），由式(2）、（3)得i(Bn-2)=i(pi)i(p4)i(Gn-2)+i(p3)i(An-3)=16i(Gn-2)+5i(An-3)如果B,-2=B_2（如图3），由式(2）、（3)得i(Bn-2)=i(pi)i(p4)i(Gn-2)+i(p3)i(Bn-3)=16i(Gn-2)+5i(Bn-3)如果B,-2=B-2（如图3），由式(2）、（3)得i(Bn-2)=i(pi)i(p4)i(Gn-2)+i(p3)i(Cn-3)=16i(Gn-2)+5i(Cn-3)3)如图2 中的G,=G,由式(2）、(3)得460i(G,)=i(P。)i(G n-1)+i(P4)i(Cn-2)=21i(G,-1)+8i(Cn-2)如果C,-2=C,-2(如图3),由式(2)、（3)得i(Cn-2)=i(P,)i(P)i(Gn-2)+i(PI)i(P,)i(An-3)=15i(Gn-2)+6i(An-3)如果Cn-2=CF-2（如图3),由式(2)、（3)得i(Cn-2)=i(P,)i(P,)i(Gn-2)+i(Pl)i(P,)i(Bn-3)=15i(Gn-2)+6i(Bn-3)如果Cn-2=C%-2（如图3),由式(2)、(3)得i(Cn-2)=i(P,)i(P)i(Gn-2)+i(Pr)i(P,)i(Cn-3)=15i(Gn-2)+6i(Vn-3)根据式(1）（3)且Pi+P2+p3=1可以得到期望：E(i(G,)=p)E(i(G)+pE(i(G)+p,E(i(G)显然有E(i(G,)=21E(i(Gn-1)+(104pi+128p2+120p:)E(i(G,-2)+(64pi+40piP2+48piP3)E(i(An-3)+(64piP2+40p2+48p2P:)E(i(Bn-3)+(64piP;+40p2P;+48p3)E(i(Cn-3)E(i(An-3)=pIE(i(A-3)+p2E(i(A,-3)+p,E(i(A-3)=13E(i(Gn-3)+8p,E(i(An-4)+8p,E(i(Bn-4)+8p,E(i(Cn-4)E(i(Bn-3)=prE(i(Bl-3)+p2E(i(B-3)+p,E(i(Br-3)=16E(i(G,-3)+5p,E(i(An-4)+5p,E(i(Bn-4)+5p,E(i(Cn-4)E(i(Bn-3)=p,E(i(Bi-3)+P,E(i(B,-3)+p,E(i(B,-3)=15E(i(G,-3)+6p,E(i(An-4)+6p,E(i(Bn-4)+6p,E(i(Cn-4)根据上式，可分别得到(64pi+40piP2+48piPs)E(i(An-3)=13(64pi+40piP2+48pipPs)E(i(G,-3)+8pE(i(Gn-1)-21E(i(G,-2)-(104pi+128p2+120p3)E(i(Gn-3)J(64piP2+40p2+48p2Ps)E(i(Bn-3)=16(64piP2+40p2+48p2P3)E(i(Gn-3)+5p2E(i(Gn-1)-21E(i(Gn-2)-(104p1+128p2+120p3)E(i(Gn-3)(64piPs+40p2P;+48p3)E(i(Cn-3)=哈尔滨商业大学学报（自然科学版）Merrifield-Simmons指数期望值的递推公式：E(i(G,)=(21+8pl+5p2+6p:)E(i(Gn-1)+(-64pi+23p2-6p;)E(i(Gn-2)=(2p1-P2+27)E(i(Gn-1)-(58p1-29p2+6)E(i(G,-2)E(i(G)=i(C4)=7 E(i(G,)=777利用上述递推关系和边界条件，可以得到：定理 3.1在随机七边形链中Merrifield-Simmons指数的期望值E(i(G,)=-2pi+p2+31+(2pi-p,-31)-256X2/(2p1-p2-31)-256(2p1-P2+27+(2p1-p2-31)-256)2p1-P2-31+(2pi-Pp2-31)-256X2/(2p;-P2-31)-256(2p1-P2+27-/(2p,-P,-31)-256)分别令P1=1,P2=1,P=1,我们可以从定理3.1中得到O,M,L,的Merrifield-Simmons指数的推论：推论3.229+/585i(0,)=22/585-29+/585(29-/585)2/58522+/3i(Mn)2/3(13+8/3)+=2+/,X2/2(13+8/3)+/705(27+705i(L,)=31+X2/705-31+/705(27-/705)2/70523 结 语本文得到了含有n个七边形的随机链的第39 卷15(64piP3+40p2P3+48p3)E(i(Gn-3)+6psE(i(Gn-1)-21E(i(Gn-2)-(104pi+128p2+120ps)E(i(Gn-3)J综上所述且根据p3=1-P1-P2可以得到关于+2229+585+2+2第4期Hosoya指数Merrifield-Simmons指数的期望值的具体推导解析公式,并分别讨论了m(G,)和i（G,)的期望值，它们的组成和结构也正在向图论的相关研究方向发展.参考文献：1 ANDRIATINAN.Hosoys index and Merrifield-Simmonsindex of trees with prescribed degree sequence J.Discret Appl Math.2013,161:724-741.2ALI A,FURTULA B,GUTMAN I,et al.Augmentedzagreb index:Extremal results and bounds J.MATCH Commun.Math.Comput.Chem.2021,85:211-244.3马丽，苏苗苗，苗芸，等.多环链的Hosoya多项式J.科技风,2 0 19(4):33-35.4唐保祥，任韩.两类图完美匹配的计数公式J.吉林大学学报：理学版,2 0 16,54（4）：7 9 0-7 9 2.5 DENG H.Wiener indices of spiro and polyphenylhexagonal chains J.Mathematical and ComputerModelling,2011,55(3):634-644.6苏晓海，孙泽清，俞天仕，等.两类图族的Merrifield-Simmons指标J.安徽大学学报：自然科学版，2 0 2 2，46(1):32-36.7王守中，江蓉.三角系统T_n的匹配数与点独立集数J.西南师范大学学报：自然科学版，2 0 10,35(1):19-22.孙玉霜，等：随机七边形链中两类拓扑指数的期望值研究(2):550-562.12LIU Y,ZHUANG W,LIANG Z.Largest Hosoya index andsmallest Merrifield-Simmons index in tricyclicgraphs J.MATCH Commun Math Comput Chem.,2015,73(1):195-224.13CRUZ R,RADA J.Extremal graphs for exponentialsVDB indicesJ.Kragujevac J.Math.,2022,46:105-113.14HAFEEZ S,FAROOQ R.On generalized inverse sumindeg index and energy of graphs J.AIMS Math.,2020,5(3):2388-2411.15 ZHU Z,YUAN C,ANDRIANTIANA E,et al.Graphswith maximal Hosoya index and minimal Merrifield-Simmons index J.D i s c r e t M a t h.，2 0 14,32 9:77 87.461.8肖正明.双星树的Merrifield-Simmons和Hosoya指数序J.湖南城市学院学报：自然科学版,2 0 0 7，（4）：50 59.9GUTMAN I,POLANSKY O E.Mathematical conceptsin organic chemistry M.Berlin:Springer,1986.10 索郎王青，田双亮，杨青.特殊树的冠积的Merrifield-Simmons指标和Hosoya指标J.鲁东大学学报：自然科学版,2 0 2 0,36（1）：2 4-2 7.11HUANG,KUANG,DENG.The expect values of Hosoyaindex and Merrifield-Simmons index in a randompolyphenylene chain J.J Comb Optim.,2016,3(上接455页）10WANG L,WONG D.Bounds for the matchingnumber，t h e e d g e c h r o m a t i c n u m b e r a n d t h eindependence number of a graph in terms of rank J.Disc.Appl.Math,2014,166:276-281.11 MA X,WONG D,TIAN F.Nullity of a graph in termsof the dimension of cycle space and the number ofpendent vertices J.Disc Appl Math,2016,215:171-176.12 李鑫图的零度与独立数、悬挂点数关系的研究D.徐州：中国矿业大学，2 0 16.13CVETKOVIC D,GUTMAN I.The algebraic multiplicityof the number zero in the spectrum of a bipartite graphJ.Mat Vesnik(Beograd),1972,9:141-150.14WANG L.Nullity of a graph in terms of path covernumber J.Linear and Multilinear Algebra,2021,69(10):1902-1908.