複製鏈接
請複製以下鏈接發送給好友

拉普拉斯矩陣

鎖定
拉普拉斯矩陣(Laplacian matrix) 也叫做導納矩陣、基爾霍夫矩陣或離散拉普拉斯算子,主要應用在圖論中,作為一個圖的矩陣表示
中文名
拉普拉斯矩陣
外文名
Laplacian matrix
別    名
導納矩陣,吉爾霍夫矩陣
主要應用
在圖論中,作為一個圖的矩陣表示

目錄

拉普拉斯矩陣定義

給定一個有
個頂點的圖
,它的拉普拉斯矩陣
定義為:
其中
為圖的度矩陣,
為圖的鄰接矩陣。度矩陣在有向圖中,只需要考慮出度或者入度中的一個。經過計算可以得
拉普拉斯矩陣 拉普拉斯矩陣
1、若
,則
為頂點
的度。
2、若
,但頂點
和頂點
相鄰,則
3、其它情況
也可以將這三種值通過除以
進行標準化。

拉普拉斯矩陣性質

  1. 拉普拉斯矩陣是半正定矩陣
  2. 特徵值中0出現的次數就是圖連通區域的個數;
  3. 最小特徵值是0,因為拉普拉斯矩陣每一行的和均為0;
  4. 最小非零特徵值是圖的代數連通度

拉普拉斯矩陣示例

度矩陣
鄰接矩陣
拉普拉斯矩陣
拉普拉斯矩陣 拉普拉斯矩陣
度矩陣 度矩陣
鄰接矩陣 鄰接矩陣
拉普拉斯矩陣 拉普拉斯矩陣