矩阵树定理(Matrix-tree Theorem)

矩阵树定理就是把图的生成树个数与矩阵行列式联系起来的一个定理

前置知识矩阵行列式

定义

假设有一个无向图 $G=(V,E)$ 有 $p$ 个顶点 $q$ 条边

对于 $G$ 中每一条边,我们任意指定一个方向,这样我们就可以定义 $G$ 的关联矩阵 $M(G)$, 它是一个 $p\times q$ 的矩阵

$$M_{ij}=\begin{cases}-1&v_i是e_i的起点\\1&v_i是e_i的终点\\0&otherwise\end{cases}$$

然后定义基尔霍夫矩阵 $L(G)$, 它是一个 $p\times p$ 的矩阵

$$L_{ij}=\begin{cases}-m_{ij}&i\ne j,v_i与v_j之间有m_{ij}条边\\d(v_i)&i=j\end{cases}$$

$d(i)$ 为点 $i$ 的度数,可以看出 $M$ 与指定的边的方向有关,而 $L$ 无光

几条引理

引理1

$MM^T=L$

证明

$(MM^T)_{ij}=\sum\limits_{e_k\in E}M_{ik}M^T_{kj}=\sum\limits_{e_k\in E}M_{ik}M_{jk}$

分类讨论,当 $i\ne j$ 时,当且仅当存在 $e_k\in E$ 把 $v_i,v_j$ 连起来时,$M_{ik}M_{jk}=-1$,否则 $M_{ik}M_{jk}=0$,因此结果就是 $v_i,v_j$ 之间的边数。

当 $i=j$ 时,当且仅当存在 $e_k\in E$ 的一个端点为 $v_i$ 时,$M_{ik}M_{jk}=1$,因此结果就是 $v_i$ 的度数

证毕

我们先定义一些 $M$ 的子矩阵,方便接下来的证明,定义 $M_0$ 表示 $M$ 去掉最后一行得到的 $(p-1)\times q$ 的矩阵

定义一个矩阵 $M_0[S]$,其中 $S={i_1,i_2,...,i_{p- 1}}\cap {1,2,...,q}$,表示从矩阵 $M_0$ 中选取 $p-1$ 列得到的一个方阵

引理2

令 $S$ 是边集 $E$ 的一个大小为 $p-1$ 的子集,若 $G'=(V,S)$ 构成生成树,则 $det~M_0[S]=\pm1$,否则,$det~M_0[S]=0$

证明

若 $G'$ 不构成生成树,则说明 $G'$ 中存在环 $C$.假设 $C$ 由 $e_1,e_2...e_k$,共 $k$ 条边构成,那么在矩阵 $M_0[S]$ 中一定存在某两行互为相反数,根据行列式的性质,就可以得到 $det~M_0[S]=0$

若 $G'$ 构成生成树,我们将 $G'$ 中的点按照拓扑关系排序,得到 $u_1,u_2...,u_k$ 即叶子节点总是在前面。

然后对 $M_0[S]$ 的列进行重新排序，排完序过后与 $u_1$ 只有 $e_1$,因为它是叶子节点,同理,与$u_i$ 相连的边也只可能有 $e_1,e_2...e_i$,那么排完序后的矩阵就成了一个下三角矩阵,主对角线上只为 $\pm 1$,所以 $det M_0[S]=\pm 1$

证毕

Binet-Cauchy Theorem定理

设 $A=(a_{ij})_{m\times n},B=(b_{ij})_{n\times m}$, 则有 $det AB=\sum\limits_S (det A[S])(det B[S])$,其中 $S$ 大小为 $m$,且 $S\subseteq \{1,2,...,n\}$。$A[S]$ 的记号与上面类似,是取 $A$ 中任意 $m$ 列得到的 $m\times m$ 的方阵

证明放这了

矩阵树定理

设图 $G=(V,E)$,拉普拉斯矩阵 $L$。则 $G$ 的生成树个数等于 $det L_0$,$L_0$ 是去掉第 $i$ 行第 $i$ 列得到的子矩阵( $i$ 任意)

证明

不妨设去掉最后一行最后一列。

由引理1,得到 $M_0M_0^T=L_0$

由Binet-Cauchy Theorem定理

得 $det L_0= \sum\limits_S(det M_0[S])(detM_0^T[S])=\sum\limits_S(detM_0[S])^2$

由引理2得若 $S$ 构成生成树,则 $detM_0[S]=\pm1$,否则为0,因此 $detL_0$ 就为生成树个数

至此,矩阵树定理就证明完了,然后我们就可以将求生成树的数量转化为行列式求值了

例题【模板】Matrix-Tree 定理

和上面的有些不一样,这道题不仅有了方向还带了边权

对于带权无向图

只需要把 $L$ 中的度数换成边权和即可,即求所有生成树的边权乘积之和,具体证明我也不会

OI要什么证明,直接背诵

对于带权无向图

若要求的是外向树,那么加到达该点的边的权值和即可

若是内向树,就加从该点出发的边的权值和

代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int n, m, t, a[305][305];

int qmi(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = (ll)res * a % MOD;
        a = (ll)a * a % MOD;
        b >>= 1;
    }
    return res;
}

int work()
{
    int res = 1, w = 1;
    for (int i = 1; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (a[j][i] && !a[i][i])
            {
                swap(a[i], a[j]), w = -w;
                break;
            }            
        }      
        int inv = qmi(a[i][i], MOD - 2);
        for (int j = i + 1; j < n; j++)
        {
            int temp = (ll)a[j][i] * inv % MOD;
            for (int k = i; k < n; k++)
                a[j][k] = (a[j][k] - (ll)temp * a[i][k] % MOD) % MOD;
        }
    }
    for (int i = 1; i < n; i++)
        res = (ll)res * a[i][i] % MOD;
    res *= w;
    return (res % MOD + MOD) % MOD;
}

int main()
{
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        u--, v--;
        if (t == 0)
        {
            a[u][u] = (a[u][u] + w) % MOD;
            a[v][v] = (a[v][v] + w) % MOD;
            a[u][v] = (a[u][v] - w) % MOD;
            a[v][u] = (a[v][u] - w) % MOD;
        }
        else
        {
            a[v][v] = (a[v][v] + w) % MOD;
            a[u][v] = (a[u][v] - w) % MOD;
        }
    }
    int ans = work();
    printf("%d", ans);
    return 0;
}

参考矩阵树定理（Matrix-tree Theorem）笔记