● 摘要
设图G是一简单无向图， 图G 的顶点集V（G）={ } ，边集E（G）={ } ，G 的邻接矩阵A （G）定义为一个N*N 阶的（0，1）对称矩阵（ ） ，其中 =1 当且仅当与连接， =0 当且仅当 与 不连接或i=jG 的点边无向关联矩阵C（G）为一 n*m 阶(0，1) 矩阵（ ） ，其中 =1当且仅当 与边 相关联。 图G的邻接矩阵A（G）的特征多项式称为图G 的特征多项式记为?（G）， 则?（G）= det（xI-A（G））。图G 的特征多项式的全部特征值称为G的谱记作 SpecG 。 设图G 的无向点边关联矩阵为C（G），则称Q（G）=C（G）C（G） 为图G的拟拉普拉斯矩阵，u（G,x）=det（xI-Q（G））称为图G 的拟拉普拉斯特征多项式，其全部特征值称为图G的拟拉普拉斯谱。 图的谱在最近得到了越来越多的研究，它在量子化学的分子图形理论中有广泛的应用，某些分子结构可应图形表示，它的特征值反映了分子中中子的能级水平和分子结构的稳定性，在计算机网络中要考虑网络的经济性（相应边数少）、有效性（相应的图直径短）和可靠性（相应图的连接度大）。近几年来，金芳蓉等人证明了图的次根小的图（网络）在边数一定时，其直径短，连通大。因此，图谱在计算机网络，通讯网络中得到了特别的应用。另外图谱在某些组合问题 及图的结构研究中也是必不可少的。图的特征多项式的研究是图谱中一个基础的重要 组成部分。
相关内容
相关标签