Havel-Hakimi

個人的メモ

次数列を降順に $D = \{ d_1, \ldots ,d_n \}$ のように並べたときに $(d_1, d_2), \ldots ,(d_1, d_{d_1+1})$ の辺を張り, 残りの次数列 $d_2-1,\ldots,d_{d_1+1}-1,d_{d_1+2},\ldots,d_n$ を降順に並べたもの($D'$ とする)に再帰的に同様の操作を繰り返す.
次数列に対応する単純グラフが存在することを graphical であると言うことにする. このとき $D$ が graphical なら $D'$ も graphical となることを背理法で示す. 実際にこれが示せたとする. するともし上記の手法で再帰的に頂点を削除していく途中で $(d_1, d_2), \ldots ,(d_1, d_{d_1+1})$ のように辺を張れなくなったとき, つまり $D'$ が graphical でないと分かったときにその対偶を繰り返し適用することで元の次数列を満たす単純グラフが存在しないことが分かる. 逆にもし上記の手法で再帰的に頂点を削除していくことができたとする. 次数列が $D'$ となる単純グラフに $(d_1, d_2), \ldots ,(d_1, d_{d_1+1})$ の辺を張ってできるグラフは明らかに次数列 $D$ を満たす単純グラフとなっているため結局元の次数列を満たす単純グラフの構成ができたことになる.
ゆえに $D$ が graphical なら $D'$ も graphical となることが示せれば Havel Hakimi アルゴリズムはグラフの次数列が与えられたときにそれを満たす単純グラフが存在する場合にのみ, そしてそのような場合は常に正しい解を返すアルゴリズムとなる.
以下 こちらの資料 を基にその証明を記す.
$G (V(G) = {v_1,\ldots,v_n})$ を $\mathrm{deg}(v_i) = d_i, d_1 \ge d_2, \dots, \ge d_n (1 \le i \le n)$ である単純グラフのうち $v_1$ と隣接している頂点の次数の総和が最大となるようなものとする. このときこのようなグラフ $G$ において $v_1$ に隣接している頂点の次数の集合は必ず $\{ d_2,\ldots,d_{d_1+1} \}$ となることを示す. 別の言葉で言い換えると次数列 $D$ を満たす単純グラフが存在するならば, 必ずそのようなグラフの中で次数最大の頂点 $v_1$ に隣接している頂点の次数の集合が $\{ d_2,\ldots,d_{d_1+1} \}$ となるようなものが存在することを示す. これが示せれば上記の手法によって再帰的に頂点を削っていくことで graphical 性が損われることはないことが分かる.
これが成り立たないとすると $d_j > d_k$ となるような異なる $2$ 頂点 $v_j, v_k$ で辺 $(v_1, v_k)$ は存在するが, 辺 $(v_1, v_j)$ は存在しないというようなものが取れる. また $d_j > d_k$ よりある頂点 $v_l$ で辺 $(v_j, v_l)$ は存在するが, 辺 $(v_j, v_k)$ は存在しないというようなものが取れる.
ここで辺 $(v_1, v_k)$, 辺 $(v_j, v_l)$ を辺 $(v_1, v_j)$, 辺 $(v_k, v_l)$ に付け替える操作を行っても次数は変化せず, また単純性も保たれる. このような操作を行うと, 頂点 $v_1$ に隣接している頂点の次数の総和が変更前よりも大きなグラフが得られることになり矛盾. よって示せた.
計算量は並び替えをバケットソートの要領で行ってやると, 線形時間で構築可能.

(修正)
ランダムグラフの生成 の際にグラフの次数列が与えられて, できることならそれに対応する単純"連結"グラフを構成したいというモチベーションがあり, こちらの資料を参考にグラフの次数列が与えられたときにそれに対応する単純グラフの中でも連結なものが存在するならば常にそのようなものを出力するアルゴリズムに変更した.
具体的な方法は, 上記の説明では最大次数の頂点から辺を張っていたが, 非ゼロ最小次数の頂点 $v$(次数を $d$ とする) に注目しそれ以外の頂点について次数の大きい上位 $d$ 個の頂点と $v$ の間に辺を張るということをする.
単純グラフの構成可能性に重要な部分はどの頂点から辺を張るかということではなく, ある頂点(次数を $d$ とする) に注目したときにそれ以外の頂点で次数の大きい上位 $d$ 個の頂点との間に 1 つずつ辺を張ることだということは上記の証明から分かる. つまり最大次数の頂点である必要は特になく, この変更によって単純グラフを構成するという意味でのアルゴリズムの正当性は変わらない.
次に連結なグラフが存在する場合に必ず連結なグラフを返すかということを考える.
まず graphical な次数列 $D = \{ d_1, \ldots ,d_n \}$(便宜上降順に並んでいるとする) に対して, 単純連結なグラフが存在するかどうかの必要十分条件は $d_i \ge 1 (1 \le i \le n)$ かつ $\sum_{1 \le i \le n} d_i \ge 2 (n - 1)$ であることが分かる. 必要性は明らかだし, 十分性は条件を満たした上で連結でない単純グラフがあったとすると必ず橋でないような辺を持つ連結成分が存在するのでその辺 $(a, b)$ と異なる連結成分に属するある辺 $(c, d)$ について swap 操作($(a, b)$, $(c, d)$ $\Rightarrow$ $(a, c)$, $(b, d)$) を繰り返し行えば連結にすることが可能であることから分かる.
次数列 $D = \{ d_1, \ldots ,d_n \}$ を満たす単純連結グラフが存在するとする. $D'$ を次数列 $\{ d_1 - 1, \ldots, d_{d_n} - 1, d_{d_n+1}, \ldots ,d_{n-1} \}$ から次数 $0$ の要素を除いた次数列とする. このとき $D'$ を満たす単純連結グラフが存在しないと仮定すると矛盾が生じることが上記の必要十分条件に注目すると簡単に分かる.
また $(d_1, d_n), \dots, (d_{n-1}, d_n)$ と辺を張る操作はもちろん単純かつ連結の性質を損なわないので上記の手法で, 存在するならば必ず連結なグラフを返すことが分かる. 厳密には $d_1 = d_n = 1$ となる場合に問題が生じそうであるが, 次数列 $D$ を満たす連結グラフが存在するという条件から $\{1, 1\}$ の場合に限定されるため特に問題はない.
ちなみにより正確に, 与えられた次数列を満たす単純グラフの中での最小連結成分数が $C$ であるとき, アルゴリズムは連結成分数が $C$ となる単純グラフを返す.