矩阵树定理

What · 是什么

矩阵树定理(Kirchhoff's Matrix-Tree Theorem)：无向图 G 的生成树个数等于其 Laplace 矩阵 L=D−A 的任一 n−1 阶主子式(删去第 i 行第 i 列)的行列式绝对值。其中 D 为度数矩阵(对角线上为各点度数，重边按条数计，自环忽略)，A 为邻接矩阵(A[u][v]=u 与 v 之间边数)。对带权图，若把 L 的 A 换成权重矩阵、D 换成各点关联边权和，则主子式 = 所有生成树的边权乘积之和(加权计数)。有向图也有对应版本：出度(入度)Laplace 删去第 k 行列的主子式 = 以 k 为根的根向(叶向)树形图数。

Why · 为什么

How · 实现

伪代码

function spanning_tree_count(n, edges):
  m = n-1
  L = zero matrix [m][m]
  for (u,v) in edges:
    if u==v: continue           # 自环忽略
    for x in (u,v): if x<m: L[x][x] += 1
    if u<m and v<m: L[u][v]-=1; L[v][u]-=1
  return |det(L)|   # 用裸高斯或 Bareiss 精确整数

Python 实现

def bareiss_det(a):
    """精确整数行列式 (Bareiss 消元, 无分数, O(n^3))"""
    n = len(a)
    a = [row[:] for row in a]
    if n == 0:
        return 1
    sign = 1
    prev = 1
    for k in range(n - 1):
        if a[k][k] == 0:
            for r in range(k + 1, n):
                if a[r][k] != 0:
                    a[k], a[r] = a[r], a[k]
                    sign = -sign
                    break
            else:
                return 0
        for i in range(k + 1, n):
            for j in range(k + 1, n):
                a[i][j] = (a[i][j] * a[k][k] - a[i][k] * a[k][j]) // prev
        prev = a[k][k]
        for i in range(k + 1, n):
            a[i][k] = 0
    return sign * a[n - 1][n - 1]


def det_mod(a, mod):
    """模素数 mod 的行列式 (高斯消元, 用逆元)"""
    n = len(a)
    a = [row[:] for row in a]
    res = 1
    for i in range(n):
        if a[i][i] == 0:
            for r in range(i + 1, n):
                if a[r][i] != 0:
                    a[i], a[r] = a[r], a[i]
                    res = -res
                    break
            else:
                return 0
        res = res * a[i][i] % mod
        inv = pow(a[i][i], -1, mod)
        for r in range(i + 1, n):
            if a[r][i]:
                t = a[r][i] * inv % mod
                for c in range(i, n):
                    a[r][c] = (a[r][c] - t * a[i][c]) % mod
    return res % mod


def laplace_minor(n, edges):
    """构造删去第 n-1 行/列的 Laplace 主子式"""
    m = n - 1
    L = [[0] * m for _ in range(m)]
    for u, v in edges:
        if u == v:
            continue
        for x in (u, v):
            if x < m:
                L[x][x] += 1
        if u < m and v < m:
            L[u][v] -= 1
            L[v][u] -= 1
    return L


def spanning_tree_count(n, edges):
    """矩阵树定理: 无向(多重)图生成树个数, 精确大整数"""
    if n <= 1:
        return 1
    return bareiss_det(laplace_minor(n, edges))


def spanning_tree_count_mod(n, edges, mod):
    """带模版(答案可能很大时用 1e9+7 取模)"""
    return det_mod(laplace_minor(n, edges), mod)


if __name__ == "__main__":
    assert spanning_tree_count(3, [(0, 1), (1, 2), (0, 2)]) == 3
    K4 = [(i, j) for i in range(4) for j in range(i + 1, 4)]
    assert spanning_tree_count(4, K4) == 16
    assert spanning_tree_count(2, [(0, 1), (0, 1)]) == 2  # 重边
    assert spanning_tree_count(4, [(0, 1), (1, 2), (2, 3)]) == 1
    K5 = [(i, j) for i in range(5) for j in range(i + 1, 5)]
    assert spanning_tree_count(5, K5) == 125
    print("matrix-tree OK")

易错点

• 忘记把重边条数累计进度数矩阵与邻接矩阵
• 自环误计入影响答案(应忽略，但不影响主要结论)
• 无向图删行删列位置任意，但必须删同一行同一列(n−1 阶主子式)
• 用浮点高斯消元求大整数行列式精度丢失，应取模或用 Bareiss
• 有向图误用无向公式(需用出度/入度 Laplace 区分根向/叶向树形图)

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/matrix-tree/
• CP-Algorithms✓ https://cp-algorithms.com/graph/kirchhoff-theorem.html