两类图的谱确定问题研究

发布时间：2017-05-03 16:17

  本文关键词：两类图的谱确定问题研究，由笔耕文化传播整理发布。

【摘要】：图谱理论起源于理论化学家和物理学家为解决一类偏微分方程的数值解而建立起来的一套离散的图模型.它在物理学、化学、计算机科学及通信网络等方面都有着十分广泛的应用.图谱理论主要是利用矩阵理论中的方法和技巧,来研究图矩阵(如邻接矩阵A,拉普拉斯矩阵L=D-A,无符号拉普拉斯矩阵Q=D+A,规范拉普拉斯矩阵?L=D-12 LD-12,Seidel矩阵S=J-2A-I等)的谱(特征值及其重数)的性质进而用这些性质来反映图的一些结构性质和拓扑性质,它是代数图论中一个重要的研究领域.图谱理论研究的内容相当广泛,概括起来主要包括两个方面,一个方面是图的谱特征,主要涉及确定图的谱及其分布,确定谱的性质,谱与图的各种参数(例如直径,色数,围长,连通度等)之间的关系等;另一个方面是谱的图特征,主要是根据谱的性质刻画图等,其中图的谱确定问题是其研究的重点.两个图同谱是指它们有相同的谱.两个图同谱不一定同构,但是两个图同构则一定同谱.一个图G被称作是由谱确定的,如果对于任意一个图H,由H与G同谱蕴含着H与G同构.图的谱确定问题是指,对于一个图,首先考虑该图是否由谱确定;其次如果该图不能由谱确定则考虑找出它所有的同谱图.图的谱确定问题最早由G¨unthard和Primas提出,接着van Dam和Haemers发表了两篇综述文章对此问题进行了概括总结,并给出了很多谱确定图及图同谱的必要条件.但是“哪些图是由它的谱所确定的”这个问题还远远没有解决.从已经取得的研究结果来看,谱确定问题主要考虑具有一定特性的图,如对称性较好的图、谱半径在一定范围之内的图、特征值个数较少的图、非正则且度序列中不同度数较少的图(例如几乎正则图)等.虽然目前已经知道了很多谱确定图,但是要考虑一般图是否由谱所确定还是有很大难度的.在本文中,我们主要考虑两类图的谱确定问题,一类是第二大特征值小于等于1的单圈图的邻接谱确定问题,另一类是4-玫瑰图的拉普拉斯谱确定及无符号拉普拉斯谱确定问题.本文结构安排如下:第一章首先简要介绍了图谱理论的研究背景及应用.其次给出了本文要用到的基本概念和符号.随后对谱确定问题的来源,国内外研究现状及发展动态做了概括总结.此外,我们还引入了一些研究谱确定问题常用的工具、方法及结论.最后介绍了本文的主要研究工作.对第二大特征值不超过1的图的刻画已经取得了很多研究成果,本论文的第二章则从图的谱确定角度来研究这些图.我们主要考虑第二大特征值小于等于1的单圈图的邻接谱确定问题.首先我们对第二大特征值小于等于1的所有单圈图进行分类并且证明了具有这一性质的所有单圈图之间不是邻接同谱的.其次我们给出了与具有这一性质的图邻接同谱的必要条件并且找到了一些禁止子图.再次,我们根据分类逐一考虑了这些图的谱确定性.其中重点证明了图Gt,s是由它的邻接谱所确定的.最后,利用禁止子图条件证明了在第二大特征值小于等于1的单圈图中,除了四个图外,其它的图都是由它们的邻接谱所确定的.此外,我们还给出了不能由邻接谱所确定的那些图的同谱对.具有p个花瓣的图(简称为p-玫瑰图)是指p个圈恰有一个公共顶点的图,“玫瑰图”的得名由玫瑰曲线而来.玫瑰图的谱确定问题一直受到人们的关注.第三章我们考虑了4-玫瑰图的拉普拉斯谱确定性.首先我们介绍了两个图L-同谱的一个必要条件.其次根据4-玫瑰图的组合结构给出了它的拉普拉斯特征多项式中倒数第三项的系数.另外,我们还给出了4-玫瑰图的拉普拉斯特征多项式的表达式.最后根据4-玫瑰图的拉普拉斯谱半径的界得出L-同谱于4-玫瑰图的图可能的度序列.最终证明了4-玫瑰图是由它的拉普拉斯谱所确定的.第四章我们讨论了4-玫瑰图的无符号拉普拉斯谱确定性.我们首先引进了一个新的Q-同谱不变量并给出了4-玫瑰图的无符号拉普拉斯特征多项式的表达式.其次介绍了Q-同谱于4-玫瑰图的图可能的形.再次,利用无符号拉普拉斯谱半径的界讨论了Q-同谱于4-玫瑰图的图可能的度序列.最后利用Q-同谱图的新的不变量和图中三角形的数目证明了4-玫瑰图是由它的无符号拉普拉斯谱所确定的.
【关键词】：邻接(拉普拉斯 无符号拉普拉斯)谱确定 第二大特征值 单圈图 r-圈图 4-玫瑰图
【学位授予单位】：新疆大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要2-4
• Abstract4-9
• 第一章 绪论9-26
• 1.1 图谱理论的研究背景及应用9-11
• 1.2 基本概念与常用符号11-14
• 1.3 谱确定问题的起源、研究现状及发展动态14-17
• 1.4 谱确定问题的研究工具、方法及结论17-23
• 1.5 本文的主要研究工作23-26
• 第二章 第二大特征值小于等于1的单圈图的邻接谱确定26-43
• 2.1 准备知识27-28
• 2.2 集合U (λ_2) 中的图相互是不同谱的28-32
• 2.3 集合U_3(λ_2) 中的图的邻接谱确定32-38
• 2.4 集合U4(λ_2) 和U5(λ_]2) 中的图的邻接谱确定38-43
• 第三章 4-玫瑰图的拉普拉斯谱确定43-56
• 3.1 准备知识44-45
• 3.2 4-玫瑰图的拉普拉斯特征多项式中倒数第三项的系数45-47
• 3.3 4-玫瑰图的拉普拉斯特征多项式47-51
• 3.4 4-玫瑰图是DLS的51-56
• 第四章 4-玫瑰图的无符号拉普拉斯谱确定56-68
• 4.1 准备知识56-57
• 4.2 没有两个非同构的 4-玫瑰图是Q-同谱的57-62
• 4.3 4-玫瑰图是DQS的62-68
• 参考文献68-77
• 科研成果77-79
• 致谢79-80

【相似文献】

中国期刊全文数据库 前10条

1 李军;关于价格中的盈利确定问题[J];青岛教育学院学报;1999年02期

2 李万军;人寿保险中赔偿金的确定问题[J];数理统计与管理;1994年03期

3 Carolyn Hunsaker;郭林海;;区域监测的生态指标[J];地理译报;1993年01期

4 王琳,牛晓华;项目经济评价中有关参数确定问题的思考[J];技术经济与管理研究;1998年01期

5 姚建民;灰色预测值精度的确定问题[J];农业系统科学与综合研究;1987年03期

6 刘扬;工业产品出厂价格指数的权数确定问题[J];统计研究;1988年03期

7 俞建;;关于最可靠控制系统综合的几点注记[J];贵州工学院学报;1983年03期

8 王新驰;经济指数中数量变动及其影响的剖析[J];统计研究;1986年01期

9 陈雄,潘永泉;轧制单元数确定问题的研究[J];控制与决策;1998年05期

10 刘波;赵毅;郭天祥;周云;王相南;;生态学领域中的高精度参数确定问题研究[J];华北电力大学学报(自然科学版);2007年05期

中国重要会议论文全文数据库 前1条

1 梁洛辉;;关于土地使用权出让金确定问题的探讨[A];土地市场与土地资源优化配置——中国土地学会第四次会员代表大会学术年会论文集[C];1994年

中国重要报纸全文数据库 前1条

1 曲荣;质量工具任你挑[N];中国质量报;2005年

中国博士学位论文全文数据库 前1条

1 马小玲;两类图的谱确定问题研究[D];新疆大学;2015年

中国硕士学位论文全文数据库 前3条

1 刘水金;多因素组合采购拍卖获胜者确定问题研究[D];重庆师范大学;2011年

2 许有磊;基于蚁群优化算法的竞胜标确定问题研究[D];清华大学;2012年

3 王卓;多重事例库系统的研究[D];东北大学;2005年

  本文关键词：两类图的谱确定问题研究，由笔耕文化传播整理发布。

，

本文编号：343346