- ベストアンサー
グラフ理論
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
【問題】 二部グラフＧが奇数個の点を含むとき、Ｇはハミルトングラフでないことを証明せよ。 【証明】 二部グラフを二分割したとき、奇数個の点を含むグラフをG_A、偶数個の点を含むグラフをG_Bとする。 いま、仮に、G_Aの点から始めるならば、 (1)V(G_A)>V(G_B)ときは、G_Bの点をすべて結び、G_Aの点で終わる。ゆえに、始点に戻ることは不可能。 (2)V(G_A)<V(G_B)ときは、G_Aの点をすべて結び、G_Bの点で終わったとき、G_Bの点が一個以上余る。ゆえに、全部の点を結ぶことは不可能。 G_Bの点から始めるときも、同様の考察ができる。 q.e.d.
関連するQ&A
- グラフ理論においての「木」
（１）木はすべて二部グラフであることを証明せよ。 （２）どのような木が完全二部グラフとなるか？ についてそれぞれしりたいのですが・・・。（１）は自明なような気がしますが、きちんとした証明方法が知りたいです。片方だけでもいいのでお願いしますm(__)m
- ベストアンサー
- 数学・算数
- ハミルトングラフの証明
単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。
- 締切済み
- 数学・算数
- グラフ理論の問題についての質問です
大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題： グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。 よろしければこの問題の証明方法を教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフKn,Kn￣、Km,n,Cn,Tn〔Ｔnは位数nの木〕の染色数をそれぞれ求めよ。 ２．グラフKn,Km,n,Cn,Tnの辺染色数をそれぞれ求めよ。 ３．オイラーの多面体公式を証明せよ。 ４．以下の問題を証明せよ。 〔１〕頂点数が３以上の平面グラフGが極大平面グラフであるための必要十分条件は、Gのすべての領域が三角形であることである。 〔２〕４頂点以上の極大平面グラフGにおいて、 △〔G〕 不等式 Σ 〔6-i〕Ni =12 〔Ni = {次数がiの頂点の数}〕が成立する。 〔３〕４頂点以上の平面的グラフには、次数５以下の頂点が存在する。 〔４〕K5,K3,3は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- グラフ理論の問題について
グラフ理論についての質問です。よろしくお願いします。 「グラフ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を示すもっとスマートな方法があるのか、ご教示いただければ幸いです。
- 締切済み
- 数学・算数
- K(3,3)完全二部グラフ 非平面性 グラフ理論
連結な平面グラフにおいて位数=p、サイズ=q,とおくと q=<3p-6 という公式？定理？がありますが、 完全二部グラフK(3,3)の非平面性を証明するのに使おうと思ったら 9<=18-6=12 で成り立ってしまいます。 すべての領域が四角形以上なら q=<2p-4というのを使えば証明できるのですが、前の方の公式がこの場合に使えないのはなぜなんでしょう
- 締切済み
- 情報工学
お礼
ありがとうございましたm(__)m