前言

本文将介绍 Matrix-Tree 定理的证明及一些应用。

Matrix-Tree 定理

内容

对于一张无向带权图,每条边带有交换环 $(R,+,\cdotp)$ 上的边权,记 $\mathcal T$ 是其所有生成树构成的集合,我们有:

(注:你可以将交换环理解为一个定义了加法和乘法运算,并且满足交换律、结合律、分配律以及存在单位元,对任意元素都存在加法逆元,且对这两种运算都封闭的集合)

定义其 Kirchhoff 矩阵为:

$$ K_{i,j} = \left\{\begin{aligned}& \sum_{k\neq i} w(i,k) &,i=j\\& -w(i,j) &,i\neq j\end{aligned}\right. $$

记 $M$ 表示 $K$ 删去任意相同编号的行列后的矩阵,则:

$$ \sum_{t\in\mathcal T} \prod_{(u,v)\in t} w(u,v) = |M| $$

(即,定义一个生成树的权值是其上所有边权的乘积,求所有生成树的权值和)

其中 $|A|$ 表示 $A$ 的行列式。

证明

先记住行列式的定义:

$$ |A| = \sum_{p} (-1)^{\tau(p)} \prod_{i} A_{i,p_i} $$

我们先建出不带符号的 Kirchhoff 矩阵。

我们考虑任选一个点做根,并在接下来的处理中把它忽略(只忽略这个点,而不忽略与它相连的边).

接下来,我们对每个点任取一条出边,统计它的权值(也就是定理中 $M$ 主对角线上的元素之积,可以通过展开乘积的式子发现为任取一条出边的方案数)。

容易发现,这样我们会连出来恰好一棵树,可能会连出来若干基环树。

于是我们考虑对环的个数进行容斥:

  • 我们枚举所有环,然后剩下的边随便连,计算这种情况的方案数,并减去它。
  • 我们枚举所有不交的两个环,然后剩下的边随便连,计算这种情况的方案数,并加上它。
  • ...

我们又注意到一个排列(置换)可以被表示成若干轮换的形式,所以实际上我们相当于枚举排列。

  • 可以发现,这个排列对应的权值和为 $\prod M_{i,p_{i}}$,任取的部分同样可以通过展开式子得到。(此处 $|x|$ 是绝对值的意思)
  • 那么容斥系数是什么呢?注意到我们枚举的排列中 $p_i = i$ 表示“随便连”,而不是自环,假如我们统计了排列的轮换个数的话,我们应该给他们($M_{i,i}$)带上容斥系数 $-1$,以消去这部分的容斥系数。

记 $C(p)$ 表示排列 $p$ 形成轮换的个数

$$ \sum(-1)^{C(p)} \prod M_{i,p_i} $$

慢着,虽然我们以及能感觉到上面的式子和行列式的定义很像,但上面说的是“统计排列的轮换个数”的奇偶性,但是行列式式子中却统计了“逆序对个数”的奇偶性,那么这两个值有什么关系呢?

引理 1:交换排列中的任意两个数,逆序对个数的奇偶性改变。

证明:首先我们显然可以知道交换排列中的相邻两个数,逆序对个数的奇偶性改变,然后我们考虑排列中的两个位置 $p_j,p_k$:

$$ p_j,p_{j+1},\cdots,p_{k-1}p_k $$

先不断把 $p_k$ 向前交换到 $p_j$ 原先的位置,记交换了恰好 $x$ 次:

$$ p_k,p_j,p_{j+1},\cdots,p_{k-1} $$

然后再把 $p_j$ 不断向右交换,则交换了恰好 $x-1$ 次:

$$ p_k,p_{j+1},\cdots,p_{k-1},p_j $$

我们发现,我们总共交换了恰好 $2x - 1$ 次,即奇偶性改变了 $2x - 1$ 次,显然这是奇数,所以逆序对个数的奇偶性必然改变。

引理 2:对于排列 $p$,$\tau(p)$ 的奇偶性和排列长度减去轮换的个数的奇偶性相等。

证明:考虑对于每个轮换我们都可以交换环长 $-~1$ 次将其上的元素排序,所以总共我们可以通过交换 $\sum$ 环长 $-~1$ 次得到排列 $1,2,\cdots,n$,显然该值等于 $n - C(p)$。注意到我们每次交换两者奇偶性都同时改变,最后排列变为 $1,2,\cdots,n$ 时两者奇偶性相同,故刚开始时两者奇偶性也相同。

这样已经很清楚了,唯一的问题是多了一个 $(-1)^n$,我们只需要把上面 $M$ 的所有系数取相反数就可以把这个系数消去了,同时我们也就得到了行列式的形式。

至此,Matrix-Tree 定理得证。

应用

生成树计数

题目:计算一张 $n(n\le 300)$ 个点的无向图的生成树的个数。

我们只需要令 $u,v$ 之间的权值为它们之间的边数,然后套用 Matrix-Tree 定理,高斯消元求行列式即可,时间复杂度为 $\mathcal O(n^3)$.

生成树权值和

题目:计算一张 $n(n\le 300)$ 个点的无向图的生成树的所有生成树的权值和,其中权值定义为生成树每条边边权之和。

若原来 $u,v$ 之间的边权为 $w$,令它们之间新的边权为一个一次的多项式 $wx+1$,然后我们可以发现两个边权乘积的一次项恰为边权值和,在 $\bmod~x^2$ 意义下定义乘法,套用 Matrix-Tree 定理即可,时间复杂度仍为 $\mathcal O(n^3)$.

有向图树形图计数

题目:计算一张 $n(n\le 300)$ 个点的有向图的以 $1$ 为根的外向树形图个数。

假如我们要求某个有向图以某个点为根的外向 / 内向树形图个数,类比无向图,我们变为了枚举入边 / 出边,并且主对角线上的权值就变为了入度 / 出度,在无向图上的 Matrix-Tree 定理的证明的基础上,我们可以很容易的构造矩阵。

代码

洛谷上的板子题:

const int kN = 3e2 + 5, kMod = 1e9 + 7;

int n, m, typ, mat[kN][kN];

int Det() {
    int ret = 1, si = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = i + 1; j <= n; ++j)
            while(mat[j][i]) {
                int t = mat[i][i] / mat[j][i];
                for(int k = i; k <= n; ++k) {
                    mat[i][k] = (mat[i][k] - 1LL * t * mat[j][k]) % kMod;
                    std::swap(mat[i][k], mat[j][k]);
                }
                si *= -1;
            }
        ret = 1LL * ret * mat[i][i] % kMod;
    }
    return (ret * si % kMod + kMod) % kMod;
}

int main() { 
    rd(n, m, typ); --n;
    for(int i = 1; i <= m; ++i) {
        int u, v, w; rd(u, v, w);
        --u; --v;
        if(!typ) {
            mat[u][u] = (mat[u][u] + w) % kMod;
            mat[v][v] = (mat[v][v] + w) % kMod;
            mat[u][v] = (mat[u][v] - w) % kMod;
            mat[v][u] = (mat[v][u] - w) % kMod;
        } else {
            mat[v][v] = (mat[v][v] + w) % kMod;
            mat[v][u] = (mat[v][u] - w) % kMod;
        }
    }
    printf("%d\n", Det());
}
最后修改:2021 年 02 月 01 日 10 : 32 AM