对环的个数进行容斥证明矩阵树定理

· · 算法·理论

图论期中考试不允许提前交卷,没事干于是就想了想课堂上只介绍没证明的矩阵树定理怎么证明(当年打OI的时候把板子过了就没管了...),想到了一种纯粹从行列式每一项来考虑的证明方法,于是打算记录下来.当然这个方法早就有人想出来了,不想看我的证明的可以去看这两篇.

【学习笔记】矩阵树定理

矩阵树定理证明 - 洛谷专栏

矩阵树(kirchhoff)定理:

设G=(V,E)是一个无自环的无向图.

定义度数矩阵D(G)为

𝐷_{𝑖𝑖}(𝐺)=deg_i,𝐷_{ij}=0,𝑖≠𝑗

设A(G)表示邻接矩阵

定义Kirchhoff 矩阵L为

𝐿(𝐺)=𝐷(𝐺)−𝐴(𝐺)

图G的所有生成树个数等于L的任一n-1阶代数余子式

证明:

先考虑L的代数余子式M_{ii}

M_{ii}=\sum_a(-1)^{sgn(a)}\prod_{j\not=i}L_{ja_j}

其中a是一个没有i的排列,sgn(a)表示a逆序对的个数的奇偶性,偶数为1,奇数为-1

将L_{j,a_j}中D_{jj}和A_{ja_j},a_j\not=j分别写出来

M_{ii}=\sum_a(-1)^{sgn(a)}\prod_{a_j=j}D_{jj}\prod_{a_j\not=j}(-1)A_{ja_j}

考虑(-1)^{sgn(a)}\prod_{a_j=j}D_{jj}\prod_{a_j\not=j}(-1)A_{ja_j}代表什么

因为$a$是一个排列,所以所有$(j,a_j)$相连会形成一个环(图论里称之为圈),而这些环正好对应这个排列 $\prod_{a_j=j}D_{jj}\prod_{a_j\not=j}A_{ja_j}$于是代表选出一个至少包含有$(j,a_j)$这些边组成的环且$|E|=|V|-1$的$G$的子图的方案数 对于环上相邻三个(或两个)点$(j,a_j)(a_j,a_{a_j})$,在排列中交换$a_j$和$a_{a_j}$会使整个排列逆序对数量奇偶性反转,而环的大小减$1

因此对于每个环,环的大小+1与该环代表的排列的逆序对个数奇偶性相同

因此(-1)^{sgn(a)}\prod_{a_j\not=j}(-1)=(-1)^{sgn((j,a_j)相连形成的子图的环的个数)}

(-1)^{sgn(a)}\prod_{a_j=j}D_{jj}\prod_{a_j\not=j}(-1)A_{ja_j}=(-1)^{sgn((j,a_j)相连形成的子图的环的个数)}\prod_{a_j=j}D_{jj}\prod_{a_j\not=j}A_{ja_j}

生成树个数就是环的个数为0且|E|=|V|-1的G的子图的个数,行列式就是对于环个数的一个容斥

因此生成树个数等于M_{ii}

现在考虑M_{ij},i\not=j

这表示一定选择边(i,j)的情况下对于环的个数做容斥

证毕

根据这个方法,有向图的生成树定理也很快就能推出来,这里不再赘述