Day 021-Q4 — 弦グラフと完全消去順序（Perfect Elimination Ordering）

2026-05-04 赤色 Master / Phase 8+ ★★★★★★★★★ 弦グラフ・グラフ彩色・クリーク分解

問題

$N$ 頂点 $M$ 辺の無向グラフ $G$ が与えられる。

  1. $G$ が弦グラフ（Chordal Graph）かどうか判定せよ。
  2. 弦グラフであれば、最大クリークサイズ（クロマティック数に等しい）を求めよ。
  3. 弦グラフであれば、最小彩色数を出力せよ（弦グラフでは $\chi(G) = \omega(G)$）。

弦グラフ: 長さ 4 以上のすべての誘導閉路に弦（chord）がある（= すべての誘導閉路が三角形）グラフ。

入力形式

N M
u_1 v_1
...
u_M v_M

制約

$2 \leq N \leq 10^5$
$1 \leq M \leq 3 \times 10^5$
自己ループ・多重辺なし

入出力例

入力例 1

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

出力例 1

Yes
3
3

入力例 2

4 4
1 2
2 3
3 4
4 1

出力例 2

No

ヒント (段階的開示)

ヒント1: 方向性
弦グラフの判定には Perfect Elimination Ordering (PEO) を使う。PEO とは、頂点の順序 $v_1, v_2, \ldots, v_n$ で、各 $v_i$ が残りのグラフ（$v_i, v_{i+1}, \ldots, v_n$）において単純化頂点（simplicial vertex）になっているもの。
ヒント2: アプローチ
PEO は Maximum Cardinality Search (MCS) で $O((N+M) \log N)$ で求められる。MCS: (1) 任意の頂点から開始、(2) 毎回「隣接済み頂点数が最大の未処理頂点」を選択、(3) これで得た逆順が PEO 候補。
ヒント3: 誘導 
import heapq
from collections import defaultdict

def mcs(adj, n):
    weight = [0] * (n+1)
    visited = [False] * (n+1)
    order = []
    heap = [(-0, v) for v in range(1, n+1)]
    heapq.heapify(heap)

    while heap:
        neg_w, v = heapq.heappop(heap)
        if visited[v]: continue
        visited[v] = True
        order.append(v)
        for u in adj[v]:
            if not visited[u]:
                weight[u] += 1
                heapq.heappush(heap, (-weight[u], u))

    return order[::-1]  # PEO 候補（逆順）

模範解答 (Python)

import sys
from collections import defaultdict
import heapq

def solve():
    data = sys.stdin.read().split()
    pos = 0
    N = int(data[pos]); pos += 1
    M = int(data[pos]); pos += 1

    adj = defaultdict(set)
    for _ in range(M):
        u = int(data[pos]); pos += 1
        v = int(data[pos]); pos += 1
        adj[u].add(v)
        adj[v].add(u)

    def mcs():
        weight = defaultdict(int)
        visited = set()
        order = []
        heap = [(0, v) for v in range(1, N+1)]
        heapq.heapify(heap)

        while heap:
            neg_w, v = heapq.heappop(heap)
            if v in visited:
                continue
            visited.add(v)
            order.append(v)
            for u in adj[v]:
                if u not in visited:
                    weight[u] += 1
                    heapq.heappush(heap, (-weight[u], u))

        return order[::-1]

    peo = mcs()

    pos_in_order = {v: i for i, v in enumerate(peo)}

    is_chordal = True
    max_clique = 1

    for i, v in enumerate(peo):
        later_neighbors = [u for u in adj[v] if pos_in_order[u] > i]
        if not later_neighbors:
            continue

        earliest = min(later_neighbors, key=lambda u: pos_in_order[u])

        earliest_later = set(u for u in adj[earliest] if pos_in_order[u] > pos_in_order[earliest])

        for u in later_neighbors:
            if u == earliest:
                continue
            if u not in adj[earliest]:
                is_chordal = False
                break

        if not is_chordal:
            break

        clique_size = 1 + len(later_neighbors)
        max_clique = max(max_clique, clique_size)

    if not is_chordal:
        print("No")
        return

    print("Yes")
    print(max_clique)
    # 弦グラフ: χ(G) = ω(G)
    print(max_clique)

solve()

Step-by-Step 解説

1弦グラフの特徴づけ
弦グラフは以下と同値（Rose, Tarjan, Lueker 1976）: PEO（完全消去順序）が存在する。ある頂点順序 $v_1, \ldots, v_n$ で各 $v_i$ が $G[\{v_i, \ldots, v_n\}]$ の simplicial vertex。Simplicial vertex: 近傍がクリークを形成する頂点。
2MCS アルゴリズム
各ステップで「すでに選ばれた頂点との隣接数が最大」の頂点を選ぶ。逆順が PEO 候補。計算量 $O((N+M) \log N)$。
3PEO の検証
MCS が出力した順序が本当に PEO かを確認: $v_i$ の後続隣接頂点の最前者 $w$ の後続隣接頂点が $v_i$ の後続隣接頂点を包含するか。
4最大クリークと彩色数
弦グラフでは $\omega(G) = \chi(G)$（完全グラフ多面体定理）。MCS の過程で各ステップのクリークサイズの最大値が $\omega(G)$。

よくあるミス

ミス原因正しい書き方
MCS の逆順をPEO候補とするのを忘れる順番通りだと逆order[::-1]
クリークサイズを後続隣接のみで計算v 自身を含め忘れ1 + len(later_neighbors)
非弦グラフでχ=ωと出力定理の適用条件を忘れ弦グラフ判定後のみ適用

次のステップ

  • 発展問題: ツリー幅（Treewidth）の計算（弦グラフと密接な関係）
  • 応用: 弦グラフ上の最大独立集合（Greedy PEO 逆順）

自己評価

自分の回答

気づき・メモ