六边形迭代图上的归一化拉普拉斯谱及其应用文献综述

文献综述

文 献 综 述图论是一门应用广泛的数学分支, 它也是近年来离散数学与组合数学领域中较为活跃的分支之一。

1736年,数学家Euler运用图论的方法解决了哥尼斯堡七桥问题,这标志着一门新的学科图论的产生,从此这一新领域逐渐受到了人们的广泛关注。

1847年Kirchhof在研究电流理论时,引入了图的拉普拉斯矩阵,并利用它给出了著名的矩阵树定理。

因此,拉普拉斯矩阵又称为基尔霍夫矩阵。

图的拉普拉斯矩阵L(G)定义为: 其中D(G)和A(G)分别为图G的对角矩阵和邻接矩阵。

图的拉普拉斯矩阵的特征值的多重集称为图的拉普拉斯谱。

由于图的拉普拉斯矩阵是在图的邻接矩阵的基础上考虑了顶点的度这个与图的结构有着密切联系的量,所以,正如Mohar所说,图的拉普拉斯特征值更能反映图的图论性质。

因此,拉普拉斯特征值的研究引起了人们的高度重视。

自20世纪90年代以来,有关拉普拉斯特征值的综述文献如 Mohar [3]、Merris[4]等,及时报导研究进展,提出新的问题与猜想。