数学专业图论与组合毕业论文答辩PPT模板

1、学科专业：数学 培养方向：图论与组合 姓 名：某某某 指导教师：某某某 教授,具有固定直径的图的最小无号 拉普拉斯谱半径,内容提要,基本概念 摘要 研究现状 本文主要研究内容与结论 攻读硕士期间取得的学术成果 致谢,第一部分 基本概念,基本概念,令 表示简单图，其中 是 的顶点集， 是边集。 表示 的与点 邻接点的集合。 表示点的度。 表示 的最大度。 的邻接矩阵 是一个 的 矩阵，其中当 与 邻接时 ；否则 。 的最大特征值称为 的谱半径。令 是度矩阵， 称为图 的拉普拉斯矩阵， 的拉普拉斯特征多项式为 ，记为 。,称 为图的无号拉普拉斯矩阵。由于 、 和 是实对称矩阵，所以它们的特征值都为

2、实数。它们对应的最大特征值分别叫做 图 的谱半径（记为 ），拉普拉斯谱半径（记为 ）和无号拉普拉斯谱半径（记为 ）。通常我们把具有 个点的圈，路，星图分别记为 和 。,基本概念,连通图 的两点 和 之间的距离为 。 连通图 的直径为图中任意两点间距离的最大值，简记为 。 二部图，又称二分图，偶图。指定点可以分成 两个不相交的集使得在同一个集内的顶点不相邻（没有共同边）的图。 正则图指的是各顶点的度均相同的图。,基本概念,令 表示顶点个数为 ，直径为 的图的集合。同理 ， 定义如上。 如果 并且具有最小无号拉普拉斯谱半径，则称 是 中的一个极图。 表示由圈 上某一点引出一条长为 的悬挂路所得到的

3、图。令 表示树 中度为3的顶点数。 设 。 设 是由图 在顶点 引出两条长度分别为 和 的悬挂路得到的图。,基本概念,第二部分 摘 要,图的谱理论是图论与组合数学论的一个重要研究领域，包括图的邻接谱，拉普拉斯谱，无号拉普拉斯谱和规范拉普拉斯谱四个方面的内容。图谱理论在量子化学、物理、计算机科学、通讯网络及信息科学技术中均有广泛应用。本文主要运用代数和几何的方法对图的无号拉普拉斯谱进行研究，特别是对具有给定直径的图的最小无号拉普拉斯谱半径进行了研究。,摘要,主要内容如下： （1）分类概括总结图的各种矩阵的谱半径的国内外研究成果； （2）研究得出了直径 的图的最小无号拉普拉斯谱半径； （3）研究得

4、出了直径 的图的最小无号拉普拉斯谱半径； （4）研究得出了直径为 的图的最小无号拉普拉斯谱半径。,摘要,第三部分 研究现状,研究现状,van dam e r和kooij r e (2007)在文献the minimal spectral radius of graphs with a given diameter中给出了直径为 的具有最小谱半径的图，并提出以下猜想： 猜想1 对于一个固定的整数 ，当直径为 ，顶点为 时，图 具有最小谱半径。,袁喜英等(2008)在文献the minimal spectral radius of graphs of order n with n-4 diamet

5、er中证明了 时该猜想成立并给出当 时， 是直径 且具有最小谱半径的图；cioaba s m等(2010)在文献asymptotic on the spectral radius and the diameter of graphs中证明了直径 时猜想成立并证明该猜想在 时不成立；belardo f等(2009)在文献trees with minimal index and diameter at most four中确定了直径 的具有最小谱半径的图。,研究现状,研究现状,而对于图的拉普拉斯谱半径，liu r-f等(2009)在文献the minimal laplacian spectral

6、radius of trees with a given diameter中给出了直径为 的具有最小拉普拉斯谱半径的树。,第四部分 本文主要研 究内容与结论,本文对图的无号拉普拉斯谱半径进行了研究，给 出了顶点个数为 ，直径为 的具有最小无号拉普拉斯谱半径的图，作为推论，给 出了直径为 的具有最小拉普拉斯谱半径的树。 基本思路是首先将直径为 的具有最 小无号拉普拉斯谱半径的图转化为树，而直径 的情况稍微简单一点，用一些已知引理即可证明，最 后对于直径为 的树我们将其分为三类并找出每一,本文主要研究内容与结论,本文主要研究内容与结论,类中唯一一个具有最小无号拉普拉斯谱半径的 树，最后运用图的剖分

7、，嫁接等运算及特征多项式技巧找出这三类树中所给出的三个最小无号拉普拉斯谱半径中最小的一个。,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可得如下结果：,本文主要研

8、究内容与结论,定理4.7 在 中，树 具有最小无号拉普拉 斯谱半径。 定理4.8 在 中， 具有最小无号拉普拉斯 谱半径。,本文主要研究内容与结论,4.2 直径 的图的最小无号拉普拉斯谱半径,本文主要研究内容与结论,记 个点的双星图为 ， 。 引理4.9 当 时，双星图 具有最小拉普拉斯谱半径。 由引理4.3和4.9可得如下结果： 定理4.10 当 时，双星图 具有最小无号拉普拉斯谱半径。,perron-frobenius定理：若方阵 ， 不 可约，则 ，等式成立当且仅当 。 由perron-frobenius定理可得如下结果： 定理4.11 当 时， 具有最小无号拉普拉 斯谱半径。 定理4.

9、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 设 ，若 是 中的一个极图，则是一棵树。 由引

10、理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 设 和 是两个顶点不交的图， 是 的点， 是 的点。 用一条边连接 则形成一个新图，记为 ，则 ， 其中 表示 去掉点 对应的行和列后的子阵对应 的

11、特征多项式。,本文主要研究内容与结论,令 表示路 的拉普拉斯矩阵 删去某个悬挂点所对应的行与列得到的 阶矩阵; 表示路 的拉普拉斯矩阵 删去两个悬挂点所对应的两行和两列所得到的 阶矩阵。 引理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 是直径为 ,顶点数为 的树中拉普 拉斯谱半径最小的唯一树。,本文主要研究内容与结论,攻读硕士期间 取得的学术成果,1 2 3,攻读硕士期间取得的学术成果,致 谢,本文是在我的导师郭继#老师的悉心指导下完成的。#老师治学严谨，学识渊博，学术方面有很深的造诣。近三年的学习和生活中，在#老