Day 143-Q4 | 行列木定理

問題

$N$頂点$M$辺の単純無向連結グラフが与えられる。このグラフに含まれる全域木の総数を素数$p$で割った余りを求めよ。

行列木定理（Kirchhoffの定理）

ラプラシアン行列$L$を$L_{ii}=\deg(i)$、$L_{ij}=-(\text{辺の本数})$（$i\ne j$）と定義する。$L$から任意の1行と同じ番号の1列を取り除いた$(N-1)\times(N-1)$行列$L'$について、

$$\det(L') = G\text{ の全域木の総数}$$

が成り立つ。本問では最後の頂点（番号$N$）に対応する行と列を除いて計算する。

入力形式

N M p
u_1 v_1
:
u_M v_M

制約

$2 \le N \le 300$

$N-1 \le M \le N(N-1)/2$

連結・単純グラフ

$p$は素数、$p > N$

入出力例

入力例1

4 6 998244353
1 2
1 3
1 4
2 3
2 4
3 4

出力例1

K4の全域木数はCayleyの公式より4^(4-2)=16。

概念図：ラプラシアン行列と余因子

ヒント（段階的開示）

ヒント1（方向性）

全域木を素朴に数え上げると指数関数的な数になり全探索は不可能。しかし「全域木の総数」という組合せ的な量が行列式という線形代数の演算で厳密に求まる（Kirchhoffの定理）。行列式はO(N³)のガウスの消去法で計算できる。

ヒント2（アプローチ）

ラプラシアン行列$L$自体は特異行列（各行・各列の和が0）。任意の1行1列を削除した$(N-1)\times(N-1)$部分行列$L'$の行列式が全域木数に一致する。mod $p$上のガウスの消去法（フェルマーの小定理で逆元を求める）で計算する。

ヒント3（誘導）

def laplacian_determinant_mod(N, edges, p):
    L = [[0] * N for _ in range(N)]
    for u, v in edges:
        L[u][u] += 1
        L[v][v] += 1
        L[u][v] -= 1
        L[v][u] -= 1

    n = N - 1
    A = [[L[i][j] % p for j in range(n)] for i in range(n)]

    det = 1
    for col in range(n):
        pivot = -1
        for row in range(col, n):
            if A[row][col] % p != 0:
                pivot = row
                break
        if pivot == -1:
            return 0
        if pivot != col:
            A[col], A[pivot] = A[pivot], A[col]
            det = (-det) % p
        det = (det * A[col][col]) % p
        inv = pow(A[col][col], p - 2, p)
        for row in range(col + 1, n):
            factor = (A[row][col] * inv) % p
            if factor:
                for k in range(col, n):
                    A[row][k] = (A[row][k] - factor * A[col][k]) % p
    return det % p

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    p = int(data[idx]); idx += 1

    L = [[0] * N for _ in range(N)]
    for _ in range(M):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        L[u][u] += 1
        L[v][v] += 1
        L[u][v] -= 1
        L[v][u] -= 1

    n = N - 1
    A = [[L[i][j] % p for j in range(n)] for i in range(n)]

    det = 1
    singular = False
    for col in range(n):
        pivot = -1
        for row in range(col, n):
            if A[row][col] % p != 0:
                pivot = row
                break
        if pivot == -1:
            singular = True
            break
        if pivot != col:
            A[col], A[pivot] = A[pivot], A[col]
            det = (-det) % p
        det = (det * A[col][col]) % p
        inv = pow(A[col][col], p - 2, p)
        for row in range(col + 1, n):
            factor = (A[row][col] * inv) % p
            if factor:
                rowA, colA = A[row], A[col]
                for k in range(col, n):
                    rowA[k] = (rowA[k] - factor * colA[k]) % p

    print(0 if singular else det % p)

main()

Step-by-Step 解説

1ラプラシアン行列の構築
対角成分に次数、辺(u,v)があればL[u][v]=L[v][u]=-1。各行・各列の和が0で単独では特異行列。

21行1列を除く理由
連結グラフのラプラシアン行列のランクはN-1。任意の1行1列を除いた部分行列の行列式が全域木数に一致する（Cauchy-Binetの公式で証明）。

3mod p上のガウスの消去法
Z/pZ（p素数）は体なので0でない要素は逆元a^(p-2)（フェルマーの小定理）を持つ。逆元を掛けて引く操作でピボット行を処理する。

4検証例（K4）
完全グラフK_nの全域木数はCayleyの公式よりn^(n-2)。K4なら4²=16本、行列木定理の結果と一致する。

5計算量と限界
ガウスの消去法はO(N³)。N≤300程度なら十分高速だが、Nが数千を超えるとPythonでは厳しくC++移植が必要。

よくあるミス

ミス	原因	正しい書き方
隣接行列の行列式を計算してしまう	「グラフの行列」＝隣接行列という思い込み	対角成分に次数を入れたラプラシアン行列L=D-Aを使う
除去する行・列を変えて平均を取ろうとする	定理の主張(任意の余因子が一致)を信頼していない	どの1行1列を除いても同じ値になる(本問は最後の頂点で固定)
合成数pでもフェルマーの小定理で逆元を求める	フェルマーの小定理はp素数が前提	合成数の場合は拡張ユークリッドの互除法で逆元を求める
ピボットが0のまま逆元計算してしまう	0行が残っている＝行列が特異(グラフ非連結)を見落とす	非零行が見つからない場合は行列式0として扱う
浮動小数点数でガウスの消去法を実装する	整数演算に慣れておらずfloatを使う	法p上の整数演算(乗算+モジュラー逆元)で正確に計算する

次のステップ

発展: 有向グラフに対する「有向木数え上げ(Tutteの有向行列木定理)」を調べ、根付き有向全域木の数え上げに拡張せよ。
発展2: 辺に重みを付けて「全域木の重み総和」を求める重み付き行列木定理を実装せよ。

自己評価

完全理解おおむね理解要復習

Day 143-Q4 — 行列木定理（Matrix-Tree Theorem / Kirchhoffの定理）

問題