Kirchhoff 矩阵树定理的无向图情况
定义
无向图无自环。
设 \(G\) 为包含 \(n\) 个点，\(m\) 条边的无向图。
设 \(\deg(i)\) 表示顶点 \(i\) 的度数，\(E(i,j)\) 表示顶点 \(i\) 与 \(j\) 连边的条数。
记边 \(i\) 的起点为 \(x_i\)，终点为 \(y_i\)（这里对于无向图任意（因为不会有影响），这个定义在有向图中通用）
记图 \(G\) 的所有生成树个数为 \(t(G)\)。
度数矩阵 \(D\)：
邻接矩阵 \(A\)：
Laplace 矩阵（亦称 Kirchhoff 矩阵） \(L\)：
关联矩阵 \(M\) 为大小 \(n \times m\) 的矩阵：
减关联矩阵 \(M_0(G)\) 为关联矩阵 \(M(G)\) 去掉最后一行后的大小为 \((n-1) \times m\) 的矩阵。
子减关联矩阵 \(M_0(G)[S]\) 为选出 \(M(G)\) 的列构成子集 \(S\)，\(|S|=n-1,S\subseteq [1,m]\)。
\(L_0(G)\) 表示 \(L(G)\) 去掉最后一行和最后一列的 \(n-1\) 阶主子矩阵。
以下所有 \(L(G),D(G),A(G),M(G),M_0(G),L_0(G)\) 简记为 \(L,D,A,M,M_0,M_0[S],K_0\)
定理
其中：
表示 \(L\) 去除第 \(i\) 行和第 \(i\) 列后的子矩阵。
相当于 \(L\) 的所有 \(n - 1\) 阶主子式均等于 \(t(G)\)。
证明
引理 1
证
引理 2
令 \(S\) 为原图的子边集，\(|S|=n-1\)，\(P(S)\) 表示事件： \(S\) 构成原图的生成树。
则有：
证
TASK 1
若原图没有构成树，则存在简单环 \(C(e_{i_1},e_{i_2},\cdots,e_{i_k})\)。
对于 \(M_0[C]\)，考虑按环的一种遍历顺序重新排列，可以发现用前 \(k-1\) 列乘上 \(1\) 或 \(-1\) 后的和可以表出第 \(k\) 列（会发现环是否包含了第 \(n\) 行，都可以表出），故 \(M_0[C]\) 线性相关， \(\det M_0[C] = 0\)。
而 \(M_0[C]\) 是 \(M_0[S]\) 的子矩阵，故 \(\det M_0[S]=0\)。
TASK 2
若 \(S\) 构成树，则可以执行下面的操作：
- 找到一个叶子节点 \(u\) 。
- 会发现 \(u\) 对应行只有一列非 \(0\)。
- 在 \(M_0[S]\) 用这一行消去其他行（实际上只能消去与它相连的那个点）
- 无视这个点，从头开始继续做，直到只剩一个点。
最后会发现对 \(M_0[S]\) 做一些初等行变换中的交换（只改变正负号） 在 \(M_0[S]\) 只有主对角线上非 \(0\) 且全为 \(1\) 或 \(-1\)，故 \(|\det M_0[S]|=1\)。
引理 3 （Binet-Cauchy 定理）
定义大小为 \(n\times m\) 的矩阵 \(A,B\)，则：
其中 \(A[S],B[S]\) 定义与 \(M_0[S]\) 相同。
证
判断排列奇偶直接展开即可。
Main
根据引理 1 可知：
根据引理 3 可知：
根据引理 2 可知：
- 若 \(S\) 构成生成树，\(|\det M_0[S]|=1\)，对原式贡献为 \(1\) 。
- 否则不构成生成树，对原式贡献为 \(0\)。
所以 \(\det L_0=t(G)\)。
可以发现，可以通过交换标号使得所有 \(n-1\) 阶主子矩阵成为 \(L_0\)。
即证。