Day 026-Q5 — ランダム行列・フィンガープリンティング（Schwartz-Zippel補題応用）

2026-05-09 赤色 Master / Phase 8+ ★★★★★★★★★ ランダム行列・Edmonds 行列

問題

$N$ 頂点 $M$ 辺の 二部グラフ $G = (L \cup R, E)$（$|L| = |R| = N$）が与えられる。

クエリ: 辺 $(u, v) \in L \times R$ を削除したとき、最大マッチングのサイズは変化するか？すなわち、辺 $(u, v)$ が最大マッチングに 必須 かどうかを判定せよ。

背景理論: Edmonds 行列

二部グラフの Edmonds 行列: $T_{ij} = x_{ij}$ if $(i,j) \in E$, else $0$。ここで $x_{ij}$ は独立なランダム変数。$\text{rank}(T) = $ 最大マッチングサイズ。辺 $(u,v)$ が必須 $\iff$ $T^{-1}_{vu} \cdot T_{uv} \ne 0$。

入力形式

N M
u_1 v_1
...
u_M v_M
Q
a_1 b_1
...
a_Q b_Q

制約

$2 \le N \le 500$
$1 \le M \le N^2$
$1 \le Q \le M$
クエリ $(a_i, b_i)$ はすべて $E$ の辺

入出力例

入力例 1

3 4
1 1
1 2
2 2
3 3
3
1 1
1 2
3 3

出力例 1

Yes
No
Yes

最大マッチング=3。辺(1,1)外すと最大2→必須。辺(1,2)外しても3→不要。辺(3,3)は3の唯一の辺→必須。

ヒント (段階的開示)

ヒント1: 方向性
Schwartz-Zippel 補題: 多項式がランダム点で 0 ならほぼ恒等的に 0。Edmonds 行列を有限体 $\mathbb{F}_p$ 上でランダム評価し、その行列式（rank）から最大マッチングを判定。辺 $(u,v)$ が必須 $\iff$ $T^{-1}[v][u] \times T[u][v] \ne 0 \pmod{p}$。
ヒント2: アプローチ
  1. Edmonds 行列 $T$ を $\mathbb{F}_p$ 上でランダム評価（各辺に乱数代入）
  2. $T$ の逆行列 $T^{-1}$ を $\mathbb{F}_p$ 上でガウス消去法により計算 $O(N^3)$
  3. 各クエリ $(u,v)$: T_inv[v-1][u-1] * T[u-1][v-1] % p != 0 なら必須
ヒント3: 誘導 
MOD = (1 << 61) - 1  # Mersenne 素数

def mat_inv_mod(M, p):
    n = len(M)
    aug = [M[i][:] + [int(i==j) for j in range(n)] for i in range(n)]
    for col in range(n):
        pivot = -1
        for row in range(col, n):
            if aug[row][col] % p != 0:
                pivot = row; break
        if pivot == -1:
            return None  # 特異行列
        aug[col], aug[pivot] = aug[pivot], aug[col]
        inv = pow(aug[col][col], p-2, p)
        # ...

模範解答 (Python)

import sys
import random
input = sys.stdin.readline

def solve():
    MOD = (1 << 61) - 1  # Mersenne 素数

    N, M = map(int, input().split())
    edges = []
    adj = [[0] * N for _ in range(N)]

    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        r = random.randint(1, MOD - 1)
        adj[u][v] = r
        edges.append((u, v, r))

    T = adj

    def mat_inv_mod(mat, p):
        n = len(mat)
        aug = [mat[i][:] + ([1 if i==j else 0 for j in range(n)]) for i in range(n)]
        for col in range(n):
            pivot = -1
            for row in range(col, n):
                if aug[row][col] % p != 0:
                    pivot = row
                    break
            if pivot == -1:
                return None
            aug[col], aug[pivot] = aug[pivot], aug[col]
            inv = pow(int(aug[col][col]) % p, p - 2, p)
            aug[col] = [int(x) * inv % p for x in aug[col]]
            for row in range(n):
                if row == col:
                    continue
                factor = int(aug[row][col]) % p
                if factor == 0:
                    continue
                aug[row] = [(int(aug[row][k]) - factor * int(aug[col][k])) % p
                            for k in range(2 * n)]
        return [[aug[i][n + j] for j in range(n)] for i in range(n)]

    T_inv = mat_inv_mod(T, MOD)

    Q = int(input())
    out = []
    for _ in range(Q):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        if T_inv is None:
            out.append("No")
        else:
            val = T_inv[v][u] * T[u][v] % MOD
            out.append("Yes" if val != 0 else "No")

    print('\n'.join(out))

solve()

Step-by-Step 解説

1Schwartz-Zippel 補題
多変数多項式 $f \not\equiv 0$ を有限体 $\mathbb{F}_p$ の部分集合 $S$ からランダム評価したとき、$\Pr[f(r_1, \ldots, r_m) = 0] \le d / |S|$。Edmonds 行列の行列式は次数 $N$ の多項式 → 誤判定確率 $\le N/p$。
2Edmonds 行列と最大マッチング
Edmonds (1967): 二部グラフの最大マッチングサイズ = $\text{rank}(T)$。$T^{-1}$ が存在 $\iff$ $\det(T) \ne 0 \iff$ 完全マッチングが存在。
3辺の必須性判定
Sherman-Morrison の公式: $\det(T') = \det(T)(1 - T_{uv} T^{-1}[v][u])$。$\det(T') = 0 \iff T_{uv} T^{-1}[v][u] = 1 \iff$ 辺が必須。
4誤判定の抑制
$p = 2^{61} - 1$（Mersenne 素数）を使用し誤判定確率を $N / p < 10^{-15}$ 程度に抑える。

よくあるミス

ミス原因正しい書き方
特異行列の処理最大マッチングが完全でない場合に逆行列が存在しないmat_inv_mod が None を返す場合の処理
行列積の mod 忘れ大きな中間値でオーバーフロー各演算ごとに % MOD
必須性条件の向きT_inv[u][v] と T_inv[v][u] の混乱$T^{-1}[v][u] \times T[u][v]$
乱数衝突同じシードで複数テストrandom.seed() で毎回異なるシード

次のステップ

  • 発展問題: 重み付き二部マッチング（Hungarian法 $O(N^3)$）と Edmonds 行列フィンガープリンティングを組み合わせ、最小重みの必須辺集合（最小辺カバー）を求める

自己評価

自分の回答

気づき・メモ