冠图的谱及其应用研究

来源 :兰州理工大学 | 被引量 : 0次 | 上传用户:poilkjqwe123
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
谱图理论是图论的一个非常活跃而又重要的分支,它在计算机科学、通信网络、信息科学和量子化学等领域都有着广泛的应用。谱图理论研究的主要对象包括图的邻接谱,Laplacian谱以及图的signless Laplacian谱,并且图的各种谱之间相互联系。谱图理论研究的一个主要问题就是由矩阵的代数性质反映图的性质,而矩阵的代数性质主要为矩阵的特征根性质。图的邻接矩阵表示图中各顶点之间的连接关系,记为A(G);图的Laplacian矩阵记为L(G)?D(G)?A(G),其中D(G)表示图G的度对角矩阵;图的signless Laplacian矩阵记为Q(G)?D(G)?A(G)。图G的矩阵的特征根及其对应的重数构成图的谱。图的邻接矩阵的特征根及其对应的重数构成图的邻接谱,记为A-谱;图的 Laplacian矩阵的特征根及其对应的重数构成图的 Laplacian谱,记为L-谱;图的 signless Laplacian矩阵的特征根及其对应的重数构成图的signless Laplacian谱,记为Q-谱。  图的矩阵与图的结构有着紧密的联系。由矩阵的定义可知,图的 Laplacian矩阵和signless Laplacian矩阵都表示为邻接矩阵与度矩阵的关系。由此可以通过一个参数t将三个矩阵联系在一起,表示成广义矩阵A(G)-tD(G)。当t=0时,得到的是图G邻接矩阵A(G);当t=1时,得到的是-L(G);当t=-1时,得到的是图G的 signless Laplacian矩阵 Q(G)。图 G的广义特征多项式记为此处为公式,其中I是与邻接矩阵 A(G)同维数的单位矩阵。根据参数t的不同取值,图G的邻接特征多项式、Laplacian特征多项式及signless Laplacian特征多项式分别可以表示为此处为公式。广义特征多项式将邻接特征多项式、Laplacian特征多项式和signless Laplacian特征多项式合成在一起,大大减少了图谱计算的工作量。  图的谱蕴含着图的许多信息。冠图是一种由图操作得到的复杂图,冠图的谱更加难以计算。文中定义了四类冠图分别是:剖分图的冠点图 G1◇G2、剖分图的冠边图 G1☆G2、点剖分冠图G1⊙G2、边剖分冠图G1(-)2G。应用分块矩阵、矩阵的coronal、克罗内克积等计算并证明了这几类冠图的谱可以表示为原图G1和G2的谱;得到了许多A-同谱图,L-同谱图及Q-同谱图;作为应用,由冠图的Laplacian谱得到了生成树数目以及Kirchhoff指数;并构造出了新冠图的一些A-整谱图。  本文的主要成果有:  (1)计算并证明了剖分图的冠点图G1◇G2、剖分图的冠边图G1☆G2的邻接谱,Laplacian谱以及signless Laplacian谱;  (2)得到剖分图的冠点图G1◇G2、剖分图的冠边图G1☆G2的生成树数目及Kirchhoff指数;  (3)计算并证明了剖分图的冠点图G1◇G2、剖分图的冠边图G1☆G2的A-整谱图。  (4)计算并证明了点剖分冠图G1⊙G2、边剖分冠图G1(-)2G的广义特征多项式;  (5)得到点剖分冠图G1⊙G2、边剖分冠图G1(-)2G的广义同谱图;  (6)计算并证明了点剖分冠图G1⊙G2、边剖分冠图G1(-)2G的邻接特征多项式、Laplacian特征多项式及signless特征多项式;  (7)计算并证明了点剖分冠图G1⊙G2、边剖分冠图G1(-)2G的A-整谱图;  (8)得到点剖分冠图G1⊙G2、边剖分冠图G1(-)2G的生成树数目及Kirchhoff指数;  (9)得到点剖分冠图G1⊙G2、边剖分冠图G1(-)2G的A-同谱图、L-同谱图及Q-同谱图。
其他文献
粒子群优化算法(ParticleSwarmOptimization,PSO)是一种新型的演化计算技术,已经被证明是一种有效的全局优化方法,并且广泛应用于函数优化、神经网络训练等领域,但存在优化复杂问
皮革轮廓智能跟踪及测量技术是指根据拍摄的皮革图像,从中提取出皮革的形状信息,内部缺陷信息,并计算出皮革表面可用面积的技术。此技术可以广泛应用于皮革行业的工业生产,在
P2P(Peer-to-Peer)技术因其强大的资源共享和平衡网络负载能力,近年来在因特网上迅猛发展并给网络用户带来巨大便利,但是其自身的开放、动态、异构和匿名等特点使得P2P系统面临
近年来,基于互联网的考试系统应运而生。网络考试系统彻底改变传统的考试方式。传统的考试方式需要运用手工方式发放试题和提交试卷,手续繁琐、缓慢及效率低下。网络考试使得
纹理合成以人工生成纹理为目的,是计算机图形学与图像处理的重要研究领域。基于样图的纹理合成是近些年来出现的一种新技术,它以小块纹理图像作为输入合成任意大的同类纹理,
数字水印是保护知识产权的一种新技术,它通过在数字产品中嵌入版权信息—水印来证实该作品的所有权,被嵌入的信息通常是不可见或不可察觉的,但通过检测器可以提取出水印或者
无线网状网(Mesh)是由Ad Hoc网络发展而来的相对静态的无线网络,是Internet的无线版本。无线网状网具有自组织、自配置和自治愈的特点,能够自动地将各个节点组织起来建立一个
支持向量机SVM是实现统计学习理论的通用学习方法,其优异的泛化性能使得支持向量机在模式识别、回归分析和预测、密度估计等领域都得到了实际应用。当SVM用于回归分析和预测
面向服务体系结构(Service Oriented Architecture,SOA)对现代软件开发模式产生了深远的影响,它通过服务的发布、发现以及绑定等机制为其他的应用程序提供服务。SOA具有松散
随着计算机技术和互联网的普及,网络安全成为每一个网络用户所必须考虑的一个重要问题。一旦网络安全问题发生,通常会造成严重的后果。在越来越多的计算机用户将个人计算机接