- 締切済み
【グラフ理論】証明問題が分かりません。【難問】
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- alice_44
- ベストアンサー率44% (2109/4759)
u,v,w に、それぞれ∀とか∃とか付いてないの？ ∀u,v,w であれば、その式は、 G が完全グラフか、辺のひとつもないグラフかの どちらかであることを示している。 対偶と併せて考えると、∀u,(∀v,uv∈E ⇔ ∀w,uw∈E) と同値になるから、uv∈E は、∀u,v について 真か偽かに統一されている。
関連するQ&A
- グラフ理論の問題についての質問です
大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題： グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。 よろしければこの問題の証明方法を教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- グラフ理論の問題について
グラフ理論についての質問です。よろしくお願いします。 「グラフ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をn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。 このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。 ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。
- ベストアンサー
- 数学・算数
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフ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は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- グラフ理論（木について）の証明
2点以上の点からなる木は、2部グラフであることを数学的帰納法を用いて証明するには、どのようにしたらよいのでしょうか？ ※使っても良い事実として、「2点以上の点からなる木では葉が存在する」というものがあります。 点の個数が2のときは明らかであることは分かるのですが、その後どのようにしたらよいのかが分かりません。 （もし、点の個数を使うときはn，辺の個数はeを用いて教えてください） よろしくお願いします。
- 締切済み
- 数学・算数
- 隠れ端末問題とグラフ理論の関係についての質問
現在、大学の理工学部の情報工学科に所属し、アドホックネットワークを研究している研究室に配属された者です。この研究室ではアドホックネットワークについて、「グラフ理論の応用」を基本的な方針としています。 私は卒研のテーマとして、アドホックネットワークにおける重要な問題である「隠れ端末問題」を研究することになりましたが、正直、どう研究を進めていって良いか全く分かりません。 「グラフ理論を用いて、隠れ端末問題を研究する」という、漠然とした方針は決まっているのですが、そもそも、隠れ端末問題とグラフ理論がどう関わっているのか、そして、何が問題となっていて、何を目的として研究をすれば良いのかが分かりません。 論文を検索するWebサイトで、「隠れ端末問題」や「グラフ理論」をキーワードにして色々と検索してみたのですが、隠れ端末問題の解決においてグラフ理論を利用している論文は全く見つかりませんし、論文を見ても、隠れ端末問題において現在何が問題となっていて、そして何を目標として研究するべきなのかが把握できません。 研究室の教授は放任主義で、こちらが質問をしてもはっきりとした答えが返ってきません。 もしこの分野にお詳しい方がいらっしゃいましたら、 ・隠れ端末問題とグラフ理論がどう関係しているのか ・隠れ端末問題において、現在何が問題なのか ・問題を解決するための研究の目的と流れ 以上の質問に答えて頂けると有り難いです。
- 締切済み
- 数学・算数
お礼
回答ありがとうございます。 問題の方は、自己解決する事が出来ました。 お騒がせして、申し訳ありませんでした＞＜