Day 098-Q5 | Erdős–Gallaiの定理（次数列のgraphical判定）

問題

$N$ 個の非負整数からなる数列 $d_1,\dots,d_N$ が与えられる。この数列を次数列として持つ単純無向グラフ（多重辺・自己ループなし）が存在するか判定せよ。存在すれば Yes、しなければ No を出力せよ。

Erdős–Gallaiの定理を用いること。降順に並べた $d_1\ge d_2\ge\dots\ge d_N\ge0$ がgraphicalであるための必要十分条件:

$\sum_{i=1}^{N} d_i$ が偶数
すべての $k=1,\dots,N$ について $\displaystyle\sum_{i=1}^{k} d_i \le k(k-1) + \sum_{i=k+1}^{N}\min(d_i,k)$

Havel-Hakimi法（構成的手法）と異なり、Erdős–Gallaiの定理は不等式を直接検証するだけで判定でき、構成手順を持たない点が特徴。

入力形式

N
d_1 d_2 ... d_N

制約

$1 \le N \le 3000$

$0 \le d_i \le N-1$

入出力例

入力例1

5
3 3 2 1 1

出力例1

Yes

入力例2

5
4 4 4 4 1

出力例2

No

例2は総和が $4+4+4+4+1=17$（奇数）のため、不等式を確認するまでもなく No。

概念図

ヒント（段階的開示）

ヒント1: 方向性

単純グラフでは頂点数が $N$ のとき1頂点の次数は最大で $N-1$。次数の和は辺数の2倍に等しいため、まず総和の偶奇を確認する必要がある。しかしそれだけでは不十分で、次数が極端に偏っている場合は実現不可能になることがある。この「偏り」をどう定量的にチェックするか考えよ。

ヒント2: アプローチ

数列を降順に並べたとき、上位 $k$ 個の頂点が持てる辺の本数の上限を考える。上位 $k$ 個同士で最大 $k(k-1)$ 本の辺の端点を作れ、残り $N-k$ 個とはそれぞれ最大 $\min(d_i,k)$ 本しか接続できない（相手の次数か、上位k個という人数の少ない方に制限される）。この上限が上位k個の次数合計以上でなければ矛盾する。

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

total = sum(d)
if total % 2 != 0:
    print("No")
    return

d_sorted = sorted(d, reverse=True)
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + d_sorted[i]

for k in range(1, n + 1):
    lhs = prefix[k]
    rhs = k * (k - 1) + sum(min(d_sorted[i], k) for i in range(k, n))
    if lhs > rhs:
        print("No")
        return
print("Yes")

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.read().split()
    n = int(data[0])
    d = [int(x) for x in data[1:1 + n]]

    total = sum(d)
    if total % 2 != 0:
        print("No")
        return

    d_sorted = sorted(d, reverse=True)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + d_sorted[i]

    ok = True
    for k in range(1, n + 1):
        lhs = prefix[k]
        rhs = k * (k - 1)
        s = 0
        for i in range(k, n):
            s += min(d_sorted[i], k)
        rhs += s
        if lhs > rhs:
            ok = False
            break

    print("Yes" if ok else "No")


solve()

計算量: $O(N^2)$（各 $k$ につき $O(N)$）。Fenwick Treeなどで $\min(d_i,k)$ の総和を高速化すれば $O(N\log N)$ に改善可能。

Step-by-Step 解説

1総和の偶奇判定
単純グラフの次数の総和は辺数の2倍で必ず偶数。奇数なら即座に No。

2降順ソートと累積和
数列を降順に並べ、累積和 prefix を前計算する。

3各kに対する不等式検証
右辺 $k(k-1)+\sum_{i=k+1}^{N}\min(d_i,k)$ を計算し左辺と比較。1つでも超えれば No。

4計算量とその改善
$O(N^2)$ だが $N\le3000$ なら十分。大きい $N$ ではFenwick Treeで $O(N\log N)$ に改善できる。

5Havel-Hakimi法との違い
Havel-Hakimi法は構成的アルゴリズムで実際にグラフを構築できる（$O(N^2\log N)$程度）。Erdős–Gallaiは判定のみの分析的手法。

よくあるミス

ミス	原因	正しい書き方
総和の偶奇チェックを忘れる	偶奇条件も必要十分条件の一部	総和が奇数なら不等式確認前に `No`
$d_i$ を降順でなく未ソートのまま使う	定理は降順ソート済み数列が前提	必ず `sorted(d, reverse=True)` してから適用
右辺の $\min(d_i,k)$ の範囲を誤る	0-indexedと1-indexedの対応を混同	0-indexedで `range(k, n)` が1-indexedの $i=k+1,\dots,N$ に対応
$d_i>N-1$ を弾かず計算を続ける	単純グラフの次数上限 $N-1$ を見落とす	制約で保証するか事前にチェックを入れる

次のステップ

発展: 有向グラフ版の次数列判定（Fulkerson-Chen-Anstee定理）
発展: $O(N\log N)$ への高速化（Fenwick Treeによる $\min(d_i,k)$ の総和高速化）
次回予告: 次回セッションで新テーマへ

自己評価

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

Day 098-Q5 — Erdős–Gallaiの定理（次数列のgraphical判定・不等式検証）

問題