特征值个数较少的图的谱刻画研究

来源 :新疆大学 | 被引量 : 0次 | 上传用户:smashnj
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
代数图论是图论学科的重要研究领域之一,主要运用代数方法来解决图论问题.代数图论有三个主要分支,分别为图与线性代数,图与群论,图不变量.其中图与线性代数的研究核心是图的谱理论.图谱理论是通过研究与图相关的矩阵(邻接矩阵,拉普拉斯矩阵,无符号拉普拉斯矩阵,正规拉普拉斯矩阵和距离矩阵等)的谱的性质来研究图的组合性质.图谱理论研究兴起于20世纪50-60年代,近20-30年来得到迅猛的发展,它是图论,组合与代数的一个交叉研究领域,是代数图论的重要研究分支.1957年,L.Collatz和U.Sinogowitz的数学论文”Spektren Endhcher Grafen”被视为图谱理论研究的开端,经过50多年的发展,它在图论,物理,量子化学,计算机科学,互联网技术等许多方面都有广泛的应用.图的谱特征往往可以反映出图的结构特征,而不同特征值输数目较少的图通常具有特殊的结构特征(如高度对称性)与较好的组合性质.目前,对含有三个或四个不同特征值的图的谱刻画已取得许多重要进展.然而,对于给定的k<7,恰有k个不同特征值的图的谱刻画问题还远未解决或未完整解决.基于此,本文研究不同特征值数目较少的图的谱刻画问题,主要包括有一个拉普拉斯特征值重数较大的图的谱刻画和邻接特征值数目较少的道半正则图的谱刻画.本文分为三章,具体结构如下:第一章主要介绍了图谱理论的研究背景,接着引入了本文所用到的符号与概念.随后对问题的研究背景以及研究进展作了概述.最后介绍了本文的主要结果.第二章研究了拉普拉斯特征值重数mL(μ)≥n-4的图的谱刻画.首先刻画了集合GL(n,n-3)中的图,即,有一个拉普拉斯特征值是n-3重的图.该类图具有三个或四个不同的拉普拉斯特征值.通过排除若干禁用子图得出结论,GL(n,n-3)中的图,除了Gn,r外均为余图(cograph),即不含导出P4的图,从而确定了所有这类图.最终与Mohammadian和Tayfeh-Rezaie的结果(GL(n,n-3)中有四个不同拉普拉斯特征值的图的谱刻画)构成了GL(n,n-3)中图类的完整刻画.其次对集合GL+(n,n-4)中的图,即拉普拉斯谱半径为n-4重的图进行了研究.通过排除所有禁用子图得出结论,拉普拉斯谱半径为n-4重的图均为余图(cograph),从而给出了GL+(n,n-4)(n≥8)中的图的完整刻画.进一步地,我们给出了GL-(n,n-4)(n≥8),即次小拉普拉斯特征值为n-4重的图的完整刻画.同时证明了,所刻画的图类都是DLS图(由拉普拉斯谱唯一确定的图).第三章研究了道半正则图的邻接谱刻画.首先给出了道半正则图的定义,即,设G是一个(V1,V2)-半正则图,对任意l>0,从v∈Vi(i=1或2)出发的l长闭道数与v的选取无关,则称G是道半正则图.一个道半正则图一定是半正则图,但是反之则不然.我们证明了,道半正则图一定具有半正则二等价划分,反之,给出了一个半正则二等价划分图成为道半正则图的充分条件.其次重点刻画了具有四个不同特征值的道半正则非偶图.令GW(t,s)表示具有t个不同特征值,其中s个是单特征值(重数为1)的连通非偶道半正则图集合.令GW(t,s;λ)表示含特征值λ的集合GW(t,s)的子集.先确定了集合GW(3,s)(s≤2)中的图,给出了GW(4,3)中图的完整刻画;之后讨论了GW(4,2)中图的性质,重点刻画了GW(4,2;0)中的图类.最后研究了道半正则偶图的相关性质,就偶图的零度(特征值0的重数)达到最大,最小和次小时,刻画了具有五个不同特征值的道半正则偶图.进一步地,针对零度为其他情况时,讨论了这类偶图的存在性并给出了一个必要条件.
其他文献
1928年,Dirac发表了相对论量子力学的运动方程,并预言了正电子的存在。Heisenberg发现正电子的存在意味着量子真空极不稳定,并给出了Maxwell拉氏量的量子修正,进而预言了众多非线性量子效应。其中,真空在外加电磁场的作用下产生正负电子对,也叫做Schwinger对产生,是量子电动力学极其重要的非微扰预言之一。理论上,真空对产生的研究不仅是在非微扰领域有着重要意义,而且它作为经典场和量
代数图论是图论研究的一个重要领域,它广泛的应用于生命科学,计算机网络,组合优化,生物化学,分子理论等学科中.图的谱刻画理论是代数图论的一个重要的研究方向,它用矩阵论、组合设计、群论等知识来研究图与图矩阵的特征多项式、特征值以及特征向量有关的各种代数参数、组合参数,从而得到谱与图的结构性质之间的关系.因此,利用图的谱来确定图,即图的谱确定问题是图的谱刻画理论中的一个主要课题.所以刻画具有较少的正特征
改革开放40年来,中国经济取得了持续的高速增长,国内生产总值由1978年的3679亿元增长到2018年的91.93万亿元,年均实际增速达到9.5%,远高于同期世界经济增速。然而,长期以来,中国经济呈现出粗放型增长方式的特点,由此也引发了污染加剧、雾霾加重等一系列环境问题,使得经济增长变得不可持续。特别是2010年以来,中国经济增速下滑的压力一直比较大,经济“脱实向虚”、产能过剩等问题互相交织,使得
分数阶偏微分方程是指未知变量中含有分数幂的方程,它比传统的整数阶方程更适合于描述具有各种材料的记忆性和遗传性的现实问题,例如,电解化学、凝聚态物理、半导体物理、湍流和粘弹性系统、生物数学和统计力学、光学和热系统、材料和信号处理等领域.分数阶对流扩散问题作为在科学和工程计算模拟中应用最广泛的问题,许多实际的流体流动过程,如传热、流体力学、地下水污染输运扩散过程和油藏、质量和能量传输以及全球天气模拟等
复杂背景条件下的红外弱小目标的检测具有非常重大的理论意义和实际应用价值,尤其是在军事领域,常用于红外侦察、制导及预警等方面。由于红外弱小目标所特有的面积小、亮度低、与周围背景之间的对比度弱等特点,在原始红外图像中,复杂背景下的高亮背景、背景边缘和噪声等很容易淹没真实红外弱小目标,导致目前针对复杂背景条件下的红外弱小目标检测算法存在检测率低、虚警率高等问题。当前,基于人类视觉系统Human Visu
辐射扩散方程的数值模拟对于受控约束核聚变、等离子体物理、天体物理等各类实际的工程和物理问题的研究具有重要意义.由于工程上对于这类可压的辐射流体力学问题界面的分辨精度要求很高,通常采用拉格朗日法进行模拟.数值模拟的网格可能随着流体的运动而扭曲变形,能量扩散的模拟就需要在扭曲的网格上进行.本文以扭曲网格上的辐射扩散方程的保正和保极值有限体积格式为研究对象,主要做了以下的工作:首先,我们构造三维扩散方程
复杂网络是指具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络,因其能够帮助人们更好的理解和研究事物的本质,近年来吸引了国内外众多学者的关注.神经网络作为复杂网络的代表,已经被成功地应用于模式识别、智能控制和组合优化等领域.对由多个神经网络所构成的耦合神经网络进行同步分析和控制,是当前复杂网络动力学研究的热点问题之一.本文结合复杂网络理论、现代控制理论和Lyapunov稳定性理论,研
随着多处理器计算机系统的大规模网络在许多领域的普及,许多理论问题引起人们广泛的关注,其中之一就是网络容错的问题。网络的容错性是指网络在发生故障时保持连通或保持某些性质的能力。网络拓扑结构经常以(有向)图,甚至以超图为模型,因此可以使用(有向)图或超图的某些容错参数来评估网络的性能。由于对称网络具有许多理想的性质,对称图的容错性也是一个重要的研究方向。本文主要研究关于边连通性的(有向)图或超图的一些
代数图论是通过运用线性代数、群论、组合设计等知识来分析图的代数性质,从而刻画图的组合结构的一门学科,它是图论研究的一个重要分支.作为代数图论的一个重要研究方向,图谱理论主要研究与图相关的矩阵的特征多项式、特征值、特征子空间等相关的代数参数性质,以及它们与图结构属性之间的关系.高度对称图是指具有较强对称性的图,从代数上看就是具有较大自同构群的图,它们往往具有良好的代数组合性质,是连接图论、组合设计和
连通性和Hamilton性是图论中的两个经典的研究课题.连通性与互联网络的容错性存在着非常紧密的联系.Hamilton性是网络设计时最基本的要求之一.生成连通性是图的连通性和Hamilton性的融合与推广.本文主要研究图的结构连通性,结构容错Hamilton性以及生成连通性.第一章,阐述本文的研究背景,现状与进展,相关概念以及网络模型.第二章,主要研究几类著名网络的结构连通性和子结构连通性.第一节