本文尚未完成

拉普拉斯矩阵(调和矩阵/基尔霍夫矩阵)

给定一个图$G(V,E)$，其拉普拉斯矩阵为$L=D-A$，其中$D$为图$G$的度矩阵，$A$为图的邻接矩阵。

如上图，该图的邻接矩阵$A$为

$$\left(\begin{array}{llllll}0 & 1 & 0 & 0 & 1 & 0 \\1 & 0 & 1 & 0 & 1 & 0 \\0 & 1 & 0 & 1 & 0 & 0 \\0 & 0 & 1 & 0 & 1 & 1 \\1 & 1 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 1 & 0 & 0\end{array}\right)$$

度数矩阵$D$为

$$\left(\begin{array}{llllll}2 & 0 & 0 & 0 & 0 & 0 \\0 & 3 & 0 & 0 & 0 & 0 \\0 & 0 & 2 & 0 & 0 & 0 \\0 & 0 & 0 & 3 & 0 & 0 \\0 & 0 & 0 & 0 & 3 & 0 \\0 & 0 & 0 & 0 & 0 & 1\end{array}\right)$$

得到的拉普拉斯矩阵$L$为

$$\left(\begin{array}{rrrrrr}2 & -1 & 0 & 0 & -1 & 0 \\-1 & 3 & -1 & 0 & -1 & 0 \\0 & -1 & 2 & -1 & 0 & 0 \\0 & 0 & -1 & 3 & -1 & -1 \\-1 & -1 & 0 & -1 & 3 & 0 \\0 & 0 & 0 & -1 & 0 & 1\end{array}\right)$$

关联矩阵

矩阵树定理(Matrix-Tree)

1. 对于无向图$G$，他的生成树个数等于其拉普拉斯矩阵任何一个$n-1$阶主子式^1的行列式的绝对值.

参考资料

https://zh.wikipedia.org/wiki/调和矩阵 (opens new window)

https://blog.csdn.net/xyz32768/article/details/81413569