毕业设计(论文)含割边的图的距离无符号拉普拉斯谱半径论文.doc
《毕业设计(论文)含割边的图的距离无符号拉普拉斯谱半径论文.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 研究问题及主要结论 本文讨论了含割边的连通图的距离无符号拉普拉斯谱半径
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 毕业设计 论文 含割边 距离 符号 拉普拉斯 半径
链接地址:https://www.31ppt.com/p-4027489.html