📂グラフ理論

ハベル-ハキミ アルゴリズムの証明

定理

非増加シーケンス $D = (d_{1} , \cdots , d_{n})$ が与えられているとしよう。$D$ がグラフィックであれば、次の方法で $D$ の実現 $G$ を見つけることができる。

• ステップ1.
  $n$ 個の頂点 $v_{1} , \cdots , v_{n}$ を持つヌルグラフを作る。
• ステップ2. $k = 1, \cdots , n$
  • ステップ2-1.
    $v_{k}$ と $v_{k+1} , \cdots , v_{d_{k} + 1}$ を繋げる。
  • ステップ2-2.
    $d_{k+1} , \cdots , d_{d_{k}+1}$ を $1$ ずつ減少させる。
  • ステップ2-3.
    $d_{k} \gets 0$ のように代入する。$D = (0,\cdots , 0)$ になるまでステップ2.を繰り返す。

$D$ がグラフィックであれば、次数が $d_{1}$ の頂点 $v_{1}$ が $v_{2} , \cdots , v_{d_{1} + 1}$ と隣接する実現 $G$ が存在する。

解説

ハベル-ハキミ アルゴリズムは、エルデシュ-ガライの定理の存在を保証する実現を具体的に見つけるアルゴリズムだ。その原理は単に最も次数が高い頂点から処理して、細かい残り物がないようにするだけだ。先に次数を与えてからグラフを構築する点で、ランダムグラフの次数がどのような分布をするかを構築するのに直接使われる。

例えば、$(5,5,5,3,2,2,1,1)$ のようなシーケンスがあれば、ハベル-ハキミ アルゴリズムで得られる実現は上のようになる。時間が許せば、エルデシュ-ガライの定理を使ってグラフィックなシーケンスを作ってみて、ハベル-ハキミ アルゴリズムなしで実現を探せることを推奨する。その有用性がわかるはずだ。

証明

$D$ が更新されるたびに、次数の最大値は徐々に小さくなる。各ステップで次数が最大のノード $v_{k}$ が $v_{k+1} , \cdots , v_{d_{k} + 1}$ と隣接するだけでよく、次数が $d_{1}$ の最初の頂点 $v_{1}$ が $v_{2} , \cdots , v_{d_{1} + 1}$ と隣接していることを示せば、数学的帰納法によって証明が完了する。

$D$ の任意の実現 $R$ の頂点が $\deg (v_{i}) = d_{i}$ を満たすとして、次のように二つの集合を定義しよう。 $$T_{R} := \left\{ v_{2} , \cdots , v_{d_{1} + 1} \right\} \\ N_{R}(v_{1}) := \left\{ v \in V(R) : vv_{1} \in E(R) \right\}$$ 定義で、$T_{R}$ はシーケンス $D$ の $v_{1}$ の後の $d_{1}$ 個の頂点を集めた集合であり、$N_{R}(v_{1})$ は $v_{1}$ のニューバーフッド、つまり $R$ で実際に $v_{1}$ と隣接している頂点の集合だ。次に、次の整数 $t_{R}$ を考えてみよう。 $$t_{R} := \left| N_{R} (v_{1}) \cap T_{R} \right|$$ 今、$G$ は $D$ の実現の中で $t_{G}$ を最大化する実現であることを示さなければならない。これはつまり、$T_{G} = N_{G}(v_{1})$ と $t_{G} = d_{1}$ を満たし、次数が $d_{1}$ の $v_{1}$ が $v_{2} , \cdots , v_{d_{1} + 1}$ と隣接していることを意味する。もし$t_{G} = d_{1}$ ならば、自然に$T_{G} = N_{G}(v_{1})$ であり、$G$ が$t_{G}$ を最大化する実現でいるためにこれ以上示す必要はない。今、$t_{G} < d_{1}$ の場合を考えてみよう。もし$t_{G'} = t_{G} + 1$ を満たす$D$ の別の実現 $G'$ が存在すれば

$t_{G'}<d_{1}$ の場合、$v_{1}$ は何らかの$v_{x} \in T_{G'}$ と隣接していない代わりに、何らかの $v_{y} \in T_{G'}^{c}$ と隣接する必要がある。上の図での赤い点線は、$G$ には存在するが$G'$ では削除されたエッジであり、赤い実線は$v_{1}$ の次数が一定でなければならないために新しく作られたエッジだ。

$v_{1}$ と同様に、$v_{x}$ と $v_{y}$ の次数も維持されなければならず、もともと $G$ で $v_{x}$ とは隣接しておらず$v_{y}$ と隣接していた $v_{z}$ を一つ選んで$v_{x} v_{z}$ を追加し$v_{y} v_{z}$ を削除する。こうすると、元の次数シーケンス $D$ は全く変わらず、$G'$ は$D$ の実現と考えられる。しかし、$G'$ は$T_{G'}$ から$v_{x}$ が一つ欠け、$N_{G'}(v_{1})$ に$v_{y}$ が一つ追加されたため、$t_{G'}$ はむしろ$t_{G}$ より小さくなった。これは$t_{G'} = t_{G} + 1$ を満たす実現$G'$ の存在に矛盾し、したがって$t_{G} = d_{1}$ でなければならない。つまり、実現$G$ の$v_{1}$ は$v_{2} , \cdots , v_{d_{1} + 1}$ と隣接している。

■