- ベストアンサー
グラフ理論（幾何学）
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
五角形をx個、六角形をy個とすると面の数はx+y、辺の数は(5x+6y)/2となります。するとオイラーの公式より点の個数nはn=3/2x+2y+2となります。 一方、多面体の各頂点では3つ以上の面が会いますので頂点の個数は(多角形の頂点の数5x+6yは三重以上重複しているので)(5x+6y)/3以下になります。 よって 3/2x+2y+2<=(5x+6y)/3 を解けば12<=xとなります。 また各頂点で会う面が丁度3個の時には等号がなりたつので丁度12個になります。 ところでmakoto05さんはどういう事情で質問されるのでしょうか。 学生さんが自分で考えもせずに課題の回答を聞いているのであれば正直答えたくないですし、それなりの理由があれば他の質問にも回答しようという気になります。
関連する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が位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。 よろしければこの問題の証明方法を教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- 3次元凸多面体
3次元凸多面体 3次元凸多面体の頂点と辺をグラフとみなしたとき、これが平面的であることを示せ。 また、3次元凸多面体は必ず三角形、四角形あるいは五角形の面を持つことを示せ。 前半は証明の糸口さえ掴めませんでした。ただ、イメージとしては、例えば立方体はある一面から見ると下図のように平面グラフに出来ますよね？ これを一般的な3次元凸多面体について、言葉として証明することができません。 後半では、正多面体については証明出来たつもりです。以下、その証明です。 [証明] (前半が証明済みと仮定して)3次元凸多面体の頂点と辺をグラフとみなし、これの平面グラフGを考える。 Gの頂点数をn、辺数をe、面数をf、各頂点の次数をd、各面がk本の辺を境界に持っているとする。 k=3または4または5であることを示せばよい。 次数の総和=辺数*2 ⇔nd=2e …(1) また、 kf=2e …(2) オイラーの公式より、 2=n-e+f =2e/d - e +2e/k (∵(1)(2)) ⇔1/d + 1/k = 1/2 + 1/m …(3) 式(3)より、明らかにmin(d,k)=3である。 d=3のとき、1/k - 1/6 = 1/m >0よりk=3,4,5 このように証明しましたが、一般の場合にはどうしたらいいでしょうか。どなたか教えてください。
- ベストアンサー
- 数学・算数
- オイラーの公式？初等整数理論？ 教えてください
条件φ(n)=(1/3)nを満たす自然数を求めよ． ヒント？： オイラーの公式 nの素因数分解をn=p1^(e1) p2^(e2) ・・・ pk^(ek)とする 出来れば解法もお願いします
- 締切済み
- 数学・算数
お礼
ご丁寧にどうもありがとうございましたm(__)m 自分は学生でこの冬に何十という数のレポを出されました。その中で、参考文献を調べ、自分で考えても問題の意味や答え方が分からない問題を質問させてもらっています。提出期限が重なったので大量に質問してしまい、誤解を招くようなことをしてしまって申し訳ありませんでしたm(__)m