- 締切済み
ハミルトングラフ
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- rabbit_cat
- ベストアンサー率40% (829/2062)
http://planetmath.org/?op=getobj&from=objects&id=6466 証明自体はそんなに難しくないです。
関連するQ&A
- ハミルトングラフの証明
単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。
- 締切済み
- 数学・算数
- 離散数学 オイラーグラフ、ハミルトングラフの質問です。
離散数学 オイラーグラフ、ハミルトングラフの質問です。 添付データの画像のグラフについて考えています。 括弧の中に書いてあることが正しいのかと、このグラフはハミルトングラフであるか？ また、その理由を教えてください。 このグラフは位数（５）の（完全）グラフであり（４）次の（４-正則）グラフ ３辺形は（5Ｃ3＝ １０個） ４辺形は（5C4 * 2 = 10個) （すべての辺から偶数個の辺が出ているためオイラーグラフ）
- ベストアンサー
- 数学・算数
- ハミルトンに関する質問
点数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 がハミルトン閉路であることを示せ という問題が出てしまいました 正直証明とか苦手でどうやって手を付けたらいいかわからないので教えてください！ よろしくお願いします。
- ベストアンサー
- 数学・算数
- グラフ理論の問題について
グラフ理論についての質問です。よろしくお願いします。 「グラフGが正則でdiam(G)=3ならば、diam(~G)=2である」（~GはGの補グラフです） を証明したいです。 前の設問に「diam(G)≧3ならばdiam(~G)≦3」というのがあるので（これは証明できました）、diam(~G)=1あるいはdiam(~G)=3の場合に矛盾を導く方向で考えています。 diam(~G)=1とするとGが空グラフになってしまう、というのは分かるのですが、diam(~G)=3の場合に矛盾を導くところが上手くいきません。 どのような方針で話を進めていけば良いのか、あるいはストレートにdiam(~G)=2を示すもっとスマートな方法があるのか、ご教示いただければ幸いです。
- 締切済み
- 数学・算数
- グラフの証明を教えてください
背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをＧとします Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。 そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき Ｈの各頂点の次数は偶数である。 この証明を教えてください。
- 締切済み
- 数学・算数
- オイラーグラフの十分条件について
グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 （最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました） また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？ 以上になります。ご教示いただければ幸いです。
- ベストアンサー
- 数学・算数
お礼
ありがとうございます。 英語ですね…がんばります！