【摘 要】
:
设G是一个简单图,M=M(G)是按照某种规定所定义的与G相联系的图矩阵,把利用M的特征值来刻画图G的组合结构的理论称为图谱理论(M-谱理论).定义det(xI-M)为图G的M-特征多项式,其中I为单位矩阵.M-特征多项式的特征根称为图G的M-特征值,由G的所有M-特征值构成的多重集称为M-谱,简记为SpecM(G).图G的最大M-特征值称为M-谱半径.关于图矩阵M具有相同谱的图称为M-同谱图,与G
论文部分内容阅读
设G是一个简单图,M=M(G)是按照某种规定所定义的与G相联系的图矩阵,把利用M的特征值来刻画图G的组合结构的理论称为图谱理论(M-谱理论).定义det(xI-M)为图G的M-特征多项式,其中I为单位矩阵.M-特征多项式的特征根称为图G的M-特征值,由G的所有M-特征值构成的多重集称为M-谱,简记为SpecM(G).图G的最大M-特征值称为M-谱半径.关于图矩阵M具有相同谱的图称为M-同谱图,与G图M-同谱但不同构的所有图称为图G的M-同谱类.如果G不存在M-同谱但非同构的图时,则称G是由M-谱确定的.即对任意的图H,SpecM(H)=SpecM(G)蕴含着H~=G,简记为DMS-图.特别地,当M等于邻接矩阵A、拉普拉斯矩阵L=D-A和无符号拉普拉斯矩阵Q=D+A时,便是图G的A-谱、L-谱以及Q-谱的相关概念,这里D为G的度对角矩阵.图的谱特征问题主要考虑图矩阵的谱性质和谱刻画问题.从目前的研究状况来看,图矩阵主要包括关联矩阵、邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵、距离矩阵、标准拉普拉斯矩阵、Seidel矩阵、广义邻接矩阵等.对于谱性质而言,谱半径及其相关参数的研究一直是图谱问题研究的重要组成部分.同时,第二大、第三大特征值以及某些图矩阵的最小、次小特征值也是比较热门的研究课题.谱刻画问题主要是通过某些谱特性来刻画具有这种谱特性的图,其中谱确定问题是谱刻画中十分棘手的问题之一,也是整个图谱问题研究的核心问题.从已知的DMS-图来看,谱确定的研究主要集中在三类图上.第一类是结构相对简单,对称性较好的图;第二类是至多含有四种不同度数的非正则图;第三类是能被度序列唯一确定其形状的图.然而,对于上述三类图而言,要判断任意给定的图是否是DMS-图也是一个相当困难的问题.本文主要借助于图结构、组合理论、矩阵理论、闭道数公式、特征多项式、特征向量、特征值及其界、谱矩量和度序列重点研究了一些图类的谱确定性问题,同时也考虑了其他一些图类的谱性质.在图谱确定方面,我们主要围绕“一个图是否是谱确定的?如若不是,能否确定出其同谱类?”这两个问题展开.文中第二章、第三章、第四章分别主要研究了一些图类的邻接谱、拉普拉斯谱以及无符号拉普拉斯谱的谱确定问题,第五章通过图运算构造了若干图的无穷同谱类.本文的具体组织结构如下:第一章主要介绍了图谱理论的研究背景,接着引入了本文所用到的符号与概念.随后对谱特征问题的起源以及研究现状作了概述.最后简要地介绍了本文的主要结论.第二章首先通过考虑主向量得到了杠铃图(barbell graph)A-谱半径的一个比较紧的上界与下界;紧接着,我们给出了杠铃图的A-特征多项式谱半径方程.其次,考虑了T-形树(T-shape tree)线图的A-谱刻画,我们证明了T-形树线图除一些图类外是由A-谱确定的.同时,给出了这些图类的同谱图.第三章首先考虑了图的L-谱与子图填充数(packing number)之间的关系.其次,我们研究了T-形树的线图、Π-形树(Π-shape tree)与风轮图(windwheel graph)的L-谱刻画.在T-形树线图的L-谱刻画中,证明了两个T-形树的线图同谱一定是同构的;在Π-形树的L-谱刻画中,我们证明了其中一类Π-形树除一个无穷同谱类外是L-谱确定的.有趣的是,在这类Π-形树中我们找到了树图的一个无穷L-同谱类.在风轮图的L-谱刻画中,证明了所有风轮图是L-谱确定的.最后,我们主要研究了一些L-谱确定的可图度序列及其对应的图.第四章首先研究了Q-谱的一些基本性质,这些性质可以看做是A-谱性质在Q-谱方面的平移.其次证明了风轮图是Q-谱确定的,并由此结论推知友谊图(friendship graph)也是由Q-谱确定的.第五章根据图G1,G2和G3,分别确定了剖分点-边邻接点-冠图(subdivision vertex-edge neighbourhood vertex-corona)GS1??(GV2∪GE3)与剖分点-边邻接边-冠图(subdivision vertex-edge neighbourhood edge-corona)GS1(GV2∪ GE3)的A-谱,L-谱以及Q-谱.作为对它们的应用,我们构造了若干无穷同谱类.与此同时,我们还给出了图GS1??(GV2∪ GE3)与GS1(GV2∪ GE3)的生成树的数目.
其他文献
复杂背景条件下的红外弱小目标的检测具有非常重大的理论意义和实际应用价值,尤其是在军事领域,常用于红外侦察、制导及预警等方面。由于红外弱小目标所特有的面积小、亮度低、与周围背景之间的对比度弱等特点,在原始红外图像中,复杂背景下的高亮背景、背景边缘和噪声等很容易淹没真实红外弱小目标,导致目前针对复杂背景条件下的红外弱小目标检测算法存在检测率低、虚警率高等问题。当前,基于人类视觉系统Human Visu
辐射扩散方程的数值模拟对于受控约束核聚变、等离子体物理、天体物理等各类实际的工程和物理问题的研究具有重要意义.由于工程上对于这类可压的辐射流体力学问题界面的分辨精度要求很高,通常采用拉格朗日法进行模拟.数值模拟的网格可能随着流体的运动而扭曲变形,能量扩散的模拟就需要在扭曲的网格上进行.本文以扭曲网格上的辐射扩散方程的保正和保极值有限体积格式为研究对象,主要做了以下的工作:首先,我们构造三维扩散方程
复杂网络是指具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络,因其能够帮助人们更好的理解和研究事物的本质,近年来吸引了国内外众多学者的关注.神经网络作为复杂网络的代表,已经被成功地应用于模式识别、智能控制和组合优化等领域.对由多个神经网络所构成的耦合神经网络进行同步分析和控制,是当前复杂网络动力学研究的热点问题之一.本文结合复杂网络理论、现代控制理论和Lyapunov稳定性理论,研
随着多处理器计算机系统的大规模网络在许多领域的普及,许多理论问题引起人们广泛的关注,其中之一就是网络容错的问题。网络的容错性是指网络在发生故障时保持连通或保持某些性质的能力。网络拓扑结构经常以(有向)图,甚至以超图为模型,因此可以使用(有向)图或超图的某些容错参数来评估网络的性能。由于对称网络具有许多理想的性质,对称图的容错性也是一个重要的研究方向。本文主要研究关于边连通性的(有向)图或超图的一些
代数图论是通过运用线性代数、群论、组合设计等知识来分析图的代数性质,从而刻画图的组合结构的一门学科,它是图论研究的一个重要分支.作为代数图论的一个重要研究方向,图谱理论主要研究与图相关的矩阵的特征多项式、特征值、特征子空间等相关的代数参数性质,以及它们与图结构属性之间的关系.高度对称图是指具有较强对称性的图,从代数上看就是具有较大自同构群的图,它们往往具有良好的代数组合性质,是连接图论、组合设计和
连通性和Hamilton性是图论中的两个经典的研究课题.连通性与互联网络的容错性存在着非常紧密的联系.Hamilton性是网络设计时最基本的要求之一.生成连通性是图的连通性和Hamilton性的融合与推广.本文主要研究图的结构连通性,结构容错Hamilton性以及生成连通性.第一章,阐述本文的研究背景,现状与进展,相关概念以及网络模型.第二章,主要研究几类著名网络的结构连通性和子结构连通性.第一节
代数图论是图论学科的重要研究领域之一,主要运用代数方法来解决图论问题.代数图论有三个主要分支,分别为图与线性代数,图与群论,图不变量.其中图与线性代数的研究核心是图的谱理论.图谱理论是通过研究与图相关的矩阵(邻接矩阵,拉普拉斯矩阵,无符号拉普拉斯矩阵,正规拉普拉斯矩阵和距离矩阵等)的谱的性质来研究图的组合性质.图谱理论研究兴起于20世纪50-60年代,近20-30年来得到迅猛的发展,它是图论,组合
Grobner 基理论是由 Buchberger,Shirshov 和 Bergman 独立引进的.Buchberger 创建的交换代数的Grobner基理论为解决交换代数中的约化问题提供了非常有效的方法.Bergman把Buchberger的理论推广到结合代数上.在李代数上的类似理论由Shirshov创建.后来,Bokut证明了 Buchberger和Bergman的Grobner基理论其实是S
本文考虑了与一个半有限von Neumann代数对应的非交换Lorentz型空间,包含四部分内容.第一部分介绍了文章的研究背景,非交换积分理论的基础知识以及本文的主要结果.第二部分研究了非交换弱Lp空间,给出了非交换弱Lp空间对偶空间的具体形式.在这一部分中还讨论了非交换弱Lp空间上的紧左(右)乘算子.第三部分研究了非交换加权Lorentz空间的对偶空间,得到了类似于经典的加权Lorentz空间对
当今,计算已成为继理论和实验之后的第三种不可或缺的科学研究方法。并且在许多情况下,由于科学计算不受外部因素和实验器材影响的灵活性,它能够最大程度以最小的代价获得与理论和实验相当的结果。这个使得计算在当今科学领域占有非同一般的统治地位。反应扩散方程是一类重要的偏微分方程,在物理、生物、材料以及社会科学中都有广泛的应用。并且,反应扩散方程有着比其他偏微分方程更加好的特性,例如极值原理、比较原理、不变集