拉普拉斯矩陣

拉普拉斯矩陣，有時也稱為導納矩陣（Cvetković等人 1998，Babić等人 2002）或基爾霍夫矩陣，是一個圖 ，其中 是一個無向、無權圖，沒有圖環 或從一個節點到另一個節點的多重邊， 是頂點集， ，並且 是邊集，是一個 對稱矩陣，每行每列對應一個節點，定義如下：

(1)

其中 是度矩陣，它是從頂點度形成的對角矩陣，而 是鄰接矩陣。因此， 的對角元素 等於頂點 的度，而非對角元素 為 如果頂點 與 相鄰，否則為 0。

圖的拉普拉斯矩陣在 Wolfram 語言 中實現為KirchhoffMatrix[g].

拉普拉斯矩陣的歸一化版本，表示為 ，類似地定義為

(2)

(Chung 1997, p. 2).

拉普拉斯矩陣是多元微積分中拉普拉斯運算元的離散 аналог，並透過衡量圖在一個頂點與其附近頂點的值的差異程度來達到類似的目的。拉普拉斯矩陣出現在圖上的隨機遊走和電路網路的分析中（Doyle 和 Snell 1984），尤其是在電阻距離的計算中。拉普拉斯運算元也出現在矩陣樹定理中。