图谱论(Spectral Graph Theory)

Du00　du00cs@gmail.com　2011.5.2

声明：英语以及专业水平不是一般地有限，写得不好随便喷，仅供个人参考。

1         图谱论(Spectral graph theory)

    在数学中，图谱论是从图的邻接矩阵或拉普拉斯矩阵出发，通过特征多项式，特征值和特征向量来研究图的性质。

    一个无向图对应对称的邻接矩阵，因而也有对应的实特征值（值的集合称作图的谱）和完备的标准正交向集。

    由于邻接矩阵与点的标记有关，谱是一个图常量。

    当两个图的邻接矩阵有相同的特征值集时，它们被称为是谱相似的。

    谱相似的图不必同构，但同构的图必谱相似。

参考文献

维基词条Spectral Graph Theory

2         拉普拉斯矩阵(Laplacian Matrix)

  在图论中拉普拉斯矩阵(Laplacian Matrix)，有时候也被称作导纳矩阵(Admittance matrix)或者基尔霍夫矩阵(Kirchohoff matrix)，是图的一种矩阵表示。与基尔霍夫定理(Kirchhoff’s theorem)一起可以计算一个给定图的生成树的数量。

2.1       定义

对于给定的有n个结点的简单图G，它的拉普拉斯矩阵 http://s6/middle/439371b507a31ee312ec5&690Graph Theory" TITLE="图谱论-Spectral Graph Theory" />定义为

http://s5/middle/439371b54c5f34dea7ff4&690Graph Theory" TITLE="图谱论-Spectral Graph Theory" />

也就是说，它是图的度矩阵和邻接矩阵的差。归一化的拉普拉斯矩阵定义为

http://s16/middle/439371b54c5f34de9404f&690Graph Theory" TITLE="图谱论-Spectral Graph Theory" />

2.2       示例

  下面是一个有标号图的拉普拉斯矩阵的简单例子。

http://s12/middle/439371b54c5f34de299bb&690Graph Theory" TITLE="图谱论-Spectral Graph Theory" />

2.3       性质

  对于图G和它的拉普拉斯矩阵L，且矩阵的特征值是http://s12/middle/439371b54c5f34dfa146b&690Graph Theory" TITLE="图谱论-Spectral Graph Theory" /> ：

  L是半正定的，http://s5/middle/439371b54c5f34df757d4&690Graph Theory" TITLE="图谱论-Spectral Graph Theory" /> ；

  拉普拉斯矩阵的特征值中0的数目是图的连通分量的个数；

  http://s11/middle/439371b54c5f34dfcd0ba&690Graph Theory" TITLE="图谱论-Spectral Graph Theory" />.因为每一个拉普拉斯矩阵有一个特征向量[1, 1, …, 1]，对每一行，加上相应的结点度到-1的邻结点，由矩阵定义从而得到特征值0；

  http://s5/middle/439371b54c5f34df3a904&690Graph Theory" TITLE="图谱论-Spectral Graph Theory" />也被称为代数连通度(algebraic connectivity)；

  最小的非0特征值称作谱间隔(spectral gap)或费德勒值(Fiedler value)。

参考文献

维基词条Laplacian Matrix