atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ グラフ理論 次数列 Erdos–Gallai の定理 Havel–Hakimi アルゴリズム 1. 概要 単純無向グラフにおいて，各頂点の次数を並べてできる列 $d = (\deg(1),\deg(2),\ldots,\deg(n))$ を次数列といいます． 本記事では，$d=(d_1,d_2,\ldots,d_n)$ が単純無向グラフの次数列となるための必要十分条件を与える $\text{Erd\H{o}s--Gallai}$ の定理および，そのような単純無向グラフを実際に構成するHavel–Hakimi アルゴリズムを解説します． なお，文字表示の都合により記事タイトルや見出しでは「$\text{Erd\H{o}s--Gallai}$ の定理」を「Erdos–Gallai の定理」… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fdegree_sequence" title="単純無向グラフの次数列 - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:16:43 rich https://info.atcoder.jp/entry/algorithm_lectures/degree_sequence 1.0 100%