ベストアンサー

続・グラフ理論

2007/08/23 22:51

Gを頂点数ｎ、変数ｍの単純グラフとし、PG(k)をGの彩色多項式をし、PG(k)のk^n-1の係数が－ｍであることを示せ。という問題で・任意の辺 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 まで出来たんですがk^n-1の係数が－ｍであることをどうやって示せばいいのでしょうか？再度すみません

zunnoyasu
お礼率82% (14/17)

数学・算数
回答数1
ありがとう数1

みんなの回答 （1）
専門家の回答

質問者が選んだベストアンサー

ベストアンサー

Tacosan
ベストアンサー率23% (3656/15482)

2007/08/24 01:51 回答No.1

辺の本数に関する帰納法が一番単純だと思う.

質問者

お礼 2007/08/24 12:58

ありがとうございます。解決しました！！

関連するQ&A

グラフ理論

Gを頂点数ｎ、変数ｍの単純グラフとし、PG(k)をGの彩色多項式をし、PG(k)のk^n-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が三角形を持たない単純平面的グラフとすると、Gが４－彩色可能であることを帰納法を用いて証明するんですけど、「ｍ≦２ｎ－４」と「次数３以下の頂点がある」の二つで帰納法のやり方を教えてください。
グラフ理論の問題について

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は非平面的グラフである。〔５〕平面的グラフは５-彩色可能である。
グラフ理論の問題についての質問です

大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題：グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。よろしければこの問題の証明方法を教えてください。よろしくお願いします。
グラフ理論（幾何学）

グラフ理論で分からない問題が・・・。Ｇは多面体（多面体グラフ）として、そのすべての面の境界は五角形または六角形であるとする。この時、（１）オイラーの公式を用いて、Ｇには１２個以上の五角形の面がなければならないことを示せ。（２）さらに、各頂点ではちょうど３つの面が会うとすると、Ｇにはちょうど１２個の五角形の面があることを示せ。ちなみにオイラーの公式とは点の数ｎ、辺数ｍ、面の数ｆとするとき、ｎ－ｍ＋ｆ＝２となる。なんですが、教えてください、お願いしますm(__)m
確率、グラフ理論(?)の質問です。

以下の問題に途中まででもよいのでご回答よろしくお願いします。少し間違っててもよいのでアドバイスをお願いします。解答してみましたが、 I．１．平均：0 分散：2/3*n ２．e(k) = 10/3*e(k - 1) + 10/3*e(k + 1) ３．(不明) II．１．(解答できました) ２．(不明) ３．(不明) という状況です。整合の方お願いします。 I．１つの粒子が数直線に沿って運動している。粒子は原点０から出発し、毎ステップごとに、等確率1/3でランダムに、-1または０または+1だけ移動する。以下の問いに答えよ。１．ｎステップ後の粒子の位置の平均および分散を求めよ。ｎは正の整数とする。２．Ｌを正の整数とする。粒子は数直線上の-Lまたは+Lに到着すると運動を終了する。粒子がｋに位置するとき、運動を終了するまでに要するステップ数の期待値をe(k)と表す。ただし、ｋは、-L<k<Lを満たす整数であるとする。e(k),e(k-1),e(k+1)の間に成り立つ差分方程式を示せ。３．前問で求めた差分方程式の解はｋについての２次式で表される。e(k)を求めよ。ただし、終端条件をe(-L) = e(L) = 0とする。 II．すべての異なる頂点が辺で繋がっているグラフを完全グラフと呼び、頂点数がｎの完全グラフをKnで表す。図６．２と図６．３はそれぞれK5とK6の例である。完全グラフの辺を２通りにラベル付けをする。図６．１に完全グラフK4のラベル付け例を示す。以下では２通りのラベルの辺をそれぞれ実線と点線で表す。このとき次の問いに答えよ。 1. 図 6.1 のラベル付けには，同じラベルの３辺をもつ K3 が含まれない。同様にして，図 6.2 の完全グラフ K5 の辺を２通りにラベル付けして，同じラベルの３辺をもつ K3 が含まれないようにせよ。 2. 「6 人集まれば，互いに知り合いである 3 人組か，互いに見知らぬ 3 人組が必ず存在する」という命題がある。この命題を図6.3 に示した完全グラフ K6 の辺のラベル付けを利用して証明せよ。ただし，一方的に知っているという関係は考えない。 3. 完全グラフ K8 の辺を２通りにラベル付けする。このとき次の２種類の完全グラフを両方とも含まないようなラベル付けの例を示せ。 - 全ての辺が実線である完全グラフ K3 - 全ての辺が点線である完全グラフ K4
グラフ理論の問題

ちょっとした定理なのですが… Vを頂点集合としてKをVの部分集合とする。KがグラフGのクリークをなすための必要十分条件は、V-K がGの補グラフG^の頂点被覆になることである。図で証明は出来るのですが、数式ではキビシい感じなんです。これは一体どうすれば宜しいのでしょうか？
グラフ理論の問題

グラフ理論の問題で分からないものがあります。次の問題の答えがわかる方は、解答を教えてください。単純グラフG＝(V,E)で、分離度ｋ＝１のとき、｜V｜＝ｐ、｜E｜＝ｑであるなら、次の式が成り立つことを証明せよ。　　ｐ－１＜＝ｑ＜＝(１／２)×ｐ×(ｐ－１) よろしくお願いします。
偏微分の計算

xのn次の多項式g(x)でx=0におけるk次の微分係数g^k (0)が、与えられた関数f(x)のk次の微分係数 f^k (0)と同じになるものを求めよ。また、e＾xをx=0の近くで近似するn次の多項式を求めよ。全然わからないので、わかる方教えてくださいm(__)m
３彩色問題について質問です。

下記の問題が解けません。説明をよろしくお願いします。 P=NPとする。３彩色可能グラフがあるとして、有効な３彩色を作れる多項時間アルゴリズムが存在することを示せ。ヒント：P=NPの仮定はグラフが多項時間内で３彩色可能なグラフかどうかを決定できることを示唆する。しかしP=NPの仮定にはこのテストがどのようになされるかしめされていない。大事なのはそのテストが探せるということを証明することである。
不定積分の問題

不定積分の問題です。ｍを自然数とするとき、　　　　　　　　　　　　　　ｎ　　　　　　 (1)∫(cosx)^(2m-1)dx＝Σa(k)(sinx)^k+C　　　　　　　　　　　　　　　k=1 (Cは積分定数）　（a(k)のｋは添え字です。）を満たす自然数ｎおよび実数a(k)（k=1,2,…,n)を求めよ。 (2)f(t)を多項式とするとき、 ∫f(cosx)dx－∫f(－cosx)dx＝g(sinx)+C (Cは積分定数）を満たす多項式ｇ(t)が存在することを示せ。という問題です。（１）はｎ＝２ｍ－１　　　　a(k)＝０（ｋ＝2.4.…ｎ－１）　　　　　　　（ｋ＝1,3,…ｎ）のときは式が複雑なので記載するのは控えます。分からないのは（２）で解答には　　　　ｎ f(t)＝Σb(k)t^k とおけるので、ｎ＝２L－１とおくと　　　k=0 　　　　　　 L f(t)-f(-ｔ）=Σ２ｂ(2m-1)t^(2m-1) 　　　　　m=1 となっているんですが、なぜｎ＝２L－１とおくのか、f(t)-f(-ｔ）の右辺のΣのｍが１→L　なのかがわかりません。宜しくお願いします。
ハミルトングラフ

ハミルトングラフになるときって、頂点がn個で、任意の二つの点ｖ,ｗ隣接してないとき deg(v)+deg(w)≧n なんで、つまり頂点ｖとｗの次数の合計がn以上なら、成り立つんですよね？でも閉路グラフＣ6の時って、どの頂点でも２+２≦６になるのにハミルトングラフなんですよね？ハミルトングラフってどんなときになるんですか？
教えてください

“臨界なグラフは連結である。” グラフGが臨界である内容は理解したのですが、連結である事が頭が足りなくて何故そうなるのかはっきりと理解することが出来ません。調べてみると「何故なら、もしグラフGが連結でなければ、頂点を共有しない二つ以上の連結部分グラフに分かれる。この時、Gの彩色数は連結部分グラフの彩色数のうち最大のものであり、その他の連結部分グラフから辺や点を除いても彩色数には影響しないから。」 http://www.iis.it-hiroshima.ac.jp/~ohkawa/www32.ocn.ne.jp/~graph_puzzle/1no10.htm 引用とあったのですがこの内容を教えてください。そのままなのかもしれないのですが理解がいまいち出来なくて…。
グラフ理論の頂点に関する性質についての証明

全ての２頂点　v1,v2∈Gについて、ある一つの頂点ｗ∈Gが存在しｖ1とｗは隣接していて、かつ、v2とｗも隣接しているようなグラフGを考える。このとき・・・（a)ｖ∈Gとｗが非隣接ならばδ(ｖ）＝δ(ｗ）を証明せよ（b）ある頂点の次数ｋ＞１かつどの頂点にも隣接しているような頂点は一つもない時、すべての頂点の次数はｋになることを証明せよの２問について証明の仕方を教えていただけると助かります。問題の状況がそもそもわかりません・・・（δはその頂点から出ている辺の数）もとの問題が英文なのでそっちも載せておきます。 Let G be a graph. Suppose that for every pair of distinct vertices v1 and v2 in G, there is a unique vertex w in G such that v1 and w are adjacent and v2 and w are adjacent. (a) Prove that if v and w are nonadjacent vertices in G , then δ(v)＝δ(w). (b) Prove that if there is a vertex of degree k>1 and no vertex is adjacent to all other vertices, then the degree of every vertex is k.
高校数学の数列の証明問題です　4-4

n個の等式(k+1)^2-k^2=2k+1(k=1,2,...,n)の左辺、右辺をそれぞれ加え合わせることにより、 (n+1)^2-1=2Σ[k=1→n]k+nがえられ、これから、Σ[k=1→n]k=1/2・n^2+n/2が導かれるこの方法を一般化してΣ[k=1→n]k^p(pは自然数)はnのp+1次の多項式として表されることかを、pに関する数学的帰納法を用いて示し、またそのときのn^(p+1)とn^pの係数を求めよ解説はΣ[k=1→n]k^pはｎのp+1次式でΣ[k=1→n]k^pは、nのp+1次式でΣ[k=1→n]k^p=1/(p+1)・n^(p+1) +1/2・n^p+...(*)という命題は、p=1のとき問題文により真である、つぎに2項定理により、自然数m(>=2)について(k+1)^(m+1)-k^(m+1)=m+1C1・k^m+m+1C2・k^(m-1)+...となるが、このkに1,2,,,,nを代入した式を辺ごとに加えることによって、(n+1)^(m+1)-1=m+1C1・Σ[k=1→n]k^m+m+1C2Σ[k=1→n]k^(m-1)+～となる　ここで、p<=m-1のとき(*)が真であると仮定すると～の部分はm-1次以下であるから Σ[k=1→n]k^mのm次以上の部分は(1/m+1C1)・{(n+1)^(m+1)-m+1C2Σ[k=1→n]k^(m-1)} のm次以上の部分に等しく、この式のm次以上の部分は2項定理および帰納法の仮定により {1/(m+1)}・｛n^(m+1)+(m+1)n^m-(m+1)m/2・n^m/m}=1/(m+1)・n^(m+1)+n^m/2 よって (*)はp=mのときも真である、したがって(*)はつねに真であるとあるのですが最初のΣ[k=1→n]k^pはｎのp+1次式とあるのですが、これはp次式じゃないですか？p乗なわけですし Σ[k=1→n]k^p=1/(p+1)・n^(p+1)+1/2・n^p+...(*)この式はどこから出てきたのですか？自然数m(>=2)について(k+1)^(m+1)-k^(m+1)=m+1C1・k^m+m+1C2・k^(m-1)+...となるとありますが何故 m>=2から始めるのですか1からじゃ駄目なんですか？ (n+1)^(m+1)-1=m+1C1・Σ[k=1→n]k^m+m+1C2Σ[k=1→n]k^(m-1)+～この式が何故等号で同じになるのか分かりません、それとこの式をp<=m-1の時で考えるのが分かりません Σ[k=1→n]k^mはm-1次以下とあるのですが、m次以下じゃないですか？m乗ですし、m次以上の部分が(1/m+1C1)・{(n+1)^(m+1)-m+1C2Σ[k=1→n]k^(m-1)}のm次以上の部分に等しいというのが良く分かりません、m次以上の部分が {1/(m+1)}・｛n^(m+1)+(m+1)n^m-(m+1)m/2・n^m/m}=1/(m+1)・n^(m+1)+n^m/2となるのも良く分かりません　と殆ど良く分からないですが、是非宜しくお願いします
問題集に載っていた問題が解けません・・・

[x_0,x_n]内で少なくともn階微分可能な関数f(x)と、n次の多項式P_n(x)が、点x_i（i=0,1,・・・,n）で交わっているとき、多項式P_n(x)のn次の項の係数をC_nとすると　f^n (k) = n! C_n　ただし x_0 < k < x_n を満たす定数kが存在することを示せ。という問題を解いています。ロルの定理を使うのかなぁと思い次のような方針で解を得ました。（得た気になってました）関数g(x)を　g(x) = f(x) - P_n(x) と置く。これをxでn階微分すれば　g^n (x) = f^n (x) - n! C_n となる。 f^n (k) が[x_0,x_n]内で微分可能ならg^n (x)も同様。またx_iでfとPは交わっていることから　f(x_i) = P(x_i) つまり　g(x_i) = f(x_i) - P(x_i) = 0 つまり　g(x_0) = g(x_1) = … = g(x_i) = 0 これより[x_0,x_n]内でg(x)にロルの定理を適用すれば　g'(k) = f'(k) - P_n'(k) = 0　・・・（Ｉ）を満たすkが存在する。これをn-1階微分すると　g^n (k) = f^n (k) - n! C_n = 0　・・・（ＩＩ）したがって　f^n (k) = n! C_n とやったんですが、「点x_i（i=0,1,・・・,n）で交わっているとき」を全く使ってないですし、（Ｉ）→（ＩＩ）の変形が間違っている気がします（kの関数をxで微分している・・・）。なにかヒントや方針などお教え頂けないでしょうか。よろしくお願いします。
和訳に関する質問です

和訳に関する質問です私の訳はこうですｎ頂点を持つGの様なグラフのトポロジー指標は異なるやり方での合計でグラフを全ての辺と確実にｋ辺をもつ互いに素な部分グラフに分割できます。ただしk≧0です。文法、訳す単語の順番は大丈夫でしょうか？ The topological index of such a graph G with n vertices is the total number of different ways the graph can be partitioned into disjoint subgraphs containing all vertices and exactly k edges, where k≧0.
gnuplotでグラフをだしたいのですがわからないです。

以下は二項分布のC言語プログラミングソースです。 #include<stdio.h> #include<stdlib.c> #include<math.h> void error(char *s) { printf("%s\n", s); } int main() { int k,m; double u,q,s,t; printf("m,u?"); scanf("%d%lf", &n,&u); q = 1 - p; s = t =pow(q, m); if (s == 0) error("mかu が大きすぎます。"); for (k = 0;k <m; k++) { printf("%4d %7.4f\n",k,s); t *= (m - k) * u / ((k + 1)*q); s += t; } printf("%4d %7.4f\n",m,s); return EXIT_SUCCESS; } この実行結果で出た数値をグラフ化をしたいのです。折線グラフでも、曲線グラフでも構わないので、おしえていただけないでしょうか???

続・グラフ理論

質問者が選んだベストアンサー

お礼 2007/08/24 12:58

関連するQ&A

グラフ理論

n角形の頂点をt色以下で塗り分けるグラフ彩色

グラフ理論

グラフ理論の問題について

グラフ理論について

グラフ理論の問題についての質問です

グラフ理論（幾何学）

確率、グラフ理論(?)の質問です。

グラフ理論の問題

グラフ理論の問題

偏微分の計算

３彩色問題について質問です。

不定積分の問題

ハミルトングラフ

教えてください

グラフ理論の頂点に関する性質についての証明

高校数学の数列の証明問題です　4-4

問題集に載っていた問題が解けません・・・

和訳に関する質問です

gnuplotでグラフをだしたいのですがわからないです。

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

続・グラフ理論

質問者が選んだベストアンサー

お礼 2007/08/24 12:58

関連するQ&A

グラフ理論

n角形の頂点をt色以下で塗り分けるグラフ彩色

グラフ理論

グラフ理論の問題について

グラフ理論について

グラフ理論の問題についての質問です

グラフ理論（幾何学）

確率、グラフ理論(?)の質問です。

グラフ理論の問題

グラフ理論の問題

偏微分の計算

３彩色問題について質問です。

不定積分の問題

ハミルトングラフ

教えてください

グラフ理論の頂点に関する性質についての証明

高校数学の数列の証明問題です 4-4

問題集に載っていた問題が解けません・・・

和訳に関する質問です

gnuplotでグラフをだしたいのですがわからないです。

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

高校数学の数列の証明問題です　4-4

カテゴリ
一覧

専門家に質問してみよう
専門家登録