- ベストアンサー
グラフ理論
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
無駄があるかもしれませんが: まず, G を n頂点の空グラフ (辺を持たないグラフ) とすると, P(G, k) = k^n です. 定義から計算してください. で, 次に n頂点のグラフG に対し P(G, k) が k に関する n次多項式で k^n の係数が 1になることを (頂点数と辺の数に関する) 帰納法で示します. 辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k) ですが, 右辺に出てくる G-e, G/e はどちらも G より小さいグラフです. G-e は G と頂点数は同じで, 辺は 1本減っています. また, G/e は G より頂点が 1個少なく, また辺も少なくとも 1本は減っています. だから右辺には帰納法が適用できて P(G-e, k) = k^n + o(k^n), P(G/e, k) = k^(n-1) + o(k^(n-1)) です. つまり P(G, k) も k^n + o(k^n) です. これだけ用意すれば, あとは辺の本数に関する帰納法がまわります.
その他の回答 (2)
- Tacosan
- ベストアンサー率23% (3656/15482)
おっと, ここでは o(k^n) は「k^n より次数の低い項」の意味で使ってます. ちょうど「最高次だけ考えればいい」ところだったので, 最高次以外の項を無視するために使いました.
お礼
ありがとうございました！！ なんとかやってみます！！
- Tacosan
- ベストアンサー率23% (3656/15482)
普段使わないのでちょっと調べたんだけど, 彩色多項式の性質をどこまで使っていいのかなぁ? 卑怯だけど, ・任意の辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k) ・n頂点のグラフ G に対し, P(G, k) は k に関する整数係数 n次多項式かつ k^n の係数は 1 ・P(empty graph, k) = k^n を使っていいなら一瞬ですね. もしくは, 帰納法かなぁ?
お礼
ええと、この前の問題が「P(G, k) = P(G-e, k) - P(G/e, k)となることを示せ」という問題なので、 誘導の意味もあって「任意の辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k)」は使えると思います。他の２つに関してはすみませんが不明です…
補足
あと「任意の辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k)」 だけでも証明は出来るんでしょうか？
関連する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の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。
- ベストアンサー
- 数学・算数
- 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) これがどのように示されるのかがわからないので、どうか教えていただけないでしょうか。
- ベストアンサー
- 数学・算数
- グラフ理論の問題についての質問です
大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題： グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。 よろしければこの問題の証明方法を教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- グラフ理論（幾何学）
グラフ理論で分からない問題が・・・。 Ｇは多面体（多面体グラフ）として、そのすべての面の境界は五角形または六角形であるとする。この時、 （１）オイラーの公式を用いて、Ｇには１２個以上の五角形の面がなければならないことを示せ。 （２）さらに、各頂点ではちょうど３つの面が会うとすると、Ｇにはちょうど１２個の五角形の面があることを示せ。 ちなみにオイラーの公式とは点の数ｎ、辺数ｍ、面の数ｆとするとき、ｎ－ｍ＋ｆ＝２となる。 なんですが、教えてください、お願いしますm(__)m
- ベストアンサー
- 数学・算数
- グラフ理論について教えてください。
n,n,n-1,n-1,n-2,n-2,・・・・2,2,1,1(n:正の整数) というグラフがグラフ的かグラフ的でないかを理由と共に 調べています。 どなたか証明して頂けませんでしょうか？ よろしくお願いいたします。
- 締切済み
- 数学・算数
- グラフ理論の彩色問題
G を3 角形がない単純平面的グラフとする．このとき，G が4-彩色可能であることを示せ． この問題の証明が出来なくて困ってます。 誰かわかりやすく解説お願いします。
- 締切済み
- 数学・算数
お礼
ありがとうございます。 あと「 o(k^n) 」のoとは何を意味しているのでしょうか？