关于图的积和多项式若干问题的研究

来源 :兰州大学 | 被引量 : 0次 | 上传用户:anny250
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
国的积和多项式是对图的邻接矩阵的特征矩阵求积和式运算而得到的多项式,即per(xI-A(G))这里A(G)是图G的邻接矩阵,I是单位矩阵.关于矩阵积和式的计算,Valiant已经证明是#P-完全问题,即使限定在(0,1)-矩阵中.因为计算上的困难,尽管图的积和多项式概念的提出已三十年有余,但该领域的研究进展非常缓慢.本文考虑了图的积和多项式的三个问题:用积和多项式确定图、图的积和多项式根的性质以及定向图的斜邻接矩阵的积和多项式.Merris等认为在区分不是树的图时积和多项式可能要比特征多项式好一些,他们发现有五对不能被特征多项式所区分的图可以被积和多项式所区分.利用积和多项式去区分图,之前并没有系统的研究.本文首先探讨在区分不是树的图时积和多项式是不是确实要优于特征多项式,或者更一般地我们去研究哪些图可以被它们的积和多项式所确定,这里一个图G称为能被它的积和多项式所确定是指对于任意与G有相同积和多项式的图H,总有H与G是同构的.我们首先给出了由图的积和多项式可确定的一些性质.利用这些性质,证明了完全国、星、正则完全二部图以及奇圈可以被它们的积和多项式所确定.然后我们表明了路、偶圈以及棒棒糖图不能被积和多项式所确定,而它们已证明均可被特征多项式所确定.如果限定在连通图中考虑,我们证明了路、不能被4整除的偶圈、奇棒棒糖图以及围长等于4的偶棒棒糖图可以被积和多项式所确定.由于积和式的定义与行列式很相似,我们考虑图的积和根(积和多项式的根)与特征根之间是不是有着相似的性质.我们知道图的特征根全为实数,二部图的特征根关于坐标原点对称,那么这些性质对于图的积和根是否也成立?本文对这些问题给出了明确的回答.我们证明了任意图不会有负的积和根;二部图没有非零的实积和根;对于至少有一条边的图,它一定存在非实的复积和根;二部图的积和根在在复平面上关于坐标实轴和虚轴对称.我们知道定向图的斜邻接矩阵在图的完美匹配计数中起着重要的作用.本文研究了定向图斜邻接矩阵的积和多项式,得到了其系数的Sachs-型公式,并将该结果推广到赋权的定向图上,这为计算一般实斜对称矩阵的积和多项式提供了一种图论的方法.我们证明了一个图的所有定向图的斜邻接矩阵有相同的积和多项式当且仅当这个图没有偶圈,进一步地,当一个图没有偶圈时,它的任意定向图的斜邻接矩阵的积和多项式恰好等于这个图的匹配多项式.最后对定向图的积和根与其底图的积和根之间的关系做了探讨.
其他文献
在乡村振兴、文化自信的时代背景下,分析了建筑现象学在宗祠建筑风貌研究中的可应用性,提出了宗祠建筑风貌内涵分类的问题,最后得出以建筑现象学理论为基础将宗祠建筑风貌组
汉江上游流域是野生鳜类资源主要分布区域之一。位于该流域的陕西安康及汉中地区翘嘴鳜养殖业处于起步阶段,其中翘嘴鳜养殖鱼苗几乎全部来自外购。由于水利设施建设和过度捕
在卡式系统的后光路中加入倾斜的平板,实现同轴透射端可见光的接收及反射端红外光的发射。该卡式系统口径为400 mm,焦距为4 000 mm,视场为±1.5′,加入平板后会给系统造成较
目的:探讨肘关节恐怖三联征的围术期护理和患肢功能康复的方法及疗效。方法:对我科收治的12例恐怖三联征患者行手术治疗及全面护理康复。结果:所有患者伤口均Ⅰ期愈合,患者均
会议
"一带一路"国家风能开发需求为我国风电产业推进跨境装备与资源开发合作带来了新机遇。风电属于资本和技术密集型行业,绿色债券要求募集资金进行封闭式管理投向绿色产业,增强
碳(C)、氮(N)和磷(P)是植物基本营养元素,在植物生长和各种生理调节机能中发挥着重要作用。当前,区域C、N、P化学计量格局及其驱动因素仍然是生态化学计量学的重要研究领域,
根据教育部<初中思想政治课课程标准>从学生思想政治素质教育评价的目的意义、评价的理论依据、评价的方法方式、评价的内容要素及其权重等四方面进行了系统的阐述.