- ベストアンサー
グラフ理論
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
三角形を持たない単純平面的グラフについて, １．どの頂点を取り除いてもやはり三角形を持たない単純平面的グラフである ２．次数が高々 3 の頂点が必ず存在する ことが言えれば, 頂点数に関する帰納法で終了じゃない? まあ, きちんと考えたわけじゃないけど. でも, m ≦ 2n-4 って条件は必要なのかなぁ.... ２ を証明するためにはあった方がいいけど....
関連する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の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。
- ベストアンサー
- 数学・算数
- グラフ理論の彩色問題
G を3 角形がない単純平面的グラフとする．このとき，G が4-彩色可能であることを示せ． この問題の証明が出来なくて困ってます。 誰かわかりやすく解説お願いします。
- 締切済み
- 数学・算数
- グラフの証明を教えてください
背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをＧとします Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。 そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき Ｈの各頂点の次数は偶数である。 この証明を教えてください。
- 締切済み
- 数学・算数
- グラフ理論の問題についての質問です
大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題： グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。 よろしければこの問題の証明方法を教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- グラフ理論（幾何学）
グラフ理論で分からない問題が・・・。 Ｇは多面体（多面体グラフ）として、そのすべての面の境界は五角形または六角形であるとする。この時、 （１）オイラーの公式を用いて、Ｇには１２個以上の五角形の面がなければならないことを示せ。 （２）さらに、各頂点ではちょうど３つの面が会うとすると、Ｇにはちょうど１２個の五角形の面があることを示せ。 ちなみにオイラーの公式とは点の数ｎ、辺数ｍ、面の数ｆとするとき、ｎ－ｍ＋ｆ＝２となる。 なんですが、教えてください、お願いしますm(__)m
- ベストアンサー
- 数学・算数
- n角形の頂点をt色以下で塗り分けるグラフ彩色
http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%BD%A9%E8%89%B2 によると、 隣接する頂点同士が同じ色にならないように全頂点に彩色する問題を頂点彩色という。 彩色多項式とは、与えられたグラフをt色以下で彩色したときの彩色の組合せ数を求める式である。 閉路グラフC_n(つまり、n角形)をt色以下で彩色したときの彩色多項式は、 (t-1)^n+(-1)^n*(t-1) これがどのように示されるのかがわからないので、どうか教えていただけないでしょうか。
- ベストアンサー
- 数学・算数
お礼
わかりました！！ ありがとうございます