《毕业设计（论文）含割边的图的距离无符号拉普拉斯谱半径论文.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）含割边的图的距离无符号拉普拉斯谱半径论文.doc（16页珍藏版）》请在三一办公上搜索。
1、目 录摘 要IAbstractII1 引言11.1 研究背景与研究意义11.2 基本符号与概念21.2.1 基本符号21.2.2 基本概念21.3 研究问题及主要结论42 图的距离无符号拉普拉斯谱半径52.1 谱半径及对应特征向量的相关性质52.2 含割边的图的距离无符号拉普拉斯谱半径8总结和展望11参考文献12致 谢13摘 要 图论是一门应用广泛的数学分支，被广泛的应用在离散数学问题中.在构成图论重要领域的图谱理论的研究过程中，人们引入了与图的结构有密切联系的矩阵，如：邻接矩阵、关联矩阵、距离矩阵和无符号距离矩阵.图谱理论主要研究图的性质能否及如何由这些矩阵的代数性质（主要为矩阵的特征值）反
2、映出来.在众多矩阵中，因为无符号矩阵包含图的各点度的信息，更能反映出图的某些性质，所以备受研究者的青睐.本文在其基础上进一步研究距离无符号拉普拉斯谱半径.一个连通图的距离无符号谱半径就是的距离无符号矩阵的谱半径.连通图的距离无符号矩阵定义为： (是的顶点距离度；为的距离矩阵).本文主要研究含割边的阶连通图的最小距离的无符号谱半径。具体内容分为下面两大部分：1.介绍图论研究背景与研究意义；所涉及的记号、基本概念；研究问题和主要结论；2.在含割边的阶连通图中，以特征向量研究特征值的方法为指导思想，首先确定具有最小距离的无符号谱半径的取值范围为：，等号当且仅当成立；随后，运用求解，为：当且仅当时等号
3、成立；最后进一步的得到一个特例，当且仅当等号成立.关键词：图；割边；距离无符号矩阵；谱半径Abstract Graph theory,a branch of Applied Mathematics,has been widely used in discrete mathematics problems. In the course of the study of it, we have introduced a matrix, closely related to the structure of a graph such as: the adjacency matrix, the inci
4、dence matrix, the distance matrix and unsigned distance matrix etc.The nature is mainly researched on Graph Spectra Theory whether and how these algebraic properties of the matrix,mainly the eigenvalue of the matrix,can reflect some properties.In many matrix, many researchers love no symbol matrix ,
5、for it contains each point ofinformation map and reflect some properties of graphs. In this paper, we research on distance unsigned Laplacian spectral radius futher. The spectral radius of a graph distance spectral radius is the unsigned unsigned distance matrix. Connected graph distance matrix is d
6、efined as unsigned: .No sign of the spectral radius of the minimum distance in this paper including the cut edges of the graph of order. Specific content is divided into the following two parts:1.Introduction to graph theory, the background and research significance; mark and the basic concept; the
7、research question and the main research conclusions;2.Containing cutting edges in the graph, method to study the eigenvalues of the feature vector as the guiding ideology, first determine the minimum distance has no range of spectral radius: with equalily if and only if ; then,using the Matlab, with
8、 equalily if and only if ;finally further get a special case,with equalily if and only if.Key words: graph; cutting edge; unsigned distance matrix; spectral radius 1 引言本章首先介绍图的距离无符号拉普拉斯谱半径的研究背景与研究意义，再介绍本文中需要用到的基本概念与相关术语，最后介绍本文所研究的问题以及所取得的主要结果.1.1 研究背景与研究意义图论是研究离散对象二元关系中关系结构的一个数学分支，与群论、矩阵论、拓扑学、概率论、数值
9、分析等其它数学分支有着密切的联系，其广阔的应用领域涵盖了计算机科学、物理学、化学、运筹学、控制论、信息论、经济学、心理学、环境保护领域等.同时随着这些学科的发展，特别是计算机科学的快速发展，又促进了图论的发展.图论起源于著名的哥尼斯堡七桥问题，经过两百多年的发展，目前形成的研究分支主要包括代数图论、组合图论、拓扑图论和随机图论等.其中，代数图论是应用代数的方法来解决图论问题，或者用图论的方法来解决代数问题.图的谱理论是代数图论的一个研究热点，主要研究图的不同矩阵表示的谱性质（图的谱即图的邻接矩阵全体特征值，又称邻接谱1），通过讨论图的特征空间和特征多项式，建立图的拓扑结构（图的各种不变量）和图
10、的矩阵表示的置换相似不变量之间的联系，应用置换群理论、矩阵论（特别是非负矩阵理论、对称矩阵理论、组合矩阵论）和谱几何理论来研究图的拓扑结构性质，同时也将图谱理论的研究结果应用于群论、矩阵论和谱几何论,以推动它们的理论发展.因此，图的谱理论是图论与组合数学共同关注的一个重要的研究领域.因此，利用代数组合和分析的方法建立图的极端特征值和这些参数的联系有着非常重要的意义.另外，图的极端特征值可视为一些特殊矩阵（如(0,1)-矩阵和整数Z-矩阵）的极端特征值.由于表示图的矩阵蕴含着图的结构信息，借助于图的特征向量的组合性质，研究这一类特殊矩阵的极端谱性质，对组合矩阵论的研究有着重要的理论意义.随着图所
11、提供的组合模型在其他学科的广泛应用，图的极端特征值在这些领域发挥着令人惊奇的效果.例如，在结构化学中，图的邻接谱半径和最小特征值可以用于表示分子结构图中电子的能量级范围；而在计算机视觉中，利用图的邻接或Laplace谱半径及其对应特征向量是处理结构图匹配问题中的重要方法.关于极端特征值的研究在过去的几十年里主要集中于图的邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵和距离矩阵等，均取得了丰硕的成果.由此可见，刻画给定图类中距离无符号谱半径的极值具有重要意义.近年来，在给定图类中谱半径取值的研究成果很多，如2-6.类似于（邻接）拉普拉斯矩阵和（邻接）无符号拉普拉斯矩阵，近来，和在文献7中给出了连通图
12、的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵.随后，关于它们的极端特征值的研究很快就受到了国内外学者的关注.本文在含割边的阶连通图中，运用特征向量研究特征值的方法，确定了具有最小距离的无符号谱半径的极图，并刻画了距离无符号谱半径关于阶数的一个下界，从而进一步刻画出含割边的任意阶连通图中距离无符号谱半径的最小值. 1.2 基本符号与概念1.2.1 基本符号设表示一个图，本文中我们采用以下符号： :图的顶点集 :图的边集 :连接和的最短路的长度 :图的距离矩阵 :顶点的距离度 :的谱半径 :个顶点的完全图 :的任意生成树 :完全图与的粘合1.2.2 基本概念表示图的概念和矩阵有很多，下面介绍与本文有
13、关的概念与矩阵.设图，其中为点集，称为图的阶数，表示边集，称为图的边数.定义1 平行边：两个结点间方向相同的若干条边称为平行边或重边.定义2 环：两端点相同的边称为环或自回路.定义3 无环且无平行边的图形称为简单图8.定义4 为有限图，如果对任意，图中都存在一条连接的路径，则称 为连通图.定义5 树：连通无圈图为树9.定义6 任意不同两结点之间都有边相连的简单无向图成为完全图8.定义7 图的邻接矩阵，定义为，其中定义8 图的度对角矩阵，定义为：定义9 的无符号拉普拉斯矩阵，定义为： 平行于上面介绍的三个矩阵，接下来我们介绍距离矩阵、距离度矩阵和距离无符号拉普拉斯矩阵.定义10 图的距离矩阵定义
14、为： 距离矩阵在很多领域都有着重要的应用，如交通网络设计10、分子稳定性11,12等。等13提出了距离谱半径作为分子助推器的应用，等14用距离谱半径推断烷烃分子的分支情况以及计算烷烃的沸点.定义11 顶点的距离定义为： 即顶点与中所有其他顶点距离之和.用表示中顶点的最大距离度.定义12 连通图的距离无符号矩阵15：易见，,所以是半正定对称矩阵，因此，它的特征值可排序列为：.另外，由于是非负矩阵，故据定理知，的谱半径(即距离无符号谱半径)恰为的重数为1的最大的特征值，并且存在唯一的正单位向量（称为向量）对应这个特征值.1.3 研究问题及主要结论 本文讨论了含割边的连通图的距离无符号拉普拉斯谱半径
15、，确定了含割边的n阶连通图的谱半径的一个下界，并刻画了相应的极图，再在此基础上，给出了含割边的连通图的谱半径的一个下界以及相应极图的结构.主要结论为：具有最小距离的无符号谱半径的取值范围为：等号当且仅当成立；随后，运用求解，为：当且仅当时等号成立；最后进一步的得到一个特例，当且仅当时等号成立.2 图的距离无符号拉普拉斯谱半径 本章主要由两小节构成：第一节介绍谱半径及对应特征向量的相关性质；第二节介绍含割边的图的距离的无符号拉普拉斯谱半径16.2.1 谱半径及对应特征向量的相关性质 对阶图和向量，若有一个从到的一一映射,则可认为是定义在上的一个函数.对任意，简记，即是的与顶点相对应的分量.若是的
16、一个特征向量，则可以自然地被定义在上。根据二次型的相关知识，易见 （2.1）由特征值与特征向量的定义，不难发现，是的属于特征值的一个特征向量当且仅当且对任意，有 （2.2）另外，对任一单位向量 （2.3）等式成立当且仅当是的Perron向量.证明:现在先证2.1.要证明2.1等式成立，我们只需要证明等式右边可以化成等式左边的形式即可.因为=所以等式右边等于等式左边，即等式2.1成立.下证2.2式子：设为的特征值为所对应的特征向量，由特征值和特征向量的定义知：，又，带入得，按照第行展开得证毕.下证2.3式子：由商，即，其中分别为矩阵的最小特征值、最大特征值，易得，证毕.由主要结论易知，若为的一条
17、边，且仍是连通的。则边的移动并没有减少距离，至少确实增加了1单位的距离，例如连通图中两点之间的距离，则在中.相似的，在中增加一条新的边并没有增加距离，至少确实减少了1单位的距离.根据非负矩阵理论，易得下述结果引理 2.1 设是连通图，表示任意边，则（1）若，则；（2）若且也是连通的，则.根据引理1知，对任一阶的连通图，有，当且仅当时等号成立；，当且仅当是树时等号成立.引理 2.217 设是连通图，则.记路的长度为，以下结论表明了图中顶点的邻域与距离度的关系.引理 2.3 设是的连通图，则（1）若 则；（2）若 则.证明：对任意且（1）若 则；若 则在与之间一定存在一条最短路，记为. 记为上与邻
18、接的顶点，为上连接与的路， 则一定为连接与的一条最短路. 如若不然，在与之间一定存在一条路，这里.记为上与邻接的顶点，为上连接与的路，则也是连接与的路.但是矛盾！因此，是连接与的一条最短路，于是.综合以上两种情形，我们证明了（1）. （2）若 则；若 则且；若 则在与之间一定存在一条最短路，记为. 记为上与邻接的顶点.若 则类似于（1），我们可以得到与之间的一条最短路，其长度等于.若 则 于是. 否则，若，则在与之间存在一条最短路，这里.记为上与邻接的顶点，为上连接与的路，则也是连接与的路.但是，与为与之间的一条最短路矛盾.综合以上三种情形，我们证明了（2).由引理2.3，我们可以得到下述引理
19、.引理2.4 设是包含顶点的连通图，为的一个 向量，(1) 若 则；(2) 若 则.证明：由等式(2.1)得: (2.4) (2.5)下面先证明（1）成立： (1)由引理2.3知，当对任意的都有且.所以有.由于式（2.4）和（2.5）的右边均为正可，所以于是. （2）同理知，当有，且对任意的 都有，且存在顶点 使得. 所以即于是.综上，引理2.4得证.2.2含割边的图的距离无符号拉普拉斯谱半径设是含顶点、是含顶点的两个不相交的连通图，将的顶点与的顶点粘到一起，可以形成一个新的图，称作图与图的粘合，记作.现规定，将完全图与的粘合记作.定理2.5 设为含割边的阶连通图，则，当且仅当 时等号成立.证
20、明: 假设阶连通图含割边的类中具有最小距离无符号Laplace谱半径的图，首先由引理2.1易知，一定只含一条割边.另外，由引理2.1知，可视为两个完全图与的粘合，其中.不妨设，并将与粘合点分别记作.用表示的距离无符号Laplace谱半径，表示对应的向量.根据的结构，由引理4知，中所有顶点对应的的分量一定相等，记为，则粘合点所对应的的分量记作；中所有顶点对应的的分量也一定相等，记为；记所对应的的分量为,则由（2.2）得：于是一定是方程的最大根，其中 若，用表示的距离无符号Laplace谱半径，则由引理2可得因为，所以得。根据为多项式的最大根以及知，.因此，对型的图，当越小，越大时，对应的距离无符
21、号Laplace谱半径越小，而注意到，于是证得结论成立.定理2.6 设是含割边的阶连通图,则当且仅当时等号成立.证明: 由定理2.5知，欲证等式成立只需计算的距离无符号Laplace谱半径即可.而由定理4的证明过程可知，为重数为1的最大特征值.运用中求矩阵特征值的函数求解可以得到，重数为1的最大特征值为：故，定理2.6得证.推论2.7 设是含割边的连通图，则，等号当且仅当时成立.证明： 法一：由定理2.6知，将，带入可得故推论2.7成立. 法二：求解可以得到重数为1的最大特征值为2.即则，等号当且仅当时成立.总结和展望 在导师的指导和同学的帮助下，我顺利完成了本篇论文.本文主要分为两大章：第一
22、章为引言，主要介绍图论的研究背景与研究意义、基本概念与记号、研究问题和主要结论；第二章是含割边的图的距离的无符号拉普拉斯谱半径，详细的介绍有关本文的结论.在求解过程中，我们通过不断添边，最后将所求问题化为只含一条割边的连通图.本文的写作过程中还存在一些思考，不过在本文中并没有得到证明，例如：（1）本文对割边数固定的情形却没有进一步深入了解；（2）若是树，相关结论又是如何.类似的问题值得思考和深入研究，而这是我们今后努力研究的方向，希望今后能继续在这一领域做出更多研究工作.参考文献1林辉球.图的邻接谱和距离谱的研究D. 华东师范大学,2013:22-36.2S.S. Bose, M. Nath,
23、 S. Paul, Distance spectral radius of graphs with r pendent verticesJ, Linear Algebra Appl. 435(2011) 2826-2836.3A. Ili, Distance spectral radius of trees with given matching numberJ, Discrete Appl. Math. 158 (2010) 1799-1806.4Z.Z. Liu, On the spectral radius of the distance matrixJ, Appl. Anal. Dis
24、crete Math. 4(2)(2010) 269-277.5M. Nath, S. Paul, On the distance spectral radius of bipartite graphsJ, Linear Algebra Appl. 436(2012)1285-1296.6D. Stevanovi, A. Ili, Distance spectral radius of trees with fixed maximum degreeJ, Electron. J. Linear Algebra 20 (2010) 168-179.7M. Aouchiche, P. Hansen,
25、 Two Laplacians for the distance matrix of a graphJ, Linear Algebra Appl. 439 (2013) 2133.8殷剑宏、吴开亚.图论及其算法M.中国科学技术大学出版社,2003:5-15.9孙惠泉.图论及其应用.科学出版社,2006:5-18.10R.L. Graham and H.O. Pollak, On the addressing problem for loop switchingJ, Bell Sys. Tech. J. 50 (1971) 2495-2519.11M. Edelberg, M.R. Garey
26、and R.L. Graham, On the distance matrix of a treeJ, Discrete Math. 14 (1976) 23-29.12R.L. Graham and H.O. Pollak, On embedding graphs in squashed cubesJ, Graph Theory and Applications, Springer, Berlin (1973) 99-110.13A.T. Balaban, D. Ciubotariu, M. Medeleanu, Topological indices and real number ver
27、tex invariants based on graph eigenvalues or eigenvectorsJ, J. Chem. Inf. Comput. Sci. 31 (1991) 517-523.14I. Gutman, M. Medeleanu, On structure-dependence of the largest eigenvalue of the distance matrix of an alkaneJ, Indian J. Chem. A 37 (1998) 569-573.15曾沁雪.图的无符号拉普拉斯谱半径的若干结果D.华东师范大学.2012:13-16.1
28、6R. Xing, B. Zhou, On the distance and distance signless Laplacian spectral radii of bicyclic graphsJ. Linear Algebra Appl. 439 (2013) 39553963.17R. Xing, B. Zhou, J. Li, On the distance signless Laplacian spectral radius of graphsJ, Linear Multilinear Algebra (2013), in press, http:/dx.doi.org/10.1080/03081087.2013.828720 .致 谢本论文的写作是在李老师的热情关怀和悉心指导完成的.无论是在论文的选题、构思和资料的收集方面，还是在论文的研究方法以及成文定稿方面，我都得到了李老师悉心细致的教诲和无私的帮助，特别是他广博的学识、深厚的学术素养、严谨的治学精神和一丝不苟的工作作风使我终生受益，在此表示真诚地感谢和深深的谢意.在论文的写作过程中，同学也给我提供了许多帮助和宝贵建议，在此一并致以诚挚的谢意.感谢所有关心、支持、帮助过我的良师益友.最后，向在百忙中抽出时间对本文进行评审并提出宝贵意见的各位专家表示衷心地感谢！
