重组图的拉普拉斯谱

《重组图的拉普拉斯谱》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、本科毕业论文题目重组图的拉普拉斯谱作者：唐晶专业：数学与应用数学（师范）指导教师：吕大梅完成日期：2014年5月南通大学本科毕业论文题目：重组图的拉普拉斯谱姓名：唐晶指导教师：吕大梅专业：数学与应用数学（师范）南通大学理学院2014年5月摘要设是一个顶点集为，边集为的阶简单图。用表示中与之间的边数，称为的邻接矩阵，矩阵的特征值就称为的邻接谱，度矩阵为的顶点度数构成的对角矩阵。图的拉普拉斯矩阵定义为：。Laplace矩阵的研究是代数图论的重要组成部分。本文着重研究了两个完全图的重组图的Laplace谱，然后研究了两个完全图的重组图删去一条边所得的图的

2、Laplace谱，通过谱之间的比较得出相应的结论，同时推广研究了个完全图的重组图的情形。关键词：Laplace谱，重组图，完全图ABSTRACTLetbeasimplegraphwiththevertexsetandtheedgeset.Weusetoexpressthenumberofedgesbetweenvertexandof,andcallastheadjacencymatrixof,viewtheeigenvaluesofastheadjacencyspectrumof.Thedegreematrixisthediagonalmatrix

3、whosei-thdiagonalentryisthedegreeofvertexiin.TheLaplacematrixofisgivenby.TheresearchonthecharacteristicsvalueofLaplacematrix,isanimportantpartofalgebraicgraphtheory.Inthispaper,westudytheLaplacespectrumoftherecombinantgraphoftwocompletegraphs,andtheLaplacespectrumoftherecombin

4、antgraphoftwocompletegraphs,furthermore,weobtainsomeresultsbycomparison.Furthermore,westudytheLaplacespectrumoftherecombinantgraphofpcompletegraphs.Keywords:Laplacespectrum,recombinantgraph,completegraph目录摘要IABSTRACTII目录III第一章绪论41.1引言41.2基本概念及已有结果41.3本文主要结果6第二章重组图的Laplace谱72.1

5、两个完全图的重组图的Laplace谱72.2去掉两个完全图的重组图中Kk内一条边的情况92.3去掉两个完全图的重组图中内一条边的情况122.4去掉两个完全图的重组图中与之间的一条边的情况142.5个完全图的重组图的情形18第三章归纳19参考文献20致谢21第一章绪论1.1引言图谱理论的主要目标是把图的重要结构性质和它的特征值联系起来，它在图划分、排名、网络病毒传播和聚集等方面都有一些应用[1]。图的特征值的研究是组合数学的一个重要组成部分。从历史观点上来说，图的谱和结构之间的第一个关系是在1876年基尔霍夫证明了他著名的矩阵-树定理时发现的[2]。

6、图谱理论的主要原理是把图的重要不变量和图谱联系起来。通常，像色数和独立数这样难以计算的不变量，用含特征值的表达式比较它们是很有效的。在[1]中，也给出一些图谱和它的结构的关系以及这些关系在图划分、排名、网络病毒传播和聚集等领域的一些实际应用。对于图的特征值的其他应用，可参见[1，3，4，5]。更多图的特征值的结果，可以看Cevtkovicetal.的专著[6，7](邻接矩阵的特征值)，Mohar的综述[8]（拉普拉斯矩阵的特征值），Godsil和Royle的专著[9]（邻接矩阵和拉普拉斯矩阵的特征值）或者是Chung的书[10]（标准拉普拉斯矩阵的

7、特征值）。1.2基本概念及已有结果下面是一些相关定义：定义1.1：既无环边也无重边的图称为简单图。定义1.2：任意两点间都有一条边的简单图称为完全图，阶完全图记为。定义1.3：设简单图都包含一个子图与图同构，把的顶点看成是一样的，所得的简单图称为基于的重组图，记为。定义1.4：由一个图删去其顶点的子集,同时删去他们关联的边所得的图，称为这个图的诱导子图。定义1.5：设图为简单图，即图不包含重边与环，的顶点集为，顶点的度为，的邻接矩阵为是一个实对称矩阵，定义如下：，当时，如果顶点与相邻，则，否则。定义1.6：图G的Laplace矩阵定义为：,其中为的

8、顶点度数构成的对角矩阵，称为度矩阵。定义1.7：矩阵的特征值是使得存在一个非零向量解为。每一个非零解称为对应特征值的特征向