- 締切済み
グラフ理論の彩色問題
G を3 角形がない単純平面的グラフとする．このとき，G が4-彩色可能であることを示せ． この問題の証明が出来なくて困ってます。 誰かわかりやすく解説お願いします。
- pee-ka-booooooo
- お礼率0% (0/3)
- 数学・算数
- 回答数3
- ありがとう数0
- みんなの回答 （3）
- 専門家の回答
みんなの回答
- pori_boy
- ベストアンサー率60% (18/30)
こんにちは． 色々な手順があるかもしれませんが，まず，以下の問題の証明は出来ますか？ G を単純平面的グラフとする．このとき，G が6-彩色可能であることを示せ． この問題の証明が自分で出来る（もしくは証明を理解できる）のであれば， 質問の問題の証明も出来るのではないかなと思います．
- Tacosan
- ベストアンサー率23% (3656/15482)
「こういう丸投げ が一番困る」の部分は #1 に同意. そして, できないなら素直に「できない」って言ったほうがいいと思う. 少なくとも, 個人的には「どうすれば証明できるのか」が思いつかない. #1 の方針でいいのかもしれんけど, なんというか, 超大質量ブラックホール並みの落とし穴が掘ってあるように見えるんだよね....
- B-juggler
- ベストアンサー率30% (488/1596)
こういう丸投げ が一番困るね。 代数学の非常勤講師ね（病気療養だけど）。 「どこまで分かっているのか」が分からないから、 どっから書いていいのかわからないんですよ。 ４色問題だから、「どういう状況のグラフであれば ４色でいい」というのが 分かっていないようです。 単純平面グラフ って何かをまず見直して。 それを理解して、 「三角形を含まない 単純平面グラフ」が理解できれば 証明も何も必要のないくらいに簡単なんだよ？ う～ん、この頃、大学生も丸投げするなぁ～。 σ(・・*)が教えていた頃も、そうだったのかな？ ｍ（＿ ＿）ｍ
関連するQ&A
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフ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をn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。 このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。 ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。
- ベストアンサー
- 数学・算数
- ３彩色問題について質問です。
下記の問題が解けません。説明をよろしくお願いします。 P=NPとする。３彩色可能グラフがあるとして、有効な３彩色を作れる多項時間アルゴリズムが存在することを示せ。 ヒント：P=NPの仮定はグラフが多項時間内で３彩色可能なグラフかどうかを決定できることを示唆する。しかしP=NPの仮定にはこのテストがどのようになされるかしめされていない。大事なのはそのテストが探せるということを証明することである。
- 締切済み
- 数学・算数
- グラフ理論の問題についての質問です
大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題： グラフ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を示すもっとスマートな方法があるのか、ご教示いただければ幸いです。
- 締切済み
- 数学・算数
- 【グラフ理論】証明問題が分かりません。【難問】
テストに向けてグラフ理論の勉強をしているのですが・・・ 下記の証明問題で行き詰まってしまいました。 『uv ∉ E(G) → uw ∉ E(G)というグラフは完全K部グラフしか存在しない事を証明せよ。』 当方、証明問題に滅法弱く、どう解けば良いのか方針すら分かりません。 方針や証明の過程など詳しくご教授して頂ければ幸いです。 何卒宜しくお願い致します。
- 締切済み
- 数学・算数
- 辺彩色のアルゴリズム
グラフ理論についての質問です。 平面グラフを辺彩色するのに必要な色の最小の数を求めるアルゴリズムがあるとききました。 しかし、調べてみましたがどのようなものかわかりません。 知っている方いましたら教えてください。
- 締切済み
- その他（プログラミング・開発）
