图无符号拉普拉斯特征值

《图无符号拉普拉斯特征值》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图的无符号拉普拉斯特征值』一O●一●-●一·sigmessLaplacianeigenvalueolGraphs作者指导教师学位类别学科专业学位授予单位论文提交日期郭晶晶I、月华理学硕士运筹学与控制论浙江师范大学2013年5月20日图的无符号拉普拉斯特征值摘要给定一个图G，用y(G)，E(G)，A，6分别表示图G的点集，边集，最大度，最小度．邻接矩阵A=(aij)。×n定义如下：若顶点i与J相邻，aij=1，否则aij=0．矩阵Q=D+A称为图G的无符号拉普拉斯矩阵，其中D=diag(d1，d2，⋯，dn)是度对角矩阵

2、，矩阵A是图G的邻接矩阵．显然矩阵Q是一个非负实对称矩阵，用91≥q2≥q3≥⋯≥gn一1≥qn表示Q的n个特征值．本文主要围绕图的无符号拉普拉斯特征值展开讨论．第一章简述目前无符号拉普拉斯特征值上下界的研究现状和本文的主要结果．第二章主要给出了无符号拉普拉斯第四大特征值94和第五大特征值q5的下界，并用穷举法给出证明．第三章主要证明了无符号拉普拉斯最大特征值口1的相关结论．关键词：无符号拉普拉斯矩阵；特征值：Nordhaus—Gaddumtype；度SignlessLaplacianeigenvalueofGraph

3、sABSTRACTForagivengraphG，lety(G)，E(G)，△(G)，6(G)denotethevertex—set，edge。set，maximumdegree，minimumdegree，respectively．TheadjacencymatrixofGisdefinedtobethe咒×nmatrixA=(o巧)n×n，whereaij=1ifViisadjacencytovj；otherwiseaij=0．ThesignlessLaplacianmatrixQ=D+AwhereD=diag(d

4、l，d2，·一，dn)isthediagonalmatrixofvertexdegreesandAistheadjacencymatrix．ItiswellknownthatQ(C)issymmetricmatrix．Denoteitseigenvaluesbyql≥q2≥⋯≥qn．ThismasterthesismainlydiscussthesignlessLaplacianeigenvalueofgraphs，Inchapter1，wegiveabriefsurveyinthisdirection．Mainres

5、ultsobtainedinthisthesisarestated．Inchapter2，westudytheforthandfifthlargestsignlessLaplacianeigenvalues，provethatthelowerboundofthem．Inchapter3，wegiveseveralresultsaboutthelargestsignlessLaplacianeigenvalue．KEYWORDS：Laplacianmatrix；Eigenvalue；Nordhaus—Gaddumtype

6、；DegreeII目录摘要⋯⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．IABS’l’KAC’l。⋯⋯⋯⋯．．．．．．．．⋯⋯⋯⋯⋯⋯⋯⋯⋯．．⋯．．．⋯⋯⋯⋯目录⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯l绪论⋯⋯．⋯⋯⋯．⋯⋯．⋯⋯⋯⋯．．．⋯⋯⋯．⋯．⋯．⋯⋯⋯．⋯·1．1基本概念⋯⋯⋯⋯⋯⋯⋯．⋯⋯．．．⋯⋯⋯⋯⋯⋯⋯⋯⋯，⋯·1．2无符号拉普拉斯特征值的研究概况⋯⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯．⋯．1．3本文的主要结果⋯⋯⋯．⋯⋯⋯⋯．⋯⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯2无符号拉普拉斯第四大、第五大特征值的界⋯⋯⋯

7、⋯⋯．⋯．⋯⋯⋯⋯．．2．1无符号拉普拉斯第四大特征值的界⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯．⋯．2．2无符号拉普拉斯第五大特征值的界⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯3无符号拉普拉斯最大特征值⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯在学期问的研究成果及发表的论文⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯．⋯⋯⋯．⋯．致谢⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。学位论文独创性声明及授权声明⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．学位论文诚信承诺书⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯．⋯⋯⋯．⋯．Ⅱm●4

8、6¨勰”舛弱卯1．1基本概念1绪论给定n个顶点，m条边的图G，让y(G)，E(G)，A，J分别表示图G的点集，边集，最大度，最小度．让，u是图G的顶点，e是图G的边．若e=UV∈E(G)，则称扎，V在G中相邻．补图召定义如下：一G的顶点集与图G相同，召中两个顶点相邻当且仅当这两个顶点在图G中不相邻．di(G)表示顶点坎的度数，令d