• 締切済み

ハミルトングラフの証明

単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。

みんなの回答

  • stomachman
  • ベストアンサー率57% (1014/1775)
回答No.1

グラフG'がハミルトングラフの定義を満たす、ということを逐一確認すればいいんです。自明なら容易でしょ？

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • ハミルトングラフ

    ハミルトングラフになるときって、頂点がn個で、任意の二つの点ｖ,ｗ隣接してないとき deg(v)+deg(w)≧n なんで、 つまり頂点ｖとｗの次数の合計がn以上なら、成り立つんですよね？ でも閉路グラフＣ6の時って、どの頂点でも ２+２≦６ になるのにハミルトングラフなんですよね？ ハミルトングラフってどんなときになるんですか？

  • ハミルトングラフ

    グラフ理論の証明なのですが、 単純グラフＧについて、ｃ(Ｇ)をＧの閉包とすると Ｇがハミルトン⇔ｃ(Ｇ)がハミルトン (⇒)は明らかですが (十分条件)の証明がわかりません。 十分条件の証明を教えてください。 よろしくお願いします。

  • グラフ理論の頂点に関する性質についての証明

    全ての２頂点　v1,v2∈Gについて、ある一つの頂点ｗ∈Gが存在しｖ1とｗは隣接していて、かつ、v2とｗも隣接しているようなグラフGを考える。このとき・・・ （a)ｖ∈Gとｗが非隣接ならばδ(ｖ）＝δ(ｗ）を証明せよ （b）ある頂点の次数ｋ＞１かつどの頂点にも隣接しているような頂点は一つもない時、すべての頂点の次数はｋになることを証明せよ の２問について証明の仕方を教えていただけると助かります。問題の状況がそもそもわかりません・・・（δはその頂点から出ている辺の数） もとの問題が英文なのでそっちも載せておきます。 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.

  • グラフ理論

    「二部グラフＧに奇数個の点があるとき、Ｇはハミルトン・グラフでない」ことを証明してください。お願いしますm(__)m

  • ハミルトンに関する質問

    点数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 　　がハミルトン閉路であることを示せ という問題が出てしまいました 正直証明とか苦手でどうやって手を付けたらいいかわからないので教えてください！ よろしくお願いします。

  • グラフの証明を教えてください

    背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをＧとします Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。 そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき Ｈの各頂点の次数は偶数である。 この証明を教えてください。

  • 一筆書き可能の証明

    ケー二スバルグの橋の問題から、下のことが出てきました。 (1) 連結な平面グラフの各頂点が偶数個の辺に隣接している⇒ 連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。 (2) 連結な平面グラフのちょうど２つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能 (1)、(2)をそれぞれ、証明したいのですが、なかなかできません。 どなたか教えていただけないでしょうか？

  • 完全グラフが平面的となるための証明について

    完全グラフKnと完全２部グラフKn,mが平面的となるためのn,mの範囲を求め、証明せよ。 という問題があるのですが証明が分かりません。 完全グラフはn≦4、完全グラフ２部グラフはn=1 or 2。 どなたか証明を教えてください。

  • オイラーグラフの十分条件について

    グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 （最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました） また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？ 以上になります。ご教示いただければ幸いです。

  • グラフ理論（木について）の証明

    2点以上の点からなる木は、2部グラフであることを数学的帰納法を用いて証明するには、どのようにしたらよいのでしょうか？ ※使っても良い事実として、「2点以上の点からなる木では葉が存在する」というものがあります。 点の個数が2のときは明らかであることは分かるのですが、その後どのようにしたらよいのかが分かりません。 （もし、点の個数を使うときはn，辺の個数はeを用いて教えてください） よろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する