谱图论

谱图论是通过分析图的拉普拉斯矩阵的特征值和特征向量研究图的性质。

拉普拉斯矩阵

定义1：
对于给定的图及其邻接矩阵，它的拉普拉斯矩阵定义为：
(1)
式中，为对角度矩阵。

定义2：
给定的图及其邻接矩阵，它的归一化拉普拉斯矩阵定义为：
(2)

拉普拉斯矩阵的性质

1. 拉普拉斯矩阵与任意向量右乘，其结果如下公式3

(3)
也即是，为节点与其邻居的差的和。

1. 的结果为相邻节点之间的差的平方和，如下公式4

(4)

拉普拉斯的特征值和特征向量

定理2.3:
对于图，其拉普拉斯的特征值是非负的。
(5)

若某个特征向量中的每个元素均相等，则其对应的特征值为0。

定理2.4
给定一个图，其拉普拉斯矩阵的特征值为0的数目等于图中连通分量的数目。
特征值0对应的特征向量为连通分量内节点元素相等，其它元素均为0。