论文部分内容阅读
代数图论是将图的性质转变为代数性质,用代数的结论与方法,来推断关于图的理论,作为代数图论的重要研究领域,谱图理论可以看作是线性代数的一种应用,通过矩阵的特征值以及特征向量自然的与图联系起来. 本文主要讨论两个问题: (i)图的谱整变化 给定一个简单图G,当G进行局部改变,删除或添加一条边或一个顶点时,其谱发生了如下情形的变化: 情形1:有一个特征值发生了整数变化,而其余的n-1个特征值均保持不变; 情形2:有两个特征值发生了整数变化,而其余的n-2个特征值均保持不变. 我们称该变化为图的谱整变化. (ii)哈密尔顿图的谱刻画 设图G为n阶简单图,若存在一条路,包含了G中所有顶点,则称该路为哈密尔顿路,若哈密尔顿路的起点与终点相同,则构成了一个圈,并称该圈为哈密尔顿圈,包含哈密尔顿圈的图称为哈密尔顿图.如果G中任意两个顶点都存在一条哈密尔顿路相连,则称该图为哈密尔顿连通图. 判断一个图是否是哈密尔顿图是一个困难问题,现已经有一些经典方法,本文将用谱图理论来判断该问题. 全文分为三章.第一章首先介绍了谱图的研究背景,其次给出了文中的基本概念和符号以及本文的主要结论;第二章研究拉普拉斯的谱整变化和无符号拉普拉斯的谱整变化,其中重点讨论了无符号拉普拉斯谱发生整数变化时的条件;第三章研究哈密尔顿图的谱刻画,用谱图理论来判断图的哈密尔顿性,首先用G补图的能量来判断图G包含哈密尔顿路、哈密尔顿圈以及是哈密尔顿连通图的充分条件,其次利用平衡二部图GBPT的拟补图的能量来判断GBPT含有哈密尔顿圈的充分条件.