矩阵树定理学习笔记

Kirchhoff 矩阵树定理（简称矩阵树定理）解决了一张图的生成树个数计数问题。

前置知识

高斯消元

在 $\mathcal O(n^3)$ 的时间复杂度下解线性方程组。

【模板】P3389 【模板】高斯消元法

#define Fail return prints("No Solution"), 0

const int N = 107;
const ld eps = 1e-6;
int n;
ld a[N][N], b[N];

int main() {
	rd(n);
	for (int i = 1, x; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			rd(x), a[i][j] = x;
		rd(x), b[i] = x;
	}
	for (int i = 1; i <= n; i++) {
		int o = 0;
		for (int j = i; j <= n; j++)
			if (fabs(a[j][i]) > eps) { o = j; break; }
		if (!o) Fail;
		swap(a[i], a[o]), swap(b[i], b[o]);
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			ld x = a[j][i] / a[i][i];
			for (int k = i; k <= n; k++)
				a[j][k] -= x * a[i][k];
			b[j] -= x * b[i];
		}
	}
	for (int i = 1; i <= n; i++) printf("%.2Lf\n", b[i] / a[i][i]);
	return 0;
}

行列式

$n \times n$ 的矩阵 $A$ 的行列式可以理解为所有列向量所夹的几何体的有向体积，记作 $\det A$ 或 $|A|$ 。

有结论：高斯消元不改变矩阵行列式，且最终行列式等于倒三角矩阵的对角线乘积。

注意，矩阵行交换，行列式取反。

矩阵树定理

本文中，图，无论无向还是有向，都允许重边，但是不允许自环。

无向图

给定一个 $n$ 个顶点的无向图。

定义 $d_i$ 表示点 $i$ 的度数， $e(i,j)$ 表示点 $i,j$ 之间的边数。

定义度数矩阵 $D$ 为： $D_{i i}=d_i,D_{i j}=0(i \neq j)$ 定义邻接矩阵 $A$ 为： $A_{ij} = A_{ji} = e(i,j)$ 定义 Laplace 矩阵（亦称 Kirchhoff 矩阵） $L$ 为： $L = D - A$ 则该图的生成树个数为： $\det L\binom{1,2, \cdots, i-1, i+1, \cdots, n}{1,2, \cdots, i-1, i+1, \cdots, n}$ 其中 $L\binom{1,2, \cdots, i-1, i+1, \cdots, n}{1,2, \cdots, i-1, i+1, \cdots, n}$ 表示 $L$ 的第 $1,2, \cdots, i-1, i+1, \cdots, n$ 行与第 $1,2, \cdots, i-1, i+1, \cdots, n$ 列构成的子矩阵。

也就是说，无向图的 Laplace 矩阵的所有 $n-1$ 阶主子式都相等。

【模板】SP104 HIGH - Highways

const int N = 13;
const ld eps = 1e-12;
int n, m;
ld a[N][N];

inline int dcmp(ld x) {
	return (x <= eps && x >= -eps) ? 0 : (x < 0 ? -1 : 1);
}

void Gauss() {
	--n;
	for (int i = 1; i <= n; i++) {
		int o = i;
		for (int j = i + 1; j <= n; j++)
			if (dcmp(a[o][i] - a[j][i]) < 0)
				o = j;
		if (o != i) swap(a[i], a[o]);
		if (!dcmp(a[i][i])) return print(0);
		for (int j = i + 1; j <= n; j++) {
			ld t = a[j][i] / a[i][i];
			for (int k = i; k <= n + 1; k++) a[j][k] -= t * a[i][k];
		}
	}
	ld ans = 1;
	for (int i = 1; i <= n; i++) ans = ans * a[i][i];
	print((ll)(ans + 0.5L));
}

int main() {
	int T;
	rd(T);
	while (T--) {
		memset(a, 0, sizeof(a));
		rd(n), rd(m);
		for (int i = 1, x, y; i <= m; i++)
			rd(x), rd(y), ++a[x][x], ++a[y][y], --a[x][y], --a[y][x];
		Gauss();
	}
	return 0;
}

【例题】P4111 [HEOI2015]小 Z 的房间

裸题。

需要注意的是，在模非质数意义下高斯消元需要辗转相除法。

const int N = 9, P = 1e9;
const int dx[] = {0, 1};
const int dy[] = {1, 0};
int n, m, a[N][N], t, b[N*N][N*N];
char s[N][N];

int main() {
	cin >> n >> m; 
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		for (int j = 0; j < m; j++)
			a[i][j] = s[i][j] == '.' ? t++ : -1;
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (~a[i][j])
				for (int k = 0; k < 2; k++) {
					int x = i + dx[k], y = j + dy[k];
					if (x >= n || y >= m || !~a[x][y]) continue;
					++b[a[i][j]][a[i][j]], ++b[a[x][y]][a[x][y]],
					--b[a[i][j]][a[x][y]], --b[a[x][y]][a[i][j]];
				}
	ll ans = 1;
	for (int i = 1; i < t; i++) {
		for (int j = i + 1; j < t; j++)
			while (b[j][i]) {
				ll d = b[i][i] / b[j][i];
				for (int k = i; k < t; k++)
					b[i][k] = (b[i][k] - d * b[j][k] % P + P) % P;
				swap(b[i], b[j]), ans = -ans;
			}
		ans = (ans * b[i][i] % P + P) % P;
	}
	cout << ans << endl;
	return 0;
}

无向图生成树边权和

将每条边的贡献写成一个一次函数 $wx+1$ ，其中 $w$ 为边权，则无向图生成树边权和就是行列式中的一次项系数。

有向图

有向图的生成树分为根向树形图和叶向树形图两种。

类似无向图的方式定义出度矩阵 $D^{out}$ 、入度矩阵 $D^{in}$ 、邻接矩阵 $A$ 。

同理，出度 Laplace 矩阵 $L^{out} = D^{out} - A$ ，入度 Laplace 矩阵 $L^{in} = D^{in} - A$ 。

则该图以 $k$ 为根的根向树形图个数为： $\det L^{out}\binom{1,2, \cdots, k-1, k+1, \cdots, n}{1,2, \cdots, k-1, k+1, \cdots, n}$ 以 $k$ 为根的叶向树形图个数为： $\det L^{in}\binom{1,2, \cdots, k-1, k+1, \cdots, n}{1,2, \cdots, k-1, k+1, \cdots, n}$ 如果要统计所有的根/叶向树形图个数，枚举所有的根 $k$ 求和即可。

BEST 定理

给定一张 $n$ 个节点的有向欧拉图。

则有：

$d_i = d^{in}_i = d^{out}_i$ 。
设 $c_k$ 表示以 $k$ 为根的根向树形图个数，对于任意 $i,j$ 有 $c_i = c_j$ 。
该图的欧拉回路个数为：

$c_k \prod_{i=1}^n (d_i-1)!$

【例题】P5807 Which Dreamed It

裸题。

需要注意的是，本题给定了起点 $1$ ，因此答案还需要乘上 $d^{out}_1$ 。

参考资料

OI Wiki 高斯消元
OI Wiki 矩阵树定理