论文部分内容阅读
图谱理论是图论研究的重要分支,其中对图的多项式的研究是近年的热点。图的多项式是研究图谱的基础,在计算机科学、物理、化学、生命科学、控制工程等前沿方向均有重要应用。设图G的邻接矩阵记为A(G)、拉普拉斯矩阵记为L(G)、无符号拉普拉斯矩阵记为Q(G),这些矩阵对应的特征多项式分别为邻接特征多项式、拉普拉斯特征多项式、无符号拉普拉斯特征多项式,这些特征多项式对应的特征值及其重数分别构成图G的邻接谱、拉普拉斯谱、无符号拉普拉斯谱。通过图的各类矩阵可以求得对应的特征多项式和积和多项式,利用各类特征多项式可以计算对应的谱及一些指标,利用各类积和多项式可以统计对应的积和同谱图。本文研究了几类复杂图的特征多项式及应用。复杂图包括:图G和m个图H1,H2,(42),Hm构造的广义剖分冠边图S(G)!i(?)Hi、图1G和图2G构造的点剖分联图G1"G2和边剖分联图G1!G2。通过矩阵的相关性质给出并证明了这些复杂图的邻接特征多项式、拉普拉斯特征多项式、无符号拉普拉斯特征多项式和广义特征多项式;同时构造了无数多对A-同谱图和L-同谱图及计算了这些复杂图的生成树数目、Kirchhoff指数和类拉普拉斯能量不变量。还利用计算机编程的方式得到了顶点数n<10的所有非同构图,计算了所有图的积和A-多项式,积和L-多项式,积和Q-多项式及补图的积和A-多项式,给出了所有积和A-、A&(?)-、L-和Q-同谱图。本文主要成果如下:(1)计算并证明了广义剖分冠边图S(G)!(?)Hi的邻接特征多项式、拉普拉斯特征多项式及原图限定条件时的生成树数目、Kirchhoff指数和类拉普拉斯能量不变量,同时构造了无数多对A-同谱图和L-同谱图;(2)计算并证明了点剖分联图G1"G2和边剖分联图G1!G2的广义特征多项式,由广义特征多项式得到邻接特征多项式、拉普拉斯特征多项式和无符号拉普拉斯特征多项式及原图限定条件时的生成树数目、Kirchhoff指数和类拉普拉斯能量不变量;(3)通过计算机编程的方式生成顶点数n<10的所有非同构图以graph6格式存储,并将此格式存储的图转换为邻接矩阵存储,然后用Maple软件读取邻接矩阵并计算得到度矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵和补图的邻接矩阵,计算这些矩阵对应的积和多项式,通过比较顶点数相同的积和多项式,求得了顶点数n<10的所有非同构图的积和A-、A&(?)-、L-和Q-同谱图并画出了所有的积和同谱图对,最后对一般同谱图和积和同谱图进行了比较分析,得出对于谱确定的研究,积和谱优于一般谱的结论。