拉普拉斯矩阵

给定一个有n个顶点的图G，它的拉普拉斯矩阵定义为:

L=D-A

其中D为图的度矩阵，A为图的邻接矩阵。度矩阵在有向图中，只需要考虑出度或者入度中的一个。经过计算可以得

1、若i=j,则

为顶点的度。

2、若i≠ j,但顶点和顶点相邻，则

3、其它情况

也可以将这三种值通过除以进行标准化。

1. 拉普拉斯矩阵是半正定矩阵；
2. 特征值中0出现的次数就是图连通区域的个数；
3. 最小特征值是0，因为拉普拉斯矩阵每一行的和均为0；
4. 最小非零特征值是图的代数连通度。