论文部分内容阅读
图谱理论在计算机科学、通信网络、量子化学等众多学科中都有应用,由图的特征多项式可以直接得到图的谱,因此研究得到图的特征多项式对于研究这些学科都很有益。图的邻接矩阵A(G)表示了图中顶点与顶点之间的邻接关系,邻接矩阵的特征多项式称为邻接特征多项式。图的度对角矩阵是对角线上为每个顶点的度的对角矩阵,记为D(G)。Laplacian矩阵记为L(G)=D(G)-A(G),Laplacian矩阵的特征多项式称为Laplacian 特征多项式;signless Laplacian 矩阵记为Q(G)=D(G)+A(G), signless Laplacian矩阵的特征多项式称为signlessLaplacian特征多项式。图的各项特征多项式的特征根及其重数称为图的谱,分别为邻接谱、Laplacian谱和signless Laplacian谱。同谱而又非同构的图称为同谱图,分别为邻接同谱图(记为A-同谱图)、Laplacian同谱图(记为L -同谱图)和signless Laplacian同谱图(记为Q-同谱图)。冠图是通过多个图进行图操作所得到的复杂图,剖分图是在每条边上新添加一个顶点所得到的图。本文将冠图广义化并融合了剖分图操作,构造了两种新的广义冠图:广义剖分冠边图S(G)(?)H,和广义剖分冠点图S(G)(?)Hi。应用分块矩阵、舒尔补、矩阵的冠值等计算并证明了这两类广义冠图的邻接特征多项式、Laplacian特征多项式和signless Laplacian特征多项式。作为应用还得到了在特殊情况下这两种广义冠图的生成树数目和Kirchhoff指数,并给出了计算生成树数目的例子。随后还得到了一系列的邻接同谱图、Laplacian同谱图和signless Laplacian同谱图图簇,并给出了例子。本文的主要成果有:(1)定义了一类新的广义冠图--广义剖分冠边图S(G)(?)Hi。计算并证明了它的各项特征多项式。(2)计算并证明了在图G为r-正则图,图H1,...Hm均为图H时构造的非广义的剖分冠边图S(G)(?)H的L-谱、生成树个数和Kirchhoff指数。并给出了计算生成树数目的例子。(3)得到了一系列邻接同谱、Laplacian同谱和signless Laplacian同谱的广义剖分冠边图图簇,并给出了同谱图的例子。(4)定义了一类新的广义冠图--广义剖分冠点图S(G)(?)Hi。计算并证明了它的各项i特征多项式。(5)计算并证明了在图G为r-正则图,图H1,...Hn均为图H时构造的非广义的剖分冠点图S(G)(?)的L-谱、生成树个数和Kirchhoff指数。并给出了计算生成树数目的例子。(6)得到了一系列邻接同谱、Laplacian同谱和signless Laplacian 同谱的广义剖分冠点图图簇,并给出了同谱图的例子。