アルゴリスト

アルゴリズムについてのブログ

ハミルトングラフ - グラフ理論入門5

すべての点を1度だけ通ってもとに戻る閉じた小道が存在するなら、その閉路をハミルトングラフという。すべての点を通る道がある場合は半ハミルトングラフ。知られている定理の多くは「Gに十分の多くな辺があれば、Gはハミルトンである」という形をしており、この中で有名なものはDiracの定理として知られる。それよりもより一般的なものはO.Oreによるもの。

定理: 単純グラフGにはn(≧3)個の点があるとする。隣接していない任意の2点vとwについて、 deg(v) + deg(w) \geq n が成立するならGはハミルトングラフ。

証明: 定理が偽とする。Gはハミルトングラフではないが、n個の点を持ち、点次数に関する上の条件を満足しているとする。もう1本どんな辺を付け加えてもハミルトングラフになると仮定してもよい。したがってGにはすべての点を含む道  v_1,...,v_nがある。しかし、Gはハミルトングラフではないので、道の始点 v_1と終点 v_nは隣接しない。よって deg(v_1)+deg(v_n) \geq nである。したがって、点 v_i v_1に隣接し、 v_{i-1} v_nに隣接するような2つの点 v_i v_{i-1}が存在する。このときGは  v_1,v_2,...,v_{i-1},v_n,v_{n-1},...,v_{i+1} ,v_i ,v_1 となるハミルトン閉路があることになり矛盾。□

系(Dirac): 単純グラフGにn(≧3)個の点があるとすると、すべての点vについて deg(v) \geq \frac{1}{2}nならばGはハミルトングラフである。

証明: 任意の2点v,wについて deg(v)+deg(w) \geq nなのでOreの定理から直ちに証明できる。

参考