ハミルトンに関する質問

質問

点数nが３以上で、最小次数がn/2以上であるグラフGはハミルトン閉路を持つことを示したい

１，Gの最長路P＝X0X1・・・・Xkを考える
　　（X0,Xi+1)がE(G)に含まれる、(Xi,Xk)がE(G)に含まれる
　　となるようなiが存在することを示せ

２，上記iに対して、
　　閉路 Xi,Xi+1,Xi+2・・・・・,Xk,Xi,Xi-1,・・・・・,X0
　　がハミルトン閉路であることを示せ

という問題が出てしまいました
正直証明とか苦手でどうやって手を付けたらいいかわからないので教えてください！
よろしくお願いします。

回答No.7

B-juggler · ベストアンサー

ＮＯ．４です。　Ｎｏ．５さん了解！　simple pass　でしょうかね。

この辺になると国語なんですね、やはり。

そういう意味で行けば、「始点と終点が同じ」物が閉路　で構わない。

　最初の三角形で、少し形を変えてあげれば、始点と終点は同じになりますね？

そうそう違う証明が思いついているとは思えないので、やはり「次数」に

落ちるんだけど。

もうこんなことしかかけないと思うけど、

「四角形＋対角線」のとき、どうなっているか考えてみたらどうだろう。

＞X0、Xi,Xi+1,Xi+2・・・・・,Xk,Xi,Xi-1,・・・・・,X0

これの、Xi　とか　Xi-1　なんかが何を意味しているか考えてみよう。

前に「２周廻って・・・」って書いたけれど、廻ってないでしょう？
　これちゃんと考えてくれた？
　違う！って流してないか？　そんなに甘くはないよ。

じゃぁ、これはなんだろうね？　

証明が明日だからではなく、分かることが先でね。

大学でお金払っているんだからそっちでやるべきだとおもう。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

補足

私が二週回ってないとどうして思うのですか？
こっちは焦ってるからここに、質問しに来たんです
回答されたのを理解しようと必死です
時間がないからです
それなのに教えることを怠りたいがため、そのような決めつけをするのならそもそもこのサイトの使い方が間違っています
あなたは本当にわからない人達の気持ちがわからないのですね

回答No.6

Tacosan

「すべての点がつながっている」とは, どういうことでしょうか? 「何において」「どう」「つながっている」のかを書かなければ通じませんよ. あと, 「つながっている」もあいまいなのでちゃんとグラフ理論の用語を使ってほしいところ.

ここで証明を書かないのはぶっちゃけ興醒めだからなんだけど, そのほかに「実はここで書いちゃうと却って質問者の負担になる」ことも頭にあるんだな.

まず, ここに書かれた質問や回答には著作権が発生する可能性がある. 単に「計算しました」なんてものならさておき, 特に証明では著作権を否定できる根拠が乏しい. ということは, ここで証明を書いてもらったとしてもそれをあなたが「自分で証明した」かのようにレポートに書くのは (複製権の侵害として) 著作権法に違反するおそれがある.

もちろん複製ではなく引用なら問題ではないが, 著作権法上の引用には
・引用元を明示する
・「自分で書いたもの」が主であり「引用したもの」が従であるという関係がある
という要件を満たす必要がある. ということは, 回答として得られた証明をあなたのレポートの中に書くことは事実上不可能 (ここの URL が書いてあるレポートを見た先生はどう思うかねぇ).

つまり, ここで証明を書いちゃうとあなたには「それ以外の証明を考える」という選択肢しかなくなっちゃうんだな.

だから基本的にヒントしか書かないんだが, 次数を指折り数えるというのが本質.

補足

あなたが証明をのせたくないのはよくわかりましたが、そもそも証明をのせないのとヒントしか出せないのは違います
もし、このサイトで質問を見て、教えようと思うのなら教えるべきことをきちんと書くべきです
ヒントというのはあなたが教えているという状況を作ってはいない
教えれるなら、そして本当に理解できているなら、証明を載せる以外にも、そしてヒントという形以外にもくさんややり方はあるはず
もし、「～してやってんだから」とか思うのなら、質問者を助けようとはしておらず、ヒントだけで満足するのはあたかも人が欲しいものを見せつけて、手の届かないところにおき、観察してるだけに見える
人が欲しいものを持っているなら、どうやって届くかを教えることくらいはするべきである

回答No.5

Tacosan

グラフ理論では 1つの概念に対していろいろな言葉が使われていて, 例えば cycle は「サイクル」といったり「閉路」といったりします＞#4. あんまり cycle を「回路」ということはないような気がします (「回路」というとどうしても circuit としちゃいたくなるなぁ). 厳密には「cycle とは何を指すのか」すら問題になったりするけど, 今はそれは無視. あと, ここで「路」はおそらく simple path でしょう.

でいちおう証明はできたっぽぃんだけど.... ただ証明をそのまま書いちゃうのも興醒めだし (わかってもらえますよね＞#4), かといってどこまでヒントを出せばいいのかも非常に難しい.

ということで, あえて超遠いヒントを一発出してみる: 2 に挙がっている閉路がハミルトン閉路であるためには, 実は隠れた「条件」が必要です. そして, その「条件」は 1 を証明するためにも (おそらく) 必要です. その「条件」とは, いったいなんでしょうか?

補足

そこをなんとか証明書いてください！！（T△T）/
明日までなんですよーーーーー

その条件は、すべての点がつながっていることですか？

回答No.4

B-juggler

Ｎｏ．１，３です。

えっとね、「閉路」って言うのがどういうことだろうか？

ハミルトン経路や回路なら、その定義で構わないんだけど。

「閉路」って書いてあるよね？？　それはグラフってこと？
　ハミルトングラフ？
　だとしたら定義は難しいよ。

まぁもうちょっと書こうか。気がつくと思うけれど。

２　のほうでは、一回しか通っていないかどうか、確かめてもらえないかなぁ？

一週廻って、逆廻りもしてないかな？　そこもついでによく見てくれる？

Ｘ０　から始まって、　Ｘｋ　までの最長路なんでしょう？

ちょっともう一回良く見てくれるかな。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

補足

閉路ってのは始点と終点が一緒ってことですよね！！
っていうことはハミルトン閉路ってのは「すべての点を通る路で、しかも始点と終点が同じ」ってことですよね！

問題は定義されたグラフのなかにハミルトン閉路があることを証明する問題ですよね
つまり、ハミルトングラフの証明ですね

2の問題は
１のiに対して
X0,Xi+1,Xi+2,...,Xk,Xi,Xi-1,...,X0
となる閉路がハミルトン閉路かどうかを証明する問題です
この閉路ってどうやって書かれているかよくわからなくて・・・
どのようになっているのですかね？？？？？

回答No.3

B-juggler

Ｎｏ．１です。　ちょっと訂正。

三角形の場合、次数は２　ですね。ごめんなさい。

それで、Ｎｏ．２さんがおっしゃるとおり、確かにこれは？

補足にある定義は違う気がします。検索してみてくれる？

友達に聴ければ・・・　じゃダメなんだ、だから。

自分でやろうとしないのが一番恥だと思ってください。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

補足

ハミルトン閉路はグラフ上にあるすべての点を一度だけ通る点だと理解してます

なにが違うのですか？？

（X0,Xi+1)がE(G)に含まれる　と　(Xi,Xk)がE(G)に含まれるとなるiというのがまず図として頭に描くことができないのですがどのようなグラフのことを言っているのですか?

回答No.2

Tacosan

んん?? ちょっと待って.

「ハミルトン閉路」の定義を書いてください.

補足

時間がないです（＞＜）
友達いたら聞けたのにな～～

ハミルトン閉路は「すべての点を一度だけ通る閉路」だと理解してます
オイラー閉路はすべての辺を一度だけしか通らないグラフです

あと問題２の最初のスタートがXiと書いてしまいましたが、ただしくはX0ですね

回答No.1

B-juggler

いやはや、ここまで丸投げするとは・・・。

元代数学の非常勤講師ですが、ちょっとね。

グラフ理論だろうけど、もう少しちゃんとしようか。

えっと、ヒントというか、考え方ね。

どこまで分かっていてどこが分からないのか分からないから、
割と、初歩的なことから書きます。

ｎ＝３　としてしまおう。（こういうのは最小を考えてみることも大事）

三角形だと思えばいい。　次数が（各点から出ている、入っているのと同じ線の数）は

（３／２）＝１．５だから、必ず一本はあるわけだ。

ここも簡単に考えて、次数を１としてしまう。

そしたら三角形の出来上がり。いいかい？

各点の名前はどうでもいいから、ＡＢＣとするよ。

経路Ａ－Ｂ－Ｃ　←　これはどこから始めても一緒　が最長路Ｐになるね？

１　のほうは瞬殺だ。　経路Ａ－Ｂ　は　経路Ａ－Ｃ－Ｂ　に等しい。

ついでに、今は三角形を考えているのだから、当然閉路だね。

後は広げるだけなんだけど。

勉強しないことは恥じなくてもいいよ。

ただ、自分でやろうとしない、考えたくない！って言うのは恥じたほうがいいだろうね。

少なくとも、わかるところまでは書こうか。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

補足

三角形の場合とかはとてもよくわかります
後は広げるだけと言うことは、数学的帰納法やらを使って３以外の時も考えるということですか?
また、２番は、三角形の場合はハミルトン閉路があることはすぐにわかるんですがそれを証明で示せって言われるとどうしたらいいかわからなくて・・・