Day 080-Q3 — Tutte行列 + Schwartz-Zippel 補題（一般グラフ最大マッチング）

問題

$N$ 頂点 $M$ 辺の 一般グラフ $G$ が与えられる。$G$ の 最大マッチングのサイズ を求めよ。

ただし Blossom Algorithm は実装禁止とし、Tutte 行列 + Schwartz-Zippel 補題 によるランダム化アルゴリズムで求めること。

入出力例

4 4
1 2
1 3
2 4
3 4

2

6 5
1 2
2 3
3 4
4 5
5 6

3

概念図: Tutte 行列とランクの関係

ヒント

MOD = (1 << 61) - 1  # メルセンヌ素数
import random

T = [[0]*N for _ in range(N)]
for u, v in edges:
    r = random.randint(1, MOD-1)
    T[u][v] = r
    T[v][u] = MOD - r  # -r mod p

rank = gauss_rank(T, MOD)  # ガウス消去法
print(rank // 2)

模範解答

import sys
import random
input = sys.stdin.readline

MOD = (1 << 61) - 1  # 2^61 - 1（メルセンヌ素数）

def mod_inv(a, p=MOD):
    return pow(a, p-2, p)

def gauss_rank(mat, p):
    n = len(mat)
    rank = 0
    for col in range(n):
        pivot = -1
        for row in range(rank, n):
            if mat[row][col] != 0:
                pivot = row
                break
        if pivot == -1:
            continue
        mat[rank], mat[pivot] = mat[pivot], mat[rank]
        inv_p = mod_inv(mat[rank][col], p)
        for j in range(n):
            mat[rank][j] = mat[rank][j] * inv_p % p
        for row in range(n):
            if row != rank and mat[row][col] != 0:
                factor = mat[row][col]
                for j in range(n):
                    mat[row][j] = (mat[row][j] - factor * mat[rank][j]) % p
        rank += 1
    return rank

def max_matching_tutte(N, edges, trials=3):
    best = 0
    for _ in range(trials):
        T = [[0]*N for _ in range(N)]
        for u, v in edges:
            r = random.randint(1, MOD-1)
            T[u][v] = r
            T[v][u] = MOD - r
        rk = gauss_rank(T, MOD)
        best = max(best, rk)
    return best // 2

def main():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v = map(int, input().split())
        edges.append((u-1, v-1))
    print(max_matching_tutte(N, edges))

main()

Step-by-Step 解説

Step 1: Tutte 行列の定義

グラフ $G = (V, E)$ に対し、$N \times N$ 反対称行列 $T$ を構築する。各辺 $(i,j) \in E$ に独立なランダム変数 $x_{ij}$ を割り当て、$T_{ij} = x_{ij}$、$T_{ji} = -x_{ij}$。

Step 2: Schwartz-Zippel 補題の活用

多変数多項式 $\det(T)$ は、最大マッチングが存在するとき恒等的に非零。変数を有限体 $\mathbb{F}_p$ の乱数に置き換えると、$\det(T) = 0$ となる確率は高々 $N/p$。$p = 2^{61} - 1 \approx 2.3 \times 10^{18}$ を使えば誤答確率は $N/p < 10^{-15}$。

Step 3: ランクとマッチングの関係

定理（Tutte, 1947）: $\text{rank}(T) = 2 \nu(G)$ ただし $\nu(G)$ は最大マッチングサイズ。

Step 4: ガウス消去（mod p）

通常のガウス消去を $\text{mod } p$ で実行。ピボット選択 → 正規化 → 消去の順。計算量 $O(N^3)$。

Step 5: 複数試行

乱数のはずれを避けるため 3 回試行して最大ランクを取る。正しいランクは単調増加しかしないので最大値が答え。

よくあるミス

次のステップ

• 発展問題: 重み付き一般マッチング（Tutte 行列の対角積最大化）
• 関連: 完全二部グラフ判定（Edmonds 行列・rank = N）

自己評価