ハミルトングラフ

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

No.1 回答者： rabbit_cat 回答日時： 2007/08/26 07:04

＞ハミルトングラフになるときって、頂点が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」となる場合はどのように判断すればいいのでしょうか？

補足日時：2007/08/26 22:39

No.2 ベストアンサー 回答者： rabbit_cat 回答日時： 2007/08/27 00:31

＞Ｃ６のように「deg(v)+deg(w)≦n」となる場合はどのように判断すればいいのでしょうか？

簡単に判断できる方法はないです。与えられたグラフがハミルトングラフかどうかを判定する問題は、ＮＰ完全問題の有名な例です。

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

この回答へのお礼

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

お礼日時：2007/09/01 22:55