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

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

矩阵树(kirchhoff)定理:

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

定义度数矩阵$D(G)$为

设$A(G)$表示邻接矩阵

定义Kirchhoff 矩阵$L$为

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

证明:

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

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

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

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

$D_{jj}$表示任选点$j$相连的边,$A_{ja_j}$表示选取$(j,a_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)相连形成的子图的环的个数)}$

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

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

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

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

证毕

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