定義
給定一個有n個頂點的圖G,它的拉普拉斯矩陣 定義為:
L=D-A
其中D為圖的度矩陣,A為圖的鄰接矩陣。度矩陣在有向圖中,只需要考慮出度或者入度中的一個。經過計算可以得
1、若i =j,則
為頂點 的度。
2、若i≠ j,但頂點 和頂點 相鄰,則
3、其它情況
也可以將這三種值通過除以 進行標準化。
示例
圖 | 度矩陣 | 鄰接矩陣 | 拉普拉斯矩陣 |
性質
拉普拉斯矩陣是半正定矩陣;
特徵值中0齣現的次數就是圖連通區域的個數;
最小特徵值是0,因為拉普拉斯矩陣每一行的和均為0;
最小非零特徵值是圖的代數連通度。
1.拉普拉斯矩陣是半正定矩陣;
2.特徵值中0齣現的次數就是圖連通區域的個數;
3.最小特徵值是0,因為拉普拉斯矩陣每一行的和均為0;
4.最小非零特徵值是圖的代數連通度。