拉普拉斯矩陣

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

拉普拉斯矩陣英文Laplacian matrix),簡稱拉氏矩陣,係圖論裏便嘅一種矩陣、描述圖啲綟戥啲檠之間拏褦嘅,由次數矩陣對角陣)減去鄰接矩陣(對角線始終係零)得到。拉氏矩陣仲着攞嚟計生成樹嘅數量同埋估計正則圖嘅擴展性。拉氏矩陣係拉普拉斯算符離散版本

拉普拉斯矩陣同埋矩陣啲細特徵值特徵向量有用喺譜聚類聚類分析嘅一種方法)入便。

定義[編輯]

一幅圖個拉氏矩陣、幅有綟集同埋檠集嘅,係一個矩陣。拉氏矩陣定義係 ,其中係圖嘅次數矩陣係圖嘅鄰接矩陣。綟個拉氏矩陣相應就有:

其中,圖啲檠可以加有權重,係噉鄰接矩陣嘅元素就嘸一定係1,即係;相對應拉氏矩陣嘅啲值就係

特別嚟講,拉普拉斯矩陣係一幅有單位矩陣 -正則圖

[編輯]

啲綟編號 次數矩陣 鄰接矩陣 拉普拉斯矩陣
6n-graf.svg

戥關聯矩陣嘅拏褦[編輯]

拉氏矩陣亦都可以由關聯矩陣計得出。令係一隻關聯矩陣,係噉拉氏矩陣有下式畀得出:

特徵值同埋特徵向量[編輯]

拉氏矩陣啲特徵值同埋特徵向量可以簡單噉攞下低條式表示:

一般攞表示拉氏矩陣啲特徵值(有時下標從1開始計)。特別嘅,第二細嘅個特徵值叫做Fiedler值,代表幅圖嘅代數連通度。個值愈大代表幅圖啲綟互相之間褦得愈多;反之啲拏褦愈少。

特性[編輯]

  • 對稱嘅。
  • 正半定嘅,特別係對所有啲 都有
  • 係一個M矩陣
  • 列累加、行累加係出零。特別係特徵向量
  • 特徵值嘅重複次數係圖啲連通元件嘅數量;對於一幅連通嘅圖(成幅圖即係一隻連通元件),有且唯有

睇埋[編輯]