Matrix Tree

无向图关联矩阵 \(B\)，行是点，列是边。若 \(e_k=(v_i,v_j)\) 那么 \(B_{ik},B_{jk}\) 中一个为 \(1\) 一个为 \(-1\)。它的 Kirchhoff 矩阵为 \(BB^T\)，也即度数矩阵 \(-\) 邻接矩阵。

性质：

1. 任意图 \(G\) 的 Kirchhoff 矩阵 \(C\) 的行列式为 \(0\)（行/列向量和为 \(0\) 向量）

2. 不连通图 \(G\) 的 Kirchhoff 矩阵 \(C\) 的任一个 \(n-1\) 阶主子式行列式为 \(0\)

3. 若 \(G\) 是一棵树，任一个 \(n-1\) 阶主子式行列式为 \(1\)

根据 Cauchy–Binet formula，把 \(C_r=B_rB_r^T\) 展开，得到：

\[ \begin{aligned} |C_r|=|B_rB_r^T|&=\sum_{S\subset \{1,2,\dots,m\},|S|=n-1}|(B_r)_S||(B_r)_S^T|\\ &=\sum_{S\subset \{1,2,\dots,m\},|S|=n-1}|(B_r)_S|^2 \end{aligned} \]

若 \(S\) 中 \(n-1\) 条边形成了树，那么贡献 \(1\)；否则贡献 \(0\)

推广：

1. 自环删掉，重边 \((i,j)\) 有 \(m\) 条边，则 \(C_{ij}=C_{ji}=-m\)，度数同样要计算在内。

2. 有向图，入度矩阵 \(-\) 邻接矩阵，行向量之和为 \(0\) 向量。

3. 边带权，令 \(C_{ij}=C_{ji}=-w_{ij},C_{ii}=-\sum_{i\neq j}C_{ij}\)。则 \(n-1\) 阶主子式的值为：

\[ \sum_{T\text{ form a tree }}\left(\prod_{e\in T}w_e\right) \]

4. 求恰有 \(k\) 条特殊边的生成树个数，把 \(k\) 条边边权设为 \(x\)，那么 \(n-1\) 阶主子式的值是一个多项式，对应阶的系数即为答案。可以用插值而不是多项式高消求解。