拉普拉斯矩阵及基尔霍夫矩阵树定理

1 Laplacian matrix

1.1 简介

　　Laplacian matrix又名Kirchhoff matrix，是一种图的矩阵表示方法，本节主要讨论Laplacian matrix的几种简单应用。

1.2 定义

1.2.1 无向图

　　给定一个有$n$个顶点$m$条边的无向图图$G=(V, E)$，则该图的Laplacian matrix$L:=(l_{i,j})_{n\times n}$,定义为：
$$
L=D-A
$$
　　其中$D$表示$G$的度数矩阵，$A$表示$G$的度数矩阵。

1.2.2 有向图

　　在有向图中，由于出入度的引入，Laplacian matrix可以被表示为如下形式：
$$
L=\left\{
\begin{aligned}
&deg(v_i) && if\ \ i = j\\
&-1 && if\ \ i \neq j\ and\ v_i\ is\ adjaccent\ to\ v_j\\
&0 && otherwise\\
\end{aligned}
\right.
$$

1.2.3 Symmetric normalized Laplacian

　　另一种常用的Laplacian matrix为其正则标准型：
$$
L^{sym}:=D^{-\frac{1}{2}}LD^{\frac{1}{2}}=I-D^{-\frac{1}{2}}AD^{\frac{1}{2}}
$$
　　也可以表示为：
$$
l^{sym}_{i,j}=\left\{
\begin{aligned}
&1 && if\ \ i = j\ and\ deg(v_i)\ne 0\\
&-\frac{1}{\sqrt{deg(v_i)\times deg(v_j)}} && if\ \ i \neq j\ and\ v_i\ is\ adjaccent\ to\ v_j\\
&0 && otherwise\\
\end{aligned}
\right.
$$

1.3 性质

1.3.1 Laplacian matrix是半正定的

　　考虑图$G$的关联矩阵$M_{m\times n}$，其中边$e$（包含了顶点$i$和顶点$j$，且$i>j$）和点$v$构成元素$M_{ev}$
$$
M_{ev}=\left\{
\begin{aligned}
&1 && if\ v = i\\
&-1 && if\ v = j\\
&0 && otherwise\\
\end{aligned}
\right.
$$
　　则可由此算出其Laplacian matrix：
$$
L = M^TM
$$
　　这是由于$M^T$的一行或$M$的一列表示其中一个顶点$v$与边集$E$的关系，当$v$相同时，与之相连的边的平方为1，相加和为度数，当$v$不同时，若这两点若通过一条边相连，其对应$e$位置的乘积为-1，否则为0，这正是Laplacian matrix的定义。

　　下面考虑$L$的特征值$\lambda_i$，其对应的单位特征向量为$v_i$，则有
$$
\begin{align}
\lambda_i &= v_i^TLv_i\\
&=v_i^TM^TMv_i\\
&=(Mv_i)^T(Mv_i)
\end{align}
$$
　　由于$(Mv_i)^T(Mv_i) \ge 0$，因此$\lambda_i \ge 0$。

　　所以$L$的任意一个特征值都是非负的，则$L$是半正定的。

1.3.2 Laplacian matrix任意一行、一列的和为0

　　由$L$的定义，其对角线上的元素为节点的度，其余元素的和为与其相连的节点数的个数的相反数，二者相加为0。

1.3.3 Laplacian matrix有一个特征值为0

　　由性质1.3.2，取向量$v_0=(1, 1,…,1)$，有$Lv_0=0$，且有$Lv_0=\lambda_0v_0$，当$\lambda_0 = 0$时成立，所以$L$存在一个零特征值，这也同时证明了$L$是奇异的。

1.3.4 Laplacian matrix任意两个代数余子式的值都相等

　　首先我们证明，代数余子式$A_{i,j}$与$A_{i,k}$（$j \ge k$）的值相等，即证$(-1)^{i+j}|A_{i,j}|=(-1)^{i+k}|A_{i,k}|$，即
$$
(-1)^{j-k}|A_{i,j}|=|A_{i,k}|
$$
　　将$A_{i,j}$中的所有列都加到第$k$列上，得到矩阵$A_0$，取出其第$k$列得到列向量$\vec{k}$，由性质1.3.2，$\vec{k}$为除去$L$中第$j$列后所有列相加的和，即有
$$
\vec{k}+\vec{j}=0
$$
　　即$\vec{k}=-\vec{j}$，将$A_0$的第$k$列取相反数，得到$A_1$，则$A_1$的第$k$列与$L$的第$j$列相等，且由行列式的性质$|A_1|=-|A_{i,k}|$

　　下面我们将$A_1$中第$k$列的值向右对换，直到这一列处于$A_{i,k}$中第$j$列的位置，则这个过程经过了$j-k-1$次对换，这时我们得到$A_2=A_{i,k}$，则$|A_{i,k}|=|A_2|=(-1)^{j-k-1}|A_1|=(-1)^{j-k}|A_{i,j}|$，证毕。

　　完全类似地，我们可以得到，代数余子式$A_{i,j}$与$A_{k,j}$的值相等。

　　由以上两个结论，不难证明$L$的任意两个代数余子式的值都相等。

2 Kirchhoff’s matrix tree theorem

2.1 定理内容

　　无向图的生成树个数等于其Laplacian matrix的任意一个代数余子式的值。

2.2 证明

2.2.1 引理——柯西-比内公式

　　设矩阵$A_{n\times m}$，$B_{m\times n}$，我们定义$[m]$是集合${1, …, m}$，规定$(\begin{matrix}[m]\\ n\end{matrix})$表示$[m]$的所有大小为$n$的子集组成的集合。

　　对于$S\in(\begin{matrix}[m]\\ n\end{matrix})$，记$A_S$为$A$中列指标位于$S$中的子矩阵，类似定义$B_S$为$B$中行指标位于$S$中的子矩阵，则有：
$$
det(AB)=\sum_Sdet(A_S)det(B_S)
$$
　　该定理证明比较复杂，不在本文讨论范围内，可查阅参考资料[2]。

2.2.2 Kirchhoff’s matrix tree theorem

　　设$G$为不具有重边和自环的无向图，由1.3.4，我们只需要证明$L$的一个代数余子式$A_{1,1}$能够使定理成立成绩，使用引理2.2.1，得到：
$$
\begin{align}
det(A_{1,1}) &= det(M_1M_1^T)\\
&=\sum_S det(M_{1,S})det(M_{1,S}^T)\\
&=\sum_S det(M_{1,S}M_{1,S}^T)\\
&=\sum_S det(M_{1,S})^2
\end{align}
$$
　　其中$S\in(\begin{matrix}[m]\\ n-1\end{matrix})$，$(\begin{matrix}[m]\\ n-1\end{matrix})$包含了所有选出$n-1$条边的方案（边集），如果这$n-1$条边是连通的，则其生成图一定为一棵树。下面，我们只需证明

1. 当这$n-1$条边不连通，$det(M_{1,S})=0$
2. 当这$n-1$条边连通，$det(M_{1,S})=\pm 1$

　　设这$n-1$条边不连通，考虑$M_{1,S}M_{1,S}^T$，其为$G$以$S$为边集的导出子图的Laplacian matrix$(L)$去掉第一行第一列得到的代数余子式，使第一行第一列保持原先位置的前提下交换$L$的行列，使新矩阵的连通分支分块并依次排列在对角线上，显然非对角线元素的连通块之间没有连边，矩阵为分块对角阵：
$$
\left(\begin{matrix}
T_1 &\dots &0\\
\vdots &\ddots &\vdots\\
0 &\dots &T_p
\end{matrix}\right)
$$
　　则对任意的$i$，$T_i$均为其连通子图的Laplacian matrix，行列式为0，且$p \ge 2$，故即使去除$L$的第一行第一列，行列式依然为0。

　　设这$n-1$条边连通，使用数学归纳法：

　　当$n=2$，则显然有$det(M_{1,S})=\pm 1$。

　　假设对于$n-1$，$det(M_{1,S})=\pm 1$成立，此时所构成图的Laplacian matrix为$L$。

　　设新加入点的标号为$n$，其加入在了标号为$u$的节点上。在边数为时$n-1$，有$det(M_{1,S}M_{1,S}^T)=det(M_{u,S}M_{u,S}^T)$，则新图的Laplacian matrix $(L’)$的去掉第$u$行第$u$列的代数余子式可以表示为：
$$
A’=
\left(\begin{matrix}
M_{u,S}M_{u,S}^T &A\\
B &1
\end{matrix}\right)
$$

　　此时，$n$与左上角矩阵中的任何点均没有连线，所以$A、B$均为0矩阵，则有$det(A’)=det(M_{u,S}M_{u,S}^T)$，所以$L’$具有与$L$相同的代数余子式

　　至此，我们归纳证明了这$n-1$条边连通时，$det(M_{1,S})=\pm 1$，同时也证明了当$G$为一棵树时，其Laplacian matrix的代数余子式值为$\pm 1$。

　　综上所述，当图$G$的生成子图为树，$det(M_{1,S})^2=1$，否则$det(M_{1,S})^2=0$，也即对于任意的$S$，只要$S$中的边能构成树，其对总和贡献1，否则不计数，所以$\sum_S det(M_{1,S})^2=det(A_{1,1})$即为生成树的个数，故无向图的生成树个数等于其Laplacian matrix的任意一个代数余子式的值。

2.2.3 推广

　　我们规定了$G$为不存在重边与自环的无向图，下面进行对有重边和自环的普通图的推广。

　　自环：自环不可能对结果产生影响，假如原图存在自环剔除即可。

　　重边：重新定义Laplacian matrix为如下形式：
$$
L=\left\{
\begin{align}
&deg(v_i) &&if\ i=j\\
&-t &&if\ i\ne j\ and\ v_i\ is\ adjaccent\ to\ v_j\ by\ t\ times \\
&0 &&otherwise
\end{align}
\right.
$$
　　显然这样的定义不影响Laplacian matrix的性质，以上命题均可轻易得证。

　　有向图：有了上述定义，则有向图的Laplacian matrix也具有相应的性质，命题也可轻易得证。

参考文献

[1] Godsil, C.; Royle, G. (2001). Algebraic Graph Theory, Graduate Texts in Mathematics. Springer-Verlag.
[2] 642:550, Summer 2004, Supplement 3;The Cauchy-Binet formula.
[3] Chung, Fan (1997) [1992]. Spectral Graph Theory. American Mathematical Society. ISBN 978-0821803158.
[4] Chaiken, S.; Kleitman, D. (1978). “Matrix Tree Theorems”. Journal of Combinatorial Theory, Series A. 24 (3): 377–381. doi:10.1016/0097-3165(78)90067-5. ISSN 0097-3165.
[5] Tutte, W. T. (2001), Graph Theory, Cambridge University Press, p. 138, ISBN 978-0-521-79489-3.