拉普拉斯矩阵

拉普拉斯矩阵，有时也称为导纳矩阵（Cvetković等人 1998，Babić等人 2002）或基尔霍夫矩阵，是一个图 ，其中 是一个无向、无权图，没有图环 或从一个节点到另一个节点的多重边， 是顶点集， ，并且 是边集，是一个 对称矩阵，每行每列对应一个节点，定义如下：

(1)

其中 是度矩阵，它是从顶点度形成的对角矩阵，而 是邻接矩阵。因此， 的对角元素 等于顶点 的度，而非对角元素 为 如果顶点 与 相邻，否则为 0。

图的拉普拉斯矩阵在 Wolfram 语言 中实现为KirchhoffMatrix[g].

拉普拉斯矩阵的归一化版本，表示为 ，类似地定义为

(2)

(Chung 1997, p. 2).

拉普拉斯矩阵是多元微积分中拉普拉斯算子的离散 аналог，并通过衡量图在一个顶点与其附近顶点的值的差异程度来达到类似的目的。拉普拉斯矩阵出现在图上的随机游走和电路网络的分析中（Doyle 和 Snell 1984），尤其是在电阻距离的计算中。拉普拉斯算子也出现在矩阵树定理中。