数学专业图论与组合毕业论文答辩ppt课件

学科专业：数学培养方向：图论与组合姓名：某某某指导教师：某某某教授,具有固定直径的图的最小无号拉普拉斯谱半径,内容提要,基本概念摘要研究现状本文主要研究内容与结论攻读硕士期间取得的学术成果致谢,第一部分基本概念,基本概念,令表示简单图，其中是的顶点集，是边集。表示的与点邻接点的集合。表示点的度。表示的最大度。的邻接矩阵是一个的矩阵，其中当与邻接时；否则。的最大特征值称为的谱半径。令是度矩阵，称为图的拉普拉斯矩阵，的拉普拉斯特征多项式为，记为。,称为图的无号拉普拉斯矩阵。由于、和是实对称矩阵，所以它们的特征值都为实数。它们对应的最大特征值分别叫做图的谱半径（记为），拉普拉斯谱半径（记为）和无号拉普拉斯谱半径（记为）。通常我们把具有个点的圈，路，星图分别记为和。,基本概念,连通图的两点和之间的距离为。连通图的直径为图中任意两点间距离的最大值，简记为。二部图，又称二分图，偶图。指定点可以分成两个不相交的集使得在同一个集内的顶点不相邻（没有共同边）的图。正则图指的是各顶点的度均相同的图。,基本概念,令表示顶点个数为，直径为的图的集合。同理，定义如上。如果并且具有最小无号拉普拉斯谱半径，则称是中的一个极图。表示由圈上某一点引出一条长为的悬挂路所得到的图。令表示树中度为3的顶点数。设。设是由图在顶点引出两条长度分别为和的悬挂路得到的图。,基本概念,第二部分摘要,图的谱理论是图论与组合数学论的一个重要研究领域，包括图的邻接谱，拉普拉斯谱，无号拉普拉斯谱和规范拉普拉斯谱四个方面的内容。图谱理论在量子化学、物理、计算机科学、通讯网络及信息科学技术中均有广泛应用。本文主要运用代数和几何的方法对图的无号拉普拉斯谱进行研究，特别是对具有给定直径的图的最小无号拉普拉斯谱半径进行了研究。,摘要,主要内容如下：（1）分类概括总结图的各种矩阵的谱半径的国内外研究成果；（2）研究得出了直径的图的最小无号拉普拉斯谱半径；（3）研究得出了直径的图的最小无号拉普拉斯谱半径；（4）研究得出了直径为的图的最小无号拉普拉斯谱半径。,摘要,第三部分研究现状,研究现状,VanDamER和KooijRE(2007)在文献Theminimalspectralradiusofgraphswithagivendiameter中给出了直径为的具有最小谱半径的图，并提出以下猜想：猜想1对于一个固定的整数，当直径为，顶点为时，图具有最小谱半径。,袁喜英等(2008)在文献Theminimalspectralradiusofgraphsofordernwithn-4diameter中证明了时该猜想成立并给出当时，是直径且具有最小谱半径的图；CioabaSM等(2010)在文献Asymptoticonthespectralradiusandthediameterofgraphs中证明了直径时猜想成立并证明该猜想在时不成立；BelardoF等(2009)在文献Treeswithminimalindexanddiameteratmostfour中确定了直径的具有最小谱半径的图。,研究现状,研究现状,而对于图的拉普拉斯谱半径，LiuR-F等(2009)在文献TheminimalLaplacianspectralradiusoftreeswithagivendiameter中给出了直径为的具有最小拉普拉斯谱半径的树。,第四部分本文主要研究内容与结论,本文对图的无号拉普拉斯谱半径进行了研究，给出了顶点个数为，直径为的具有最小无号拉普拉斯谱半径的图，作为推论，给出了直径为的具有最小拉普拉斯谱半径的树。基本思路是首先将直径为的具有最小无号拉普拉斯谱半径的图转化为树，而直径的情况稍微简单一点，用一些已知引理即可证明，最后对于直径为的树我们将其分为三类并找出每一,本文主要研究内容与结论,本文主要研究内容与结论,类中唯一一个具有最小无号拉普拉斯谱半径的树，最后运用图的剖分，嫁接等运算及特征多项式技巧找出这三类树中所给出的三个最小无号拉普拉斯谱半径中最小的一个。,4.1直径的图的最小无号拉普拉斯谱半径,本文主要研究内容与结论,引理4.1设，若是中的一个极图，则是一棵树。引理4.2设，若是中的一个极图，则是一棵树。引理4.3，当且仅当为二分图时等号成立。,引理4.4在中，树和具有最小拉普拉斯谱半径。引理4.5在中，树具有最小拉普拉斯谱半径。由引理4.1，引理4.3和引理4.4可得如下结果：定理4.6在中，树和具有最小无号拉普拉斯谱半径。由引理4.2，引理4.3和引理4.5可得如下结果：,本文主要研究内容与结论,定理4.7在中，树具有最小无号拉普拉斯谱半径。定理4.8在中，具有最小无号拉普拉斯谱半径。,本文主要研究内容与结论,4.2直径的图的最小无号拉普拉斯谱半径,本文主要研究内容与结论,记个点的双星图为，。引理4.9当时，双星图具有最小拉普拉斯谱半径。由引理4.3和4.9可得如下结果：定理4.10当时，双星图具有最小无号拉普拉斯谱半径。,Perron-Frobenius定理：若方阵，不可约，则，等式成立当且仅当。由Perron-Frobenius定理可得如下结果：定理4.11当时，具有最小无号拉普拉斯谱半径。定理4.12当时，具有最小无号拉普拉斯谱半径。,本文主要研究内容与结论,4.3直径为的图的最小无号拉普拉斯谱半径,本文主要研究内容与结论,引理4.13是一个连通图，是内路上的一条边，是剖分边得到的图，则。由Perron-Frobenius谱半径比较定理可得如下结果：引理4.14设是一个连通图，如果是的真子图，则有。由引理4.13和引理4.14可得：,引理4.15顶点个数为10，圈长不超过8的单圈图中，具有最小无号拉普拉斯谱半径的一个图且。由引理4.13、引理4.14、引理4.15可得：引理4.16设，若是中的一个极图，则是一棵树。由引理4.13和引理4.14可得：引理4.17设，若树是中的一个极图，则且。引理4.18令是一个顶点数为的连通二分图，则当时，。,本文主要研究内容与结论,由引理4.13、引理4.14、引理4.18可得：定理4.19（1）设，则树（见图4-1）是中的唯一极图；（2）设，则树（见图4-2）是中的唯一极图。,本文主要研究内容与结论,由引理4.13和引理4.14可得：定理4.20设，则。引理4.21设和是两个顶点不交的图，是的点，是的点。用一条边连接则形成一个新图，记为，则，其中表示去掉点对应的行和列后的子阵对应的特征多项式。,本文主要研究内容与结论,令表示路的拉普拉斯矩阵删去某个悬挂点所对应的行与列得到的阶矩阵;表示路的拉普拉斯矩阵删去两个悬挂点所对应的两行和两列所得到的阶矩阵。引理4.22令，则（1）；（2）；（3）。,本文主要研究内容与结论,由引理4.22可得：推论4.23设，则有（1）；（2）；（3）。由引理4.14、引理4.3、引理4.21、引理4.22、引理4.23可得：定理4.24令如图4-3，当，时，有。,本文主要研究内容与结论,由引理4.13和4.14和定理4.24可得：定理4.25设，则树(见图4-4)是中的唯一极图。,本文主要研究内容与结论,由引理4.13、引理4.14、引理4.18可得：定理4.26设，则。由定理4.20和定理4.26可得：定理4.27是中的唯一极图。由引理4.3和定理4.27，我们有如下结果：推论4.28是直径为,顶点数为的树中拉普拉斯谱半径最小的唯一树。,本文主要研究内容与结论,攻读硕士期间取得的学术成果,123,攻读硕士期间取得的学术成果,致谢,本文是在我的导师郭继#老师的悉心指导下完成的。#老师治学严谨，学识渊博，学术方面有很深的造诣。近三年的学习和生活中，在#老师的悉心指导和同学的帮助下我学到