论文部分内容阅读
谱图理论是图论的一个非常活跃而又重要的分支,它在计算机科学、通信网络、信息科学和量子化学等领域都有着广泛的应用。谱图理论研究的主要对象包括图的邻接谱,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-同谱图。