Day 052-Q4 — グラフの彩色多項式（Deletion-Contraction + 包除原理）

2026-06-05 赤色 Master / Phase 8+ ★★★★★★★★★ 彩色多項式 / Deletion-Contraction / 包除原理 / Union-Find

問題

$N$ 頂点 $M$ 辺の無向グラフ $G$ の彩色多項式 $P(G, k)$ を求めよ。

$$P(G, k) = \sum_{i=0}^{N} c_i \cdot k^i$$

各係数 $c_i$（$i = 0, 1, \ldots, N$ の順）を出力せよ。

制約

パラメータ範囲
$N$$1 \le N \le 15$
$M$$0 \le M \le N(N-1)/2$
グラフ無向・単純グラフ
時間制限2秒

入出力例

入力例 1 (4頂点サイクル C₄)

4 4
1 2
2 3
3 4
4 1

出力例 1

0 -3 6 -4 1

$C_4$ の彩色多項式: $P = k^4 - 4k^3 + 6k^2 - 3k = k(k-1)(k^2-3k+3)$。係数: $c_0=0, c_1=-3, c_2=6, c_3=-4, c_4=1$。

入力例 2 (辺なし K̄₃)

3 0

出力例 2

0 0 0 1

辺なし3頂点グラフ: $P = k^3$。係数: $c_0=c_1=c_2=0, c_3=1$。

概念図: 包除原理による彩色多項式計算

包除原理: P(G,k) = Σ_{S⊆E} (-1)^|S| · k^{c(S)} 例: K₃（三角形） 1 2 3 辺部分集合 S |S| c(S) (-1)^|S|·k^{c(S)} ∅03+k³ {(1,2)}12-k² {(1,3)}12-k² {(2,3)}12-k² {(1,2),(1,3)}21+k {(1,2),(2,3)}21+k {(1,3),(2,3)}21+k {(1,2),(1,3),(2,3)}31-k 合計: k³ - 3k² + 3k - k = k³ - 3k² + 2k P(K₃, k) = k(k-1)(k-2) ← 3色以上で完全3色塗り分け可 c₀=0, c₁=2, c₂=-3, c₃=1 （k¹の係数は Union-Find で c(S)=1 のとき±1を集計）

ヒント（段階的開示）

ヒント1: 方向性
Deletion-Contraction: $P(G, k) = P(G - e, k) - P(G / e, k)$。 辺 $e$ を「削除」した場合と「収縮（両端をマージ）」した場合の差。 $N \le 15$ なら包除原理アプローチが実装しやすい。
ヒント2: アプローチ（包除原理）
$$P(G, k) = \sum_{S \subseteq E} (-1)^{|S|} k^{c(S)}$$ ここで $c(S)$ = 辺集合 $S$ が張る連結成分数（全 $N$ 頂点を含む）。
  • 全部分集合 $S$ を列挙（$2^M$ 通り）
  • 各 $S$ に対して Union-Find で $c(S)$ を計算
  • $\text{coeffs}[c(S)]$ に $(-1)^{|S|}$ を加算
ヒント3: コード骨格 
coeffs = [0] * (N + 1)

def find(par, x):
    while par[x] != x: par[x] = par[par[x]]; x = par[x]
    return x

for mask in range(1 << M):
    par = list(range(N + 1))
    cnt = bin(mask).count('1')
    for i in range(M):
        if (mask >> i) & 1:
            u, v = edges[i]
            pu, pv = find(par, u), find(par, v)
            if pu != pv: par[pu] = pv
    c = sum(1 for v in range(1, N+1) if find(par, v) == v)
    sign = 1 if cnt % 2 == 0 else -1
    coeffs[c] += sign

print(' '.join(map(str, coeffs)))

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v = map(int, input().split())
        edges.append((u, v))

    # 包除原理: P(G,k) = Σ_{S⊆E} (-1)^|S| * k^{c(S)}
    # c(S) = S の辺で結ばれた N 頂点の連結成分数
    coeffs = [0] * (N + 1)

    def find(par, x):
        while par[x] != x:
            par[x] = par[par[x]]
            x = par[x]
        return x

    for mask in range(1 << M):
        par = list(range(N + 1))
        cnt = 0
        for i in range(M):
            if (mask >> i) & 1:
                u, v = edges[i]
                pu, pv = find(par, u), find(par, v)
                if pu != pv:
                    par[pu] = pv
                cnt += 1

        # 連結成分数（全 N 頂点を考慮）
        c = sum(1 for v in range(1, N + 1) if find(par, v) == v)
        sign = 1 if cnt % 2 == 0 else -1
        coeffs[c] += sign

    print(' '.join(map(str, coeffs)))

solve()

Step-by-Step 解説

1彩色多項式の定義
$P(G, k)$ = $k$ 色を使って隣接頂点が異なる色になるように塗る方法数。これは $k$ の多項式。 $P(G, 0) = 0$、$P(K_n, k) = k(k-1)(k-2)\cdots(k-n+1)$。
2包除原理の適用
「辺集合 $S$ の全辺の両端が同色」の方法数 = $k^{c(S)}$（$c(S)$ は Union-Find で求める連結成分数）。 符号付き和：$P(G,k) = \sum_{S \subseteq E} (-1)^{|S|} k^{c(S)}$。
3多項式の係数抽出
各 mask について $c(S)$ を求め、$(-1)^{|S|}$ を $\text{coeffs}[c(S)]$ に加算。 最終的に $\text{coeffs}[i]$ が $k^i$ の係数。
4Deletion-Contraction の関係
$P(G-e, k) = P(G, k) + P(G/e, k)$（包除原理の特殊ケース）。 収縮 $G/e$ は両端をマージした $N-1$ 頂点グラフ。

計算量

全部分集合の列挙: $O(2^M)$
各 mask での Union-Find: $O(M \alpha(N))$
連結成分数の計算: $O(N)$
全体: $O(2^M \cdot (M + N))$
注意: $N=15$ では $M \le 105$, $2^{105}$ は計算不可。実用は $M \le 25$ 程度まで

よくあるミス

ミス原因正しい書き方
連結成分数の誤り辺の端点のみを数えるrange(1, N+1) 全頂点を確認
cnt の計算Union した回数ではなく辺選択数を数えるcnt は popcount(mask)
係数の出力順$k^N$ から $k^0$ の順にしてしまうcoeffs[0] から coeffs[N] の順
par の初期化忘れ各 mask で par を使い回すpar = list(range(N+1)) を mask ごとに

次のステップ

  • 発展問題: Deletion-Contraction の再帰実装 + メモ化（$M > 25$ 対応）
  • 関連: Tutte 多項式 $T(G; x, y)$（彩色多項式の一般化。$T(G; 1+k, 1) = P(G, k)/k^{c(G)}$）
  • 応用: 信頼性多項式 $R(G, p)$（各辺が確率 $p$ で生き残るときの連結確率）

自己評価