ハミルトンに関する質問

Question

点数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
　　がハミルトン閉路であることを示せ

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

B-juggler · Accepted Answer

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

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

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

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

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

落ちるんだけど。

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

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

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

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

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

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

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

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

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

Tacosan · Answer

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

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

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

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

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

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

Tacosan · Answer

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

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

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

B-juggler · Answer

Ｎｏ．１，３です。

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

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

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

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

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

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

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

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

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

B-juggler · Answer

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

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

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

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

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

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

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

Tacosan · Answer

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

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

B-juggler · Answer

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ハミルトンに関する質問

ＮＯ．４です。

この回答への補足

この回答への補足

この回答への補足

Ｎｏ．１，３です。

この回答への補足

Ｎｏ．１です。

この回答への補足

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

この回答への補足

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

この回答への補足

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング