Day 070-Q1 | 弦グラフ・完全消去順序 + 木幅（Chordal Graph / PEO）

問題

$N$ 頂点 $M$ 辺の無向グラフ $G$ に対して以下の3つのクエリを順に処理せよ。

クエリ1: $G$ が弦グラフか判定する。弦グラフとは、長さ4以上のすべての単純サイクルに少なくとも1本の弦が存在するグラフ。
クエリ2: 弦グラフであれば完全消去順序（PEO）を出力。PEO とは頂点の順列 $v_1,\ldots,v_N$ で、各 $v_i$ の右隣接集合 $R(v_i)$ が完全グラフをなすもの。
クエリ3: 木幅 $= \max_i |R(v_i)|$ を出力。

制約

パラメータ	範囲
$N$	$1 \le N \le 2000$
$M$	$0 \le M \le N(N-1)/2$
頂点番号	$1 \le u, v \le N$（自己ループ・多重辺なし）

入出力例

入力例 1

出力例 1

YES
6 5 4 3 2 1
2

入力例 2

出力例 2

NO

入力例2は 4-サイクル（1-2-3-4-1）に弦がないため非弦グラフ。

概念図: MCS と PEO

ヒント（段階的開示）

ヒント1: 方向性

弦グラフの判定には Maximum Cardinality Search（MCS）を使う。MCS は貪欲に「既訪問頂点との隣接数が最大の頂点」を選ぶアルゴリズムで、弦グラフであれば逆順が PEO になる。

ヒント2: アプローチ

MCS でPEO候補 $v_1, \ldots, v_N$ を生成
各 $v_i$ の右隣接集合 $R(v_i)$ を計算
$R(v_i)$ 内で最も pos の小さい頂点 $w$ について、$R(v_i) \setminus \{w\}$ が $w$ の隣接集合の部分集合か確認
条件が成立すれば弦グラフ

ヒント3: コード骨格

# MCS による PEO 候補生成
cnt = [0] * (N + 1)  # 訪問済み隣接数
visited = [False] * (N + 1)
order = []
for _ in range(N):
    v = max((cnt[i], i) for i in range(1,N+1) if not visited[i])[1]
    visited[v] = True
    order.append(v)
    for u in adj[v]:
        if not visited[u]:
            cnt[u] += 1
peo = order[::-1]

# PEO 検証
pos = {v: i for i, v in enumerate(peo)}
for i, v in enumerate(peo):
    R = [u for u in adj[v] if pos[u] > i]
    if R:
        w = min(R, key=lambda u: pos[u])
        if not set(R) - {w} <= adj[w]:
            print("NO"); return

模範解答 (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 = [set() for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        adj[u].add(v)
        adj[v].add(u)

    # MCS で PEO 候補を取得 O(N^2)
    cnt = [0] * (N + 1)
    visited = [False] * (N + 1)
    order = []
    for _ in range(N):
        v = -1; best = -1
        for i in range(1, N + 1):
            if not visited[i] and cnt[i] > best:
                best = cnt[i]; v = i
        visited[v] = True
        order.append(v)
        for u in adj[v]:
            if not visited[u]:
                cnt[u] += 1
    peo = order[::-1]

    # PEO 検証
    pos = [0] * (N + 1)
    for i, v in enumerate(peo):
        pos[v] = i

    is_chordal = True
    treewidth = 0
    for i, v in enumerate(peo):
        R = [u for u in adj[v] if pos[u] > i]
        treewidth = max(treewidth, len(R))
        if R:
            w = min(R, key=lambda u: pos[u])
            if not (set(R) - {w}).issubset(adj[w]):
                is_chordal = False; break

    if not is_chordal:
        print("NO")
    else:
        print("YES")
        print(*peo)
        print(treewidth)

solve()

Step-by-Step 解説

Step 1: 弦グラフの特徴

弦グラフは以下の等価条件を持つ: 長さ4以上のサイクルに弦が存在 ⟺ 完全消去順序 (PEO) が存在 ⟺ 木幅 = 最大クリークサイズ - 1

Step 2: MCS アルゴリズム

贪欲に「訪問済み隣接頂点数が最大」の頂点を選ぶ。時間計算量 $O(N^2)$（バケットキューで $O(N+M)$ まで高速化可能）。

Step 3: PEO 検証条件

PEO 候補 $v_1,\ldots,v_N$ が真の PEO か確認: 各 $v_i$ の右隣接集合 $R(v_i)$ の最左頂点 $w$ に対し、$R(v_i) \setminus \{w\}$ が $\mathrm{adj}(w)$ の部分集合である必要がある。これが成立 ⟺ $R(v_i)$ は完全グラフ。

Step 4: 木幅の計算

弦グラフの木幅 $= \max_i |R(v_i)|$（最大クリークサイズ - 1 に等しい）。

Step 5: 計算量分析

処理	計算量
MCS（シンプル）	$O(N^2)$
PEO 検証	$O(N + M)$
木幅計算	$O(N + M)$
全体	$O(N^2)$（$N \le 2000$ で十分）

よくあるミス

ミス	原因	正しい書き方
PEO の向きを間違える	MCS の出力はそのままではなく逆順が PEO	`order.reverse()` を忘れない
$R(v_i)$ の完全グラフ検証の条件	$w$ の全隣接ではなく $R(v_i)\setminus\{w\}$ が $\text{adj}(w)$ の部分集合	`(set(R) - {w}).issubset(adj[w])`
弦グラフでない場合に続けて処理	早期リターンの欠如	`if not is_chordal: print("NO"); return`
adj を list で持ち部分集合チェックが O(M)	issubset が $O(\|R\| \cdot \|adj\|)$ になる	`adj` を `set` で持つ

次のステップ

発展問題: 弦グラフの最大重みクリーク探索（PEO 順に貪欲 DP）
k-tree からの弦グラフ生成と木分解構築
弦グラフ上のグラフ彩色（クリーク数 = 彩色数が成立）
一般グラフの木幅計算（NP困難・FPTアルゴリズム）

Day 070-Q1 — 弦グラフ・完全消去順序 + 木幅（Chordal Graph / PEO）

問題

制約