读书笔记摘抄新闻资讯
拉普拉斯矩阵
拉普拉斯矩阵(Laplacian matrix) 也叫做导纳矩阵、基尔霍夫矩阵或离散拉普拉斯运算元，主要套用在图论中，作为一个图的矩阵表示。
基本介绍
- 中文名：拉普拉斯矩阵
- 外文名：Laplacian matrix
- 别称：导纳矩阵，吉尔霍夫矩阵
- 主要套用：在图论中，作为一个图的矩阵表示
定义
给定一个有n个顶点的图G，它的拉普拉斯矩阵
定义为:
L=D-A
其中D为图的度矩阵，A为图的邻接矩阵。度矩阵在有向图中，只需要考虑出度或者入度中的一个。经过计算可以得
1、若i =j,则
2、若i≠ j,但顶点 和顶点
相邻，则
3、其它情况
也可以将这三种值通过除以
进行标準化。
示例
| 图 | 度矩阵 | 邻接矩阵 | 拉普拉斯矩阵 |
|---|---|---|---|
|  度矩阵 |  |  |
性质
- 拉普拉斯矩阵是半正定矩阵；
- 特徵值中0齣现的次数就是图连通区域的个数；
- 最小特徵值是0，因为拉普拉斯矩阵每一行的和均为0；
- 最小非零特徵值是图的代数连通度。