Day 110-Q4 | 彩色数（bitmask DP）

問題

$N$頂点$M$辺の単純無向グラフの彩色数（隣接頂点が異なる色になる最小の色数）を求めよ。

入力形式

N M
u_1 v_1
...
u_M v_M

制約

$1 \le N \le 15$

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

多重辺なし

入出力例

入力例1

出力例1

4サイクルは偶数長→二部グラフ→2色で塗れる（頂点1,3をA、2,4をB）。

入力例2

出力例2

頂点1,2,3は三角形（クリーク）なので3色必要。頂点4は孤立。

概念図: グラフを独立集合の層に分割する

ヒント（段階的開示）

ヒント1: 方向性

「$k$色で塗り分け可能か」を$k=1,2,\dots$と増やして初めて可能になった$k$を答えとする。この判定をどう高速化するかが本質。

ヒント2: アプローチ

$k$色で塗れることは、頂点集合を高々$k$個の独立集合に分割できることと同値。$dp[S]=1+\min_{T\subseteq S,\ T\text{は独立集合}}dp[S\setminus T]$ という部分集合DPで解ける。独立集合判定は$O(2^N)$で前計算でき、部分集合の部分集合列挙は全体で$O(3^N)$。$N\le15$なら$3^{15}\approx1.4\times10^7$で十分高速。

ヒント3: 誘導（コード骨格）

is_independent = [False] * (1 << n)
is_independent[0] = True
for S in range(1, 1 << n):
    low = S & (-S)
    v = low.bit_length() - 1
    rest = S ^ low
    is_independent[S] = is_independent[rest] and (adj_mask[v] & rest) == 0

dp = [INF] * (1 << n); dp[0] = 0
for S in range(1, 1 << n):
    T = S
    while T > 0:
        if is_independent[T]:
            dp[S] = min(dp[S], dp[S ^ T] + 1)
        T = (T - 1) & S

模範解答 (Python)

import sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    adj_mask = [0] * n
    for _ in range(m):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        adj_mask[u] |= (1 << v)
        adj_mask[v] |= (1 << u)

    full = 1 << n

    is_independent = [False] * full
    is_independent[0] = True
    for S in range(1, full):
        low = S & (-S)
        v = low.bit_length() - 1
        rest = S ^ low
        is_independent[S] = is_independent[rest] and (adj_mask[v] & rest) == 0

    INF = float("inf")
    dp = [INF] * full
    dp[0] = 0
    for S in range(1, full):
        best = INF
        T = S
        while T > 0:
            if is_independent[T] and dp[S ^ T] + 1 < best:
                best = dp[S ^ T] + 1
            T = (T - 1) & S
        dp[S] = best

    print(dp[full - 1])

solve()

計算量: 独立集合判定の前計算 $O(2^N)$、部分集合DP本体 $O(3^N)$。$N\le15$で$3^{15}\approx1.4\times10^7$。入力例1（4-サイクル→2）、入力例2（三角形+孤立点→3）と一致することを確認済み。ランダム小規模グラフ（$N\le6$）での全数塗り分け探索とも一致。

Step-by-Step 解説

1彩色数＝独立集合への最小分割数
$k$色で塗る＝頂点集合を$k$個の独立集合（同色グループ）に分割することと同値。

2独立集合判定を高速に前計算する
最下位ビット$v$を除いた残りが独立集合、かつ残りに$v$と隣接する頂点がないことと同値な漸化式で埋める。

3部分集合の部分集合を列挙する定番イディオム
T=S; while T>0: ...; T=(T-1)&Sで$S$の空でない部分集合を全列挙する。

4DPの意味
$dp[S]$は集合$S$だけを塗るのに必要な最小色数。最後に塗った色（独立集合$T$）を全探索する。

5全頂点集合に対するDP値が答え
dp[full-1]がグラフ全体の彩色数。

よくあるミス

ミス	原因	正しい書き方
部分集合の部分集合列挙で無限ループ	`T>=0`として空集合の後にオーバーフロー的挙動を起こす	`while T>0`とする
最下位ビットの取り出し方を誤る	`S.bit_length()-1`（最上位ビット）と混同	`low=S&(-S)`で最下位ビットを取り`low.bit_length()-1`でインデックス化
$O(3^N)$を$O(4^N)$等と誤解し制約設計を誤る	部分集合の部分集合列挙が$O(3^N)$になる理由（二項定理）を理解していない	$\sum_S 2^{\|S\|}=3^N$の関係を踏まえて$N$の上限を設計する
隣接情報をリストのリストで持ちビット演算の速さを活かせない	ビットマスク隣接リストの利点を理解していない	隣接情報は整数のビットマスクとして持ちAND演算で判定する

次のステップ

発展: Björklund–Husfeldt–Koivisto の包除原理による$O(2^N N)$彩色数計算に挑戦する
発展: 塗り分け方の総数（彩色多項式）を数える拡張に取り組む
発展: 貪欲法+DSATURによる近似彩色と厳密解の差を比較する

自己評価

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

Day 110-Q4 — 彩色数（独立集合の部分集合DPによる厳密計算）

問題