矩阵树定理 学习笔记

作者: xht37 分类: 笔记 发布时间: 2019-12-13 16:29

点击数:352

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$ 个节点的有向欧拉图

则有:

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

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

【例题】P5807 Which Dreamed It

裸题。

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

参考资料

发表评论

电子邮件地址不会被公开。 必填项已用*标注