- ベストアンサー
ハミルトンに関する質問
点数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 がハミルトン閉路であることを示せ という問題が出てしまいました 正直証明とか苦手でどうやって手を付けたらいいかわからないので教えてください！ よろしくお願いします。
- tibinaneko
- お礼率0% (0/7)
- 数学・算数
- 回答数7
- ありがとう数0
- みんなの回答 （7）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (6)
- Tacosan
- ベストアンサー率23% (3656/15482)
「すべての点がつながっている」とは, どういうことでしょうか? 「何において」「どう」「つながっている」のかを書かなければ通じませんよ. あと, 「つながっている」もあいまいなのでちゃんとグラフ理論の用語を使ってほしいところ. ここで証明を書かないのはぶっちゃけ興醒めだからなんだけど, そのほかに「実はここで書いちゃうと却って質問者の負担になる」ことも頭にあるんだな. まず, ここに書かれた質問や回答には著作権が発生する可能性がある. 単に「計算しました」なんてものならさておき, 特に証明では著作権を否定できる根拠が乏しい. ということは, ここで証明を書いてもらったとしてもそれをあなたが「自分で証明した」かのようにレポートに書くのは (複製権の侵害として) 著作権法に違反するおそれがある. もちろん複製ではなく引用なら問題ではないが, 著作権法上の引用には ・引用元を明示する ・「自分で書いたもの」が主であり「引用したもの」が従であるという関係がある という要件を満たす必要がある. ということは, 回答として得られた証明をあなたのレポートの中に書くことは事実上不可能 (ここの URL が書いてあるレポートを見た先生はどう思うかねぇ). つまり, ここで証明を書いちゃうとあなたには「それ以外の証明を考える」という選択肢しかなくなっちゃうんだな. だから基本的にヒントしか書かないんだが, 次数を指折り数えるというのが本質.
補足
あなたが証明をのせたくないのはよくわかりましたが、そもそも証明をのせないのとヒントしか出せないのは違います もし、このサイトで質問を見て、教えようと思うのなら教えるべきことをきちんと書くべきです ヒントというのはあなたが教えているという状況を作ってはいない 教えれるなら、そして本当に理解できているなら、証明を載せる以外にも、そしてヒントという形以外にもくさんややり方はあるはず もし、「～してやってんだから」とか思うのなら、質問者を助けようとはしておらず、ヒントだけで満足するのはあたかも人が欲しいものを見せつけて、手の届かないところにおき、観察してるだけに見える 人が欲しいものを持っているなら、どうやって届くかを教えることくらいはするべきである
- Tacosan
- ベストアンサー率23% (3656/15482)
グラフ理論では 1つの概念に対していろいろな言葉が使われていて, 例えば cycle は「サイクル」といったり「閉路」といったりします＞#4. あんまり cycle を「回路」ということはないような気がします (「回路」というとどうしても circuit としちゃいたくなるなぁ). 厳密には「cycle とは何を指すのか」すら問題になったりするけど, 今はそれは無視. あと, ここで「路」はおそらく simple path でしょう. でいちおう証明はできたっぽぃんだけど.... ただ証明をそのまま書いちゃうのも興醒めだし (わかってもらえますよね＞#4), かといってどこまでヒントを出せばいいのかも非常に難しい. ということで, あえて超遠いヒントを一発出してみる: 2 に挙がっている閉路がハミルトン閉路であるためには, 実は隠れた「条件」が必要です. そして, その「条件」は 1 を証明するためにも (おそらく) 必要です. その「条件」とは, いったいなんでしょうか?
補足
そこをなんとか証明書いてください！！（T△T）/ 明日までなんですよーーーーー その条件は、すべての点がつながっていることですか？
- B-juggler
- ベストアンサー率30% (488/1596)
Ｎｏ．１，３です。 えっとね、「閉路」って言うのがどういうことだろうか？ ハミルトン経路や回路なら、その定義で構わないんだけど。 「閉路」って書いてあるよね？？ それはグラフってこと？ ハミルトングラフ？ だとしたら定義は難しいよ。 まぁもうちょっと書こうか。気がつくと思うけれど。 ２ のほうでは、一回しか通っていないかどうか、確かめてもらえないかなぁ？ 一週廻って、逆廻りもしてないかな？ そこもついでによく見てくれる？ Ｘ０ から始まって、 Ｘｋ までの最長路なんでしょう？ ちょっともう一回良く見てくれるかな。 (=^. .^=) ｍ（＿ ＿）ｍ (=^. .^=)
補足
閉路ってのは始点と終点が一緒ってことですよね！！ っていうことはハミルトン閉路ってのは「すべての点を通る路で、しかも始点と終点が同じ」ってことですよね！ 問題は定義されたグラフのなかにハミルトン閉路があることを証明する問題ですよね つまり、ハミルトングラフの証明ですね 2の問題は １のiに対して X0,Xi+1,Xi+2,...,Xk,Xi,Xi-1,...,X0 となる閉路がハミルトン閉路かどうかを証明する問題です この閉路ってどうやって書かれているかよくわからなくて・・・ どのようになっているのですかね？？？？？
- B-juggler
- ベストアンサー率30% (488/1596)
Ｎｏ．１です。 ちょっと訂正。 三角形の場合、次数は２ ですね。ごめんなさい。 それで、Ｎｏ．２さんがおっしゃるとおり、確かにこれは？ 補足にある定義は違う気がします。検索してみてくれる？ 友達に聴ければ・・・ じゃダメなんだ、だから。 自分でやろうとしないのが一番恥だと思ってください。 (=^. .^=) ｍ（＿ ＿）ｍ (=^. .^=)
補足
ハミルトン閉路はグラフ上にあるすべての点を一度だけ通る点だと理解してます なにが違うのですか？？ （X0,Xi+1)がE(G)に含まれる と (Xi,Xk)がE(G)に含まれるとなるiというのがまず図として頭に描くことができないのですがどのようなグラフのことを言っているのですか?
- Tacosan
- ベストアンサー率23% (3656/15482)
んん?? ちょっと待って. 「ハミルトン閉路」の定義を書いてください.
補足
時間がないです（＞＜） 友達いたら聞けたのにな～～ ハミルトン閉路は「すべての点を一度だけ通る閉路」だと理解してます オイラー閉路はすべての辺を一度だけしか通らないグラフです あと問題２の最初のスタートがXiと書いてしまいましたが、ただしくはX0ですね
- B-juggler
- ベストアンサー率30% (488/1596)
いやはや、ここまで丸投げするとは・・・。 元代数学の非常勤講師ですが、ちょっとね。 グラフ理論だろうけど、もう少しちゃんとしようか。 えっと、ヒントというか、考え方ね。 どこまで分かっていてどこが分からないのか分からないから、 割と、初歩的なことから書きます。 ｎ＝３ としてしまおう。（こういうのは最小を考えてみることも大事） 三角形だと思えばいい。 次数が（各点から出ている、入っているのと同じ線の数）は （３／２）＝１．５だから、必ず一本はあるわけだ。 ここも簡単に考えて、次数を１としてしまう。 そしたら三角形の出来上がり。いいかい？ 各点の名前はどうでもいいから、ＡＢＣとするよ。 経路Ａ－Ｂ－Ｃ ← これはどこから始めても一緒 が最長路Ｐになるね？ １ のほうは瞬殺だ。 経路Ａ－Ｂ は 経路Ａ－Ｃ－Ｂ に等しい。 ついでに、今は三角形を考えているのだから、当然閉路だね。 後は広げるだけなんだけど。 勉強しないことは恥じなくてもいいよ。 ただ、自分でやろうとしない、考えたくない！って言うのは恥じたほうがいいだろうね。 少なくとも、わかるところまでは書こうか。 (=^. .^=) ｍ（＿ ＿）ｍ (=^. .^=)
補足
三角形の場合とかはとてもよくわかります 後は広げるだけと言うことは、数学的帰納法やらを使って３以外の時も考えるということですか? また、２番は、三角形の場合はハミルトン閉路があることはすぐにわかるんですがそれを証明で示せって言われるとどうしたらいいかわからなくて・・・
関連するQ&A
- 数学の解答お願いします
点数nが３以上で、最小次数がn/2以上であるグラフGはハミルトン閉路を持つことを示したい １，Gの最長路P＝X0X1・・・・Xkを考える （X0,Xi+1)がE(G)に含まれる、(Xi,Xk)がE(G)に含まれる となるようなiが存在することを示せ ２，上記iに対して、 閉路 X0,Xi+1,Xi+2・・・・・,Xk,Xi,Xi-1,・・・・・,X0 がハミルトン閉路であることを示せ すいません 説破つまってて まず1番の最長路は適当にグラフ書いて、そのグラフの一番長い路（閉路でなくても）を見つけて、ってとこまでくらいしか考えれてません 一人で考えても時間が無くなるばかりで すいません すぐに回答できるかたお願いします
- 締切済み
- 数学・算数
- 数学IIIの問題です、添削＆解答お願いします！
数学IIIの問題です。 （１）～（３）は添削、（４）、（５）は解答を教えていただけると嬉しいです。 問、 数列｛Xi｝が次の漸化式を満たしている。 Xi+1=Xi^2+1/2(i=1,2,3,・・・) （１）すべての自然数iに対して、Xi+1≧Xiが成り立つことを示せ。 （２）lX1l≦1のとき、全ての自然数iに対してXi≦1であることを示せ。 （３）自然数ｎに対して、等式Xn+1-X1=1/2*Σ（i=1,n）(Xi-1)^2 （４）lX1l≦1のとき、Xn+1-X1≧n/2*(Xn-1)^2が成り立つことを示せ。 （５）初項X1の値に応じて、数列｛Xn｝の収束、発散について調べ、 収束するときは極限値を求めよ。 （１）Xi+1-Xi≧0 Xi^2+1/2-Xi≧0 （Xi-1）＾2/2≧0 よって、すべての自然数iに対して成り立つ （２）数学的帰納法を用いて導く。 （I）i＝1のとき、lX1l≦1よりX1≦1 よって、Xi≦1はなりたつ （II）i=kのときXi≦1が成り立つと仮定するとXk≦1 i=k+1のとき、Xｋ+1=Xｋ^2+1/2 Xk≦1よりＸｋ+1≦1 よって、Xi≦1は成り立つ (I)(II)より、全ての自然数iに対してXi≦1は成り立つ。 (3)(右辺)＝Σ（i=1,n）(Xi+1-Xi) (1より) ＝Xn+1-X1 =(右辺) したがって、成り立つ。
- ベストアンサー
- 数学・算数
- こんな関数は存在する？存在しない？
とある理由で、以下のような問題を考えています。 しかしながら、どう証明（or反例）してよいのかいいアイディア が浮かばず、質問させていただきました。 -------------------------------------- 問い： ある関数f(x1,x2)が存在したとします。 この時下記条件を満足する関数g(x1,x2,...,xn)が存在できるか。 条件： まず、任意のiとj(j≠i)を選びます。 {xk}(k≠i,j)に対して任意の定数値{ck}を設定します。 こうして生成されたh(xi,xj)=g(c1,...,xi,...,xj,...,cn)を考えます。 この関数hがh(xi,xj) = a*f(xi,xj)を常に満足する。 ここでaは0以外の定数。 ------------------------------------- 一般的に証明するのは難しそうなので、g(x1,x2,x3)の場合などでもかまいません。 また、f(x1,x2)に対して拘束条件f(x1,x2)=f(x2,x1)をかけてもかまいません。 なにか「こういうアプローチで証明(or反例)できるのではないか？」といったアイディアをお持ちではないでしょうか？ ------------------------------------------- ちなみにこの問題は量子力学のN-representability問題に端を発しています。もしこの証明ができれば、N-representability問題に対してすこし切り込めるかなぁと考えている次第です。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 数値解析の補間多項式
（１）nを１以上の整数とし,X0,X1,,,Xnを相異なるn＋1個の標本点とする。R上の関数f,g,hにおいて、gはfをX0,X1,,,Xn-1で補間し（つまり,g(Xi)=f(Xi),i=0,1,2,,,,n-1となる）、hはfをX1,,,Xnで補間するとき、関数 g(X)＋(X0ーX)/(Xn-X0)×｛g(X)ーh(X)} は、ｆをX0,X1,,,Xnで補間することを示したのですが質問があります。 まず補間するということはどんな意味を持っているのでしょうか？そしてこの問題の但し書きとしてf,g,hは多項式とは限らないとあったのですがではどう考えたらよいのでしょうか？？ 最終的にどのように証明していけばよいかアドバイスお願いします★
- ベストアンサー
- 数学・算数
- 期待値？平均？意味不明！
統計の勉強をしていて？？？？な内容に出くわし困惑しております。どなたかお知恵をお貸しください。 E(a1X1+a2X2+.....+anXn)=a1E(X1)+a2E(X2)+...+anE(Xn)・・・・(1) X1,X2,....,Xnが独立ですべて期待値μ、分散σ^2の同一分布に従い"a1=a2=...=an=1/n"の時 E(X1)=E(X2)=....=E(Xn)=μ E(X1/n+X2/n+....+Xn/n)=μ/n+μ/n+...+μ/n=μ X~=(X1+x2+....+Xn)/nとすると E(X~)=μ これまではいいんですが後に (1)の性質で"X1,X2,.....,Xn"が独立でどれも平均μとすると E(X~)=E(X1/n+X2/n+....+Xn/n) =E(X1)/n+E(X2)/n+...+E(Xn)/n =μ/n+μ/n+.....μ/n=μ と書いてありました。 μっていったい期待値なんでしょうか？平均なんでしょうか？それともどちらでもこのE(X~)=μは成立するのでしょうか？ μが平均の場合はなぜE(Xk)=μ(kは第k項の意味です)とできるのか理由も付けて教えてください。 読みにくくてすみませんがよろしくお願いします。
- ベストアンサー
- 数学・算数
- 【緊急です】期待値、分散について
【緊急です】期待値、分散について 今日の統計学の試験勉強をしていたら以下の質問がわからなくなり、困っています。 平均E(x)=5、E(x^2)=30のとき分散Var(x)=？？となる。さらにE(y)=1,E(xy)=-1ならば、共分散Cov(x,y)=-6である。n-3のとき平均u、分散σ^2＝１の正規母集団から無作為抽出された標本(x1,x2,x3)について、Σi=1 n(xi―標本平均値xバー）^2の期待値E(Σ(xi―標本平均値xバー)=？？？である。またE（Σ(xi-u)^2=？？？となる。 以上3点の問題がわかりません。噛み砕いて説明していただけると幸いです。
- ベストアンサー
- 数学・算数
- 不偏分散、ガンマ分布、そして不偏推定量
X1..Xnは独立で標準分布、期待値μ、分散σ^2。不偏分散s^2=1/(n-1) Σ（Xi - X')^2, X'=1/n ΣXi, で iは１からnまでです。X'はガンマ分布Γ（α、λ）に従い、α＝(n-1)/2, λ＝（n-1)/(2*σ~2）です。 (a) ガンマ分布を利用して、s^2がσ^2の不偏推定量であることと、その分散を求めよ。 (b) T(k)=k*s^2、kは定数 を考えます。その際に、T(k)の偏り と 分散をσ^2の推定量で表せ。そして、T(k)の 誤差の平方は（MSE)を最小値にするkを求めよ。 と言う問題があります。 最初にs^2=1/(n-1) Σ（Xi^2 - n X'^2)と表し、E(X')=σ^2と言う準備はできたのですが、それ以降さっぱりここ３,４日間考えてますがわかりません。回答は自分で導きたいと思ってますので、アドバイスをいただけないでしょうか？
- 締切済み
- 数学・算数
補足
私が二週回ってないとどうして思うのですか？ こっちは焦ってるからここに、質問しに来たんです 回答されたのを理解しようと必死です 時間がないからです それなのに教えることを怠りたいがため、そのような決めつけをするのならそもそもこのサイトの使い方が間違っています あなたは本当にわからない人達の気持ちがわからないのですね