- 締切済み
ハミルトングラフの証明
単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。
- saldsstripe
- お礼率0% (0/3)
- 数学・算数
- 回答数1
- ありがとう数0
- みんなの回答 (1)
- 専門家の回答
みんなの回答
- stomachman
- ベストアンサー率57% (1014/1775)
グラフG'がハミルトングラフの定義を満たす、ということを逐一確認すればいいんです。自明なら容易でしょ?
関連するQ&A
- グラフ理論の頂点に関する性質についての証明
全ての2頂点 v1,v2∈Gについて、ある一つの頂点w∈Gが存在しv1とwは隣接していて、かつ、v2とwも隣接しているようなグラフGを考える。このとき・・・ (a)v∈Gとwが非隣接ならばδ(v)=δ(w)を証明せよ (b)ある頂点の次数k>1かつどの頂点にも隣接しているような頂点は一つもない時、すべての頂点の次数はkになることを証明せよ の2問について証明の仕方を教えていただけると助かります。問題の状況がそもそもわかりません・・・(δはその頂点から出ている辺の数) もとの問題が英文なのでそっちも載せておきます。 Let G be a graph. Suppose that for every pair of distinct vertices v1 and v2 in G, there is a unique vertex w in G such that v1 and w are adjacent and v2 and w are adjacent. (a) Prove that if v and w are nonadjacent vertices in G , then δ(v)=δ(w). (b) Prove that if there is a vertex of degree k>1 and no vertex is adjacent to all other vertices, then the degree of every vertex is k.
- ベストアンサー
- 数学・算数
- ハミルトンに関する質問
点数nが3以上で、最小次数がn/2以上であるグラフGはハミルトン閉路を持つことを示したい 1,Gの最長路P=X0X1・・・・Xkを考える (X0,Xi+1)がE(G)に含まれる、(Xi,Xk)がE(G)に含まれる となるようなiが存在することを示せ 2,上記iに対して、 閉路 Xi,Xi+1,Xi+2・・・・・,Xk,Xi,Xi-1,・・・・・,X0 がハミルトン閉路であることを示せ という問題が出てしまいました 正直証明とか苦手でどうやって手を付けたらいいかわからないので教えてください! よろしくお願いします。
- ベストアンサー
- 数学・算数
- グラフの証明を教えてください
背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをGとします Gの中のツアーで中で、最も辺の数が多いものをCとします。 そのときGからCの辺をすべて取り除いたグラフの連結成分Hがあるとしたとき Hの各頂点の次数は偶数である。 この証明を教えてください。
- 締切済み
- 数学・算数
- 完全グラフが平面的となるための証明について
完全グラフKnと完全2部グラフKn,mが平面的となるためのn,mの範囲を求め、証明せよ。 という問題があるのですが証明が分かりません。 完全グラフはn≦4、完全グラフ2部グラフはn=1 or 2。 どなたか証明を教えてください。
- ベストアンサー
- 数学・算数
- オイラーグラフの十分条件について
グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 (最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました) また、そもそもGは連結という条件が必要だと思うのですが(非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので)、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか? 以上になります。ご教示いただければ幸いです。
- ベストアンサー
- 数学・算数
- グラフ理論(木について)の証明
2点以上の点からなる木は、2部グラフであることを数学的帰納法を用いて証明するには、どのようにしたらよいのでしょうか? ※使っても良い事実として、「2点以上の点からなる木では葉が存在する」というものがあります。 点の個数が2のときは明らかであることは分かるのですが、その後どのようにしたらよいのかが分かりません。 (もし、点の個数を使うときはn,辺の個数はeを用いて教えてください) よろしくお願いします。
- 締切済み
- 数学・算数