次数からグラフを復元する

degree setから復元する

Dをdegree set {d1, d2, d3, ..., dn } (d1 < d2 < ... < dn)として、f(D)をdegree setを満たすグラフを返す関数とすると

f(D) = dn+1頂点のクリーク - f({dn - d1, dn - d2, ... , dn - d(n-1)})

となる

出題例

次数全体から復元する

判定だけならErdős–Gallai theorem - Wikipedia

復元するならHavel–Hakimi algorithm - Wikipedia

出題例