Day 089-Q2 — Havel-Hakimi法（次数列の graphical 実現可能性判定）

問題

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

入出力例

6
3 3 2 2 1 1

Yes

4
3 3 3 1

No

例2は次数合計10（偶数）で必要条件は満たすが、Havel-Hakimi法で構成すると途中で負の次数が生じ実現不可能。

概念図: 最大次数の頂点を、次数が大きい順に接続する貪欲構成

ヒント

def is_graphical(d):
    if sum(d) % 2 != 0:
        return False
    while True:
        d.sort(reverse=True)
        if d[0] == 0:
            return True
        k = d[0]
        d = d[1:]
        if k > len(d):
            return False
        for i in range(k):
            d[i] -= 1
            if d[i] < 0:
                return False

模範解答

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    d = list(map(int, data[1:1 + n]))

    if sum(d) % 2 != 0 or any(x < 0 or x > n - 1 for x in d):
        print("No")
        return

    while True:
        d.sort(reverse=True)
        if d[0] == 0:
            print("Yes")
            return
        k = d[0]
        d = d[1:]
        if k > len(d):
            print("No")
            return
        for i in range(k):
            d[i] -= 1
            if d[i] < 0:
                print("No")
                return

main()

計算量: 各イテレーションで要素数が1減り、ソートに $O(N\log N)$ かかるため全体で $O(N^2\log N)$。

Step-by-Step 解説

Step 1: 必要条件のチェック

次数合計は必ず偶数（握手補題）。次数は $N-1$ を超えられない。これらを満たさなければ即座に No。

Step 2: 最大次数の頂点を選び貪欲に接続

降順ソートし先頭値 $k$ を取り出す。残りの上位 $k$ 個に接続するのが最適（Havel-Hakimi の定理）。

Step 3: 接続先の次数を1ずつ減らす

上位 $k$ 個を1ずつ減らし、負になれば矛盾で No。

Step 4: 繰り返して全次数が0になるか判定

全て0になれば Yes。k > 残り頂点数 となれば No。

よくあるミス

次のステップ

• 発展問題: Erdős–Gallai の定理を使った高速判定への置き換え
• 発展問題: 実現可能な場合の辺集合の具体的な構成・出力

自己評価