重组图的拉普拉斯谱毕业论文

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

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

2、然后研究了两个完全图的重组图删去一条边所得的图的Laplace谱，通过谱之间的比较得出相应的结论，同时推广研究了个完全图的重组图的情形。关键词：Laplace谱，重组图，完全图21南通大学毕业论文ABSTRACTLetbeasimplegraphwiththevertexsetandtheedgeset.Weusetoexpressthenumberofedgesbetweenvertexandof,andcallastheadjacencymatrixof,viewtheeigenvaluesofastheadja

3、cencyspectrumof.Thedegreematrixisthediagonalmatrixwhosei-thdiagonalentryisthedegreeofvertexiin.TheLaplacematrixofisgivenby.TheresearchonthecharacteristicsvalueofLaplacematrix,isanimportantpartofalgebraicgraphtheory.Inthispaper,westudytheLaplacespectrumofthereco

4、mbinantgraphoftwocompletegraphs,andtheLaplacespectrumoftherecombinantgraphoftwocompletegraphs,furthermore,weobtainsomeresultsbycomparison.Furthermore,westudytheLaplacespectrumoftherecombinantgraphofpcompletegraphs.Keywords:Laplacespectrum,recombinantgraph,compl

5、etegraph21南通大学毕业论文目录摘要IABSTRACTII目录III第一章绪论41.1引言41.2基本概念及已有结果41.3本文主要结果6第二章重组图的Laplace谱72.1两个完全图的重组图的Laplace谱72.2去掉两个完全图的重组图中Kk内一条边的情况92.3去掉两个完全图的重组图中内一条边的情况122.4去掉两个完全图的重组图中与之间的一条边的情况142.5个完全图的重组图的情形18第三章归纳19参考文献20致谢2121南通大学毕业论文第一章绪论1.1引言图谱理论的主要目标是把图的重要结构性质和它

6、的特征值联系起来，它在图划分、排名、网络病毒传播和聚集等方面都有一些应用[1]。图的特征值的研究是组合数学的一个重要组成部分。从历史观点上来说，图的谱和结构之间的第一个关系是在1876年基尔霍夫证明了他著名的矩阵-树定理时发现的[2]。图谱理论的主要原理是把图的重要不变量和图谱联系起来。通常，像色数和独立数这样难以计算的不变量，用含特征值的表达式比较它们是很有效的。在[1]中，也给出一些图谱和它的结构的关系以及这些关系在图划分、排名、网络病毒传播和聚集等领域的一些实际应用。对于图的特征值的其他应用，可参见[1，3，4

7、，5]。更多图的特征值的结果，可以看Cevtkovicetal.的专著[6，7](邻接矩阵的特征值)，Mohar的综述[8]（拉普拉斯矩阵的特征值），Godsil和Royle的专著[9]（邻接矩阵和拉普拉斯矩阵的特征值）或者是Chung的书[10]（标准拉普拉斯矩阵的特征值）。1.2基本概念及已有结果下面是一些相关定义：定义1.1：既无环边也无重边的图称为简单图。定义1.2：任意两点间都有一条边的简单图称为完全图，阶完全图记为。定义1.3：设简单图都包含一个子图与图同构，把的顶点看成是一样的，所得的简单图称为基于的重

8、组图，记为。定义1.4：由一个图删去其顶点的子集,同时删去他们关联的边所得的图，称为这个图的诱导子图。定义1.5：设图为简单图，即图不包含重边与环，的顶点集为，顶点的度为，的邻接矩阵为是一个实对称矩阵，定义如下：，当时，如果顶点与相邻，则，否则。定义1.6：图G的Laplace矩阵定义为：,其中为21南通大学毕业论文的顶点度数构成的对角矩阵，称