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

本 科 毕 业 论 文题目重组图的拉普拉斯谱作 者： 唐 晶 专 业： 数学与应用数学（师范）指导教师： 吕 大 梅 完成日期： 2014年5月 南 通 大 学本 科 毕 业 论 文题目： 重组图的拉普拉斯谱 姓 名： 唐 晶 指导教师： 吕 大 梅 专 业： 数学与应用数学（师范） 南通大学理学院2014年5月南通大学毕业论文摘 要 设是一个顶点集为，边集为的阶简单图。用表示中与之间的边数，称为的邻接矩阵，矩阵的特征值就称为的邻接谱，度矩阵为的顶点度数构成的对角矩阵。图的拉普拉斯矩阵定义为：。Laplace矩阵的研究是代数图论的重要组成部分。矚慫润厲钐瘗睞枥庑赖。 本文着重研究了两个完全图的重组图的Laplace谱，然后研究了两个完全图的重组图删去一条边所得的图的Laplace谱，通过谱之间的比较得出相应的结论，同时推广研究了个完全图的重组图的情形。聞創沟燴鐺險爱氇谴净。关键词： Laplace谱，重组图，完全图ABSTRACTLet be a simple graph with the vertex set and the edge set . We use to express the number of edges between vertex and of , and call as the adjacency matrix of , view the eigenvalues of as the adjacency spectrum of . The degree matrix is the diagonal matrix whose i-th diagonal entry is the degree of vertex i in . The Laplace matrix of is given by . The research on the characteristics value of Laplace matrix , is an important part of algebraic graph theory. 残骛楼諍锩瀨濟溆塹籟。In this paper, we study the Laplace spectrum of the recombinant graph of two complete graphs, and the Laplace spectrum of the recombinant graph of two complete graphs, furthermore, we obtain some results by comparison. Furthermore, we study the Laplace spectrum of the recombinant graph of p complete graphs.酽锕极額閉镇桧猪訣锥。Key words: Laplace spectrum, recombinant graph, complete graph彈贸摄尔霁毙攬砖卤庑。目录摘 要I謀荞抟箧飆鐸怼类蒋薔。ABSTRACTII厦礴恳蹒骈時盡继價骚。目录III茕桢广鳓鯡选块网羈泪。第一章 绪 论4鹅娅尽損鹌惨歷茏鴛賴。1.1 引 言4籟丛妈羥为贍偾蛏练淨。1.2基本概念及已有结果4預頌圣鉉儐歲龈讶骅籴。1.3 本文主要结果6渗釤呛俨匀谔鱉调硯錦。第二章 重组图的Laplace谱7铙誅卧泻噦圣骋贶頂廡。2.1 两个完全图的重组图的Laplace谱7擁締凤袜备訊顎轮烂蔷。2.2 去掉两个完全图的重组图中Kk内一条边的情况9贓熱俣阃歲匱阊邺镓騷。2.3 去掉两个完全图的重组图中内一条边的情况12坛摶乡囂忏蒌鍥铃氈淚。2.4 去掉两个完全图的重组图中与之间的一条边的情况14蜡變黲癟報伥铉锚鈰赘。2.5 个完全图的重组图的情形18買鲷鴯譖昙膚遙闫撷凄。第三章 归 纳19綾镝鯛駕櫬鹕踪韦辚糴。参考文献20驅踬髏彦浃绥譎饴憂锦。致 谢21猫虿驢绘燈鮒诛髅貺庑。21第一章 绪 论1.1 引 言图谱理论的主要目标是把图的重要结构性质和它的特征值联系起来，它在图划分、排名、网络病毒传播和聚集等方面都有一些应用1。锹籁饗迳琐筆襖鸥娅薔。图的特征值的研究是组合数学的一个重要组成部分。从历史观点上来说，图的谱和结构之间的第一个关系是在1876年基尔霍夫证明了他著名的矩阵-树定理时发现的2。图谱理论的主要原理是把图的重要不变量和图谱联系起来。通常，像色数和独立数这样难以计算的不变量，用含特征值的表达式比较它们是很有效的。在1 中，也给出一些图谱和它的结构的关系以及这些关系在图划分、排名、网络病毒传播和聚集等领域的一些实际应用。对于图的特征值的其他应用，可参见1，3，4，5。更多图的特征值的结果，可以看Cevtkovic et al.的专著6，7(邻接矩阵的特征值)，Mohar的综述8（拉普拉斯矩阵的特征值），Godsil和Royle的专著9（邻接矩阵和拉普拉斯矩阵的特征值）或者是Chung的书10（标准拉普拉斯矩阵的特征值）。構氽頑黉碩饨荠龈话骛。1.2基本概念及已有结果下面是一些相关定义：定义1.1：既无环边也无重边的图称为简单图。定义1.2：任意两点间都有一条边的简单图称为完全图，阶完全图记为。定义1.3：设简单图都包含一个子图与图同构，把的顶点看成是一样的，所得的简单图称为基于的重组图，记为。輒峄陽檉簖疖網儂號泶。定义1.4：由一个图删去其顶点的子集,同时删去他们关联的边所得的图，称为这个图的诱导子图。定义1.5：设图为简单图，即图不包含重边与环，的顶点集为，顶点的度为，的邻接矩阵为是一个实对称矩阵，定义如下：，当时，如果顶点与相邻，则，否则。尧侧閆繭絳闕绚勵蜆贅。定义1.6：图G的Laplace矩阵定义为：,其中为的顶点度数构成的对角矩阵，称为度矩阵。定义1.7：矩阵的特征值是使得存在一个非零向量解为。每一个非零解称为对应特征值的特征向量。Laplace矩阵的所有特征值称为图的拉普拉斯（Laplace）谱。识饒鎂錕缢灩筧嚌俨淒。下给出几个简单图的拉普拉斯谱11。l 完全图的拉普拉斯谱： 一个n-1，n-1个-1；l 完全二部图的拉普拉斯谱：一个0，n-1个m，m-1个n，一个m+n； l 圈的拉普拉斯谱：2-2； 路的拉普拉斯谱：2-2。拉普拉斯算子矩阵的特征值按递增顺序列出：。和是的两个顶点且，从中删除行和列得到矩阵。定理1.1（矩阵-树定理）2如果和是连通图的两个顶点且，则的生成树的数目等于的绝对值。另外，的生成树的数目等于。凍鈹鋨劳臘锴痫婦胫籴。由矩阵-树定理可知：当且仅当是连通的，据此，M.Fiedler称为的代数连通度，记为12。现在我们列出图的拉普拉斯矩阵的特征值的一些简单性质51，第14章。定理1.21 设为一个简单图。则的拉普拉斯矩阵为半正定矩阵。的拉普拉斯算子的最小特征值等于0，它的重数等于的连通分支数目。图是连通的当且仅当。定理1.31设为一任意n阶图，。RMerris给出图与其补图Laplace谱之间的关系如下：定理1.41 若的Laplace谱为，则，。定理1.5 1 若为偶图，为的线图，的Laplace谱为，的邻接谱为，若，则，。1.3 本文主要结果 本文着重研究了两个完全图的重组图的Laplace谱，然后研究了两个完全图的重组图删去一条边所得的图的Laplace谱，通过谱之间的比较得出相应的结论，同时推广研究了个完全图的重组图的情形。恥諤銪灭萦欢煬鞏鹜錦。第二章 重组图的Laplace谱2.1 两个完全图的重组图的Laplace谱设为Kk的顶点集。为连同共有个点的完全图，其顶点集记为，为连同共有个点的完全图，其顶点集记为。设表示完全图和在Kk基础上的重组图，即=（，；Kk），其中：。鯊腎鑰诎褳鉀沩懼統庫。定理2.1.1，设重组图=（，；Kk）的Laplace谱为,则。证明：图的邻接矩阵为,其中： ，1代表全1矩阵，0代表全0矩阵，其中：。度矩阵=,其中：， Laplace矩阵的特征多项式为根据行列式的定义可以得到：从而得重组图=（，；Kk）的Laplace谱为 2.2 去掉两个完全图的重组图中Kk内一条边的情况定理2.2.1，设重组图为去掉Kk内一条边的所得到的图，其Laplace谱为，则 。证明：图的邻接矩阵为,其中：，度矩阵为=,其中：，Laplace矩阵为的特征多项式为根据行列式的定义可以得到从而得重组图的Laplace谱为 2.3 去掉两个完全图的重组图中内一条边的情况定理2.3.1，设重组图为去掉中一条边所得到的图，其Laplace谱为，则。证明：图的邻接矩阵为，其中：，度矩阵为其中：，Laplace矩阵为的特征多项式为根据行列式的定义可以得到从而得重组图的Laplace谱为2.4 去掉两个完全图的重组图中与之间的一条边的情况定理2.4.1，设重组图为去掉与之间一条边所得到的图，其Laplace谱为，则重组图的Laplace谱为：1个0，个，个，个，。硕癘鄴颃诌攆檸攜驤蔹。证明：图的邻接矩阵为，其中：，度矩阵Laplace矩阵= 其中：=所以令并进行如下计算： 根据根的存在性定理可知：和之间至少存在一个根，和之间至少存在一个根综上：重组图的Laplace谱为：1个0，个，个，个，。2.5 个完全图的重组图的情形由两个完全图的重组图Laplace谱的变化情况，我们可以推广得到个完全图的重组图的情形。定理4.1，设重组图的Laplace谱为,则谱为：1个0，1个，个，个，个，个个。定理4.2，设重组图为去掉Kk内一条边的所得到的图，则其Laplace谱为：其中包括1个0，1个，1个，个，个，个，个个。阌擻輳嬪諫迁择楨秘騖。定理4.3，设重组图为去掉中一条边所得到的图，则其Laplace谱为：1个0，1个，1个，个，个，个，个个。氬嚕躑竄贸恳彈瀘颔澩。定理4.4，设重组图为去掉与之间一条边所得到的图，其Laplace谱为，则重组图的Laplace谱为：釷鹆資贏車贖孙滅獅赘。1个0，个，个，个，个个，。第三章 归 纳特征值下表是各种情况下重组图的拉普拉斯谱个数分布的情况：不同情况个数0不去边1100无无无内去边1110无无无内去边1101无无无与间去边1无无无111通过上表，我们可以发现：1.比较定理2.1.1和定理2.2.1，去掉重组图中内一条边，重组图的谱半径和代数连通度均未发生改变，只是定理2.2.1比定理2.1.1增加了这个特征值，及特征值的重数发生了改变。怂阐譜鯪迳導嘯畫長凉。2.比较定理2.1.1和定理2.3.1，去掉重组图中内一条边，重组图的代数连通度未发生改变，谱半径发生了变化，需要根据和的大小来确定。谚辞調担鈧谄动禪泻類。3.比较定理2.1.1和定理2.4.1，去掉重组图中与之间的一条边，重组图的谱半径不变，代数连通度发生改变，有三个特征值的大小较难确定，只能给出大概的范围。 参考文献嘰觐詿缧铴嗫偽純铪锩。1 M. Dehmer . Structural Analysis of Complex NetworksM. Springer Science+Business Media.熒绐譏钲鏌觶鷹緇機库。2 Kirchhoff G. U ber die Auflosung der Gleichungen auf welche man bei der Untersuchung der Linearen Vertheilung galvanischer Strome gefuhrt wirdJ. Ann Phys Chem, 1847,72:497508.鶼渍螻偉阅劍鲰腎邏蘞。3 Krivelevich M, Sudakov B. Pseudo-random graphsJ. More sets, graphs and numbers. Bolyai Society Mathematical Studies, 2006,vol 15: 199262.纣忧蔣氳頑莶驅藥悯骛。4 van Dam E, Haemers W. Which graphs are determined by their spectrum?J. Lin Algebra Appl, 2003,373:241272.颖刍莖蛺饽亿顿裊赔泷。5 van Dam E, Haemers W. Developments on spectral characterization of graphsJ. Discrete Math, 2009,309:576586.濫驂膽閉驟羥闈詔寢賻。6 Cvetkovic D, Doob M, Sachs H. Spectra of graphs theory and applicationJ. Academic, New York, 3rd edn, 1995.銚銻縵哜鳗鸿锓謎諏涼。7 Cvetkovic D, Rowlinson P, Simic S. Eigenspaces of graphsM. Cambridge University Press: