From Wikipedia, the free encyclopedia
拉普拉斯矩陣(英文:Laplacian matrix),簡稱拉氏矩陣,係圖論裏便嘅一種矩陣、描述圖啲綟戥啲檠之間拏褦嘅,由次數矩陣(對角陣)減去鄰接矩陣(對角線始終係零)得到。拉氏矩陣仲着攞嚟計生成樹嘅數量同埋估計正則圖嘅擴展性。拉氏矩陣係拉普拉斯算符嘅離散版本。
一幅圖個拉氏矩陣、幅有綟集同埋檠集嘅,係一個矩陣。拉氏矩陣定義係 ,其中係圖嘅次數矩陣,係圖嘅鄰接矩陣。綟同個拉氏矩陣相應就有:
其中,圖啲檠可以加有權重,係噉鄰接矩陣嘅元素就嘸一定係1,即係;相對應拉氏矩陣嘅啲值就係。
特別嚟講,拉普拉斯矩陣係一幅有單位矩陣嘅 -正則圖:
拉氏矩陣亦都可以由關聯矩陣計得出。令係一隻關聯矩陣,係噉拉氏矩陣有下式畀得出:
拉氏矩陣啲特徵值同埋特徵向量可以簡單噉攞下低條式表示:
一般攞表示拉氏矩陣啲特徵值(有時下標從1開始計)。特別嘅,第二細嘅個特徵值叫做Fiedler值,代表幅圖嘅代數連通度。個值愈大代表幅圖啲綟互相之間褦得愈多;反之啲拏褦愈少。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.