一些关联图的拉普拉斯谱和基尔霍夫指标.pdf
《一些关联图的拉普拉斯谱和基尔霍夫指标.pdf》由会员分享,可在线阅读,更多相关《一些关联图的拉普拉斯谱和基尔霍夫指标.pdf(6页珍藏版)》请在咨信网上搜索。
1、第37 卷第2 期2024年4月文章编号:10 0 4-8 8 2 0(2 0 2 4)0 2-0 12 8-0 6烟台大学学报(自然科学与工程版)Journal of Yantai University(Natural Science and Engineering Edition)Vol.37 No.2Apr.2024doi:10.13951/ki.37-1213/n.230701一些关联图的拉普拉斯谱和基尔霍夫指标于越,郭帅(青岛理工大学理学院,山东青岛2 6 6 52 5)摘要:基于图G,定义了三种关联图GI,G z 和Gs,其拉普拉斯矩阵可以经过恰当排序表出。利用图论和行列式的性质以
2、及代数组合的方法,研究这些关联图的拉普拉斯谱和基尔霍夫指标,最后得出了相应的结果。关键词:拉普拉斯谱;基尔霍夫指标;关联图中图分类号:0 157.5文献标志码:A1引言和预备知识本文研究的均为简单连通无向图,对于顶点数为n,边数为m的图G,V(G)=(u 1,U 2,,U n 和E(G)分别表示它的顶点集合和边集。图G的邻接矩阵为A(G)=(j)n x n,其中若顶点u;和u;相邻,则j=1。否则,a=O。令d表示为图G中顶点;的度,则D(G)=d i a g i d i,d,,d,表示由图G的顶点的度组成的对角矩阵。图 G的拉普拉斯矩阵为 L(G)=D(G)-A(G)。L(G)的特征多项式为
3、Pc()=lxI-L(G)I,其中I为单位矩阵,方程Pc()=O的根为图G的拉普拉斯特征值。所有特征值集合称为图G的拉普拉斯谱,记为 S(G)=1o,入n-1,其中0=入。入,入n-1是L(G)的特征值。显然,图 G的邻接矩阵A(G)是一个对称矩阵,拉普拉斯矩阵L(G)是半正定的。1993年,KLEIN和RANDIC第一次提出了电阻距离 的概念。他们把图G中的每条边都用单位电阻来代替,这样图G就变成了一个电网络。图G中任意两点;和u;之间的电阻距离,记作ri,定义为电网络中两个节点之间的等效电阻,就是在这两个节点之间施加一个电压后电路中的总电压和总电流的比值。图G的基尔霍夫指标),记作Kf(G
4、),定义为图G中所有顶点对之间的电阻距离的和,即 Kf(G)=r i。在电网络理论中,基尔霍夫指标反应了网络的连通性。在化学领域中,图的基尔霍夫指标可以用来描述分子的结构特征,在定量构效关系(quantitative structure activity relationship,Q SA R)和定量构性关系(quantitative structureproperties relationship,QSPR)的研究中发挥着重要的作用。电阻距离和基尔霍夫指标拥有广泛的应用前景,在物理、工程、数学、化学、生态学等众多学科领域都受到重视,得到了广泛地研究2 。众多学者给出了一些特殊图类的基尔霍夫指
5、标的精确的显式表达式,如完全图、循环图、圈和凯莱图等3-8 。同时,对于一些通过在图上做一元或者二元运算得到的图,如剖分图、三角化以及合成图等9-14,电阻距离和基尔霍夫指标也得到了计算。下面给出三种关联图15 的定义,设图G是n个顶点的图,顶点集V(G)=(u i,D 2,,。另一顶点集mU=Uuk,us=(u,un,unl且ml。h=1收稿日期:2 0 2 3-0 7-0 3基金项目:国家自然科学基金资助项目(12 17 1414);山东省自然科学基金资助项目(ZR2020QF028)。通信作者:于越(),助教,硕士,主要研究方向为图论及其应用。第2 期定义1给定图G和顶点集U,连接与uw
6、(i=1,2,,n;k=1,2,m),生成的关联图为图G,邻接矩阵记为A,拉普拉斯矩阵记为LI。定义2 给定图G和顶点集U,连接,ui,u2i,,u m(i=1,2,n)为完全图,生成的关联图为图Gz,邻接矩阵记为A,拉普拉斯矩阵记为L2。定义3给定图G和图C的m个复制(顶点集为U),连接;,ui,uzi,um(i=1,2,n)为完全图,生成的关联图为图G,邻接矩阵记为A,拉普拉斯矩阵记为L3。设图G是顶点数为n的r-正则图,通过恰当排序可得A,为块箭型矩阵,A和A,为块循环矩阵。即-1A,=L,=10A1101A11A11于越,等:一些关联图的拉普拉斯谱和基尔霍夫指标A11011A1291(
7、m+r)I-A00110(m+r)I-A-1L3-1-11-1(m+r)I-A-1L-1-1(m+r)I-A-1-170.01-1-1ml-1.-1ml-1-1(m+r)I-A.2关联图的拉普拉斯谱和基尔霍夫指标引 理 1 4-5 设图G是顶点数为n的图(n2),则基尔霍夫指标为这个引理巧妙地将图的基尔霍夫指标与拉普拉斯特征值密切联系到了一起,这是一个非常重要的结论。后面在计算关联图的基尔霍夫指标时,主要依据此公式。2.1关联图的拉普拉斯谱定理1设图是顶点数为n的r-正则图,拉普拉斯特征值分别为入。=0,入1,,入n-1,则三种关联图的拉普拉斯谱为n-1Kf(C)=nZ入。22S(G,)=入。
8、=0,入1,.,an-1,(m+1),(m+1+入),.,(m+1+n-)。=0I xI-L,I=证明已知图G是顶点数为n的r-正则图,拉普拉斯特征值为入。=0,入1,,入n-1,设其邻接矩阵为A,则IA=()(-)(n-1)=。下面根据定义依次求三种关联图的拉普拉斯谱第一种关联图G,的拉普拉斯谱,已知其邻接矩阵为A1,拉普拉斯矩阵为Li,特征多项式为P(x)=IxI-L,I。A+(x-m-r)I111(x-1)1010(x-1)1130烟台大学学报(自然科学与工程版)第37 卷mA+(x-m-r+11(x-1)mlA+(x-m-r+一一n-1(x-1)II(r-;+x-m-r+十1-i0n-
9、1(x-1)n(m-1)为+./m+1+)-4l=,n-1;(m-1):1。i-0所以,图G,的拉普拉斯特征值为0(x-1)10-(m+1+入,)x+入;o200(-1)Imm(x-.1)二2下面求第二种关联图G,的拉普拉斯谱,已知其邻接矩阵为A2,拉普拉斯矩阵为L,特征多项式为P,(x)=Ixl-L,l。I I-L2 I=A+(x-m-r)11(-m)111(x-m)Il11(-1)A+(x-m-r-1)1(-m)I(x-m)I1.1三110(-1)A+(x-m-r-1)I1(x-m-1)I0(x-m)I(1-x+m)I(1-x+m)Il10(-1)(x-m-1)(m-1)A+(x-m-r-
10、1)l110(x-m)I-1(1-x+m)I二10(-1)(x-m-1)(m-1)0-A-(-m-r-1)I.(11.(x-m)I-1(1-x+m)I-(x-m)IA+(x-m-r-1)I二第2 期(-1)(-m-1)(n-1I)(-1)(x-m-1)n(m-)I-(x-m-r-1)(-1)-(x-m-1)I-A(x-1)1=(-1)(-m-1)(m-1)于越,等:一些关联图的拉普拉斯谱和基尔霍夫指标110100n-1-(-m-r-1)(x-1)-(-m-1)-(r-,)(x-1)=0(-1)(x-m-1)(m-1)131(-m)I-1-(x-m-r-1)(x-1)-(x-m-1)I-A(x-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一些 关联 拉普拉斯 基尔霍夫 指标
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。