ハミルトングラフ

質問

ハミルトングラフになるときって、頂点がn個で、任意の二つの点ｖ,ｗ隣接してないとき
deg(v)+deg(w)≧n
なんで、
つまり頂点ｖとｗの次数の合計がn以上なら、成り立つんですよね？
でも閉路グラフＣ6の時って、どの頂点でも
２+２≦６
になるのにハミルトングラフなんですよね？
ハミルトングラフってどんなときになるんですか？

回答No.2

rabbit_cat · ベストアンサー

＞Ｃ６のように「deg(v)+deg(w)≦n」となる場合はどのように判断すればいいのでしょうか？
簡単に判断できる方法はないです。与えられたグラフがハミルトングラフかどうかを判定する問題は、ＮＰ完全問題の有名な例です。

もちろん、頂点数がＮ個のとき、Ｎ！通りの可能性を全てしらみつぶしに調べれば、ハミルトングラフかどうか判断できるわけですが。

お礼

簡単には判断できないんですか...
でも条件の違いについてはわかりました！
ありがとうました！！

回答No.1

rabbit_cat

＞ハミルトングラフになるときって、頂点がn個で、任意の二つの点ｖ,ｗ隣接してないとき
＞deg(v)+deg(w)≧n
＞なんで、
＞つまり頂点ｖとｗの次数の合計がn以上なら、成り立つんですよね？
これ（Ore's theorem）は、十分条件であって、必要条件ではないんで、これが成り立たなくてもハミルトングラフになる場合もあります。

必要十分条件は、Bondy-Chvátal theoremてやつが有名。
n個の頂点をもつグラフＧについて、
任意の二つの点ｖ,ｗ隣接してないとき
deg(v)+deg(w)≧n
なら、vとwの間に新たに辺を追加する
って処理をしたグラフをＧの閉包っていいます。
で、
Ｇがハイミルトングラフ ⇔ Ｇの閉包がハミルトングラフ
って定理です。

補足

返事ありがとうございます。
「deg(v)+deg(w)≧n」になる場合はわかりましたが
Ｃ６のように「deg(v)+deg(w)≦n」となる場合はどのように判断すればいいのでしょうか？