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

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.