• ベストアンサー

Ｋ_nの全域木の数の証明

Ｋ_nはn点からなるグラフ（図形）で、ある任意の点は自分自身以外の点と辺で結ばれています。つまり各辺の次数がn-1のグラフです。 このグラフの全域木の数は一般的にn^(n-2)個であることが知られているそうなのですが、どう証明すればいいでしょうか。 全域木とは、全ての点を通る「木」のことです。つまり全ての点と点を結びつけつつも閉路が存在しないようなグラフのことをいいます。 どなたか分かる方、よろしくお願いします。

  • arcsin
  • お礼率46% (194/417)

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

  • ベストアンサー
回答No.2

Cayleyの公式の話ですね。 証明は次の本を見て下さい １　グラフ理論入門　　サイエンス社発行 　N．ハーツフィールド G．リンゲル 著 　早稲田大学 教授 鈴木晋一 訳 　　「５章２節　ケーリーの全域木公式」参照 ２　数え上げの手法　　東海大学出版会発行 　　L.ロバース　著 　　成嶋弘、土屋守正　訳 　　「４章１節　Cayleyの公式と木の数え上げ」参照

その他の回答 (1)

  • korochin
  • ベストアンサー率40% (2/5)
回答No.1

直接答えとは関係ないですけど、 >つまり各辺の次数がn-1のグラフです。 は「各点」ではないですか？ 次数とは、ひとつの点にn-1本の辺があるということですよね？

arcsin
質問者

お礼

すいません。おっしゃるとおりです＾＾；

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 最小全域木について

    　現在、最小全域木の問題はグラフ理論や遺伝的アルゴリズムの文献など様々な分野で解説されていますが、この「最小全域木」について気になることがあります。 最小全域木とは辺に対して一つの重みがあるものですが、この重みが多重化すること、つまり一つの辺に対して二つ以上の重みが存在する最小全域木とは存在しないのでしょうか？？ つまりは「二重の重みを持つグラフ」を対象とした研究とは世の中では行われていないのでしょうか？？ 厳密な解を求めるのが不可能など、様々な問題が生じてくるから不可能なのかなと思ったりしたのですが、、、違うのでしょうか？？ もし、この分野に詳しい方がいらっしゃったら返事をお願いしたいです。

  • グラフ理論（木について）の証明

    2点以上の点からなる木は、2部グラフであることを数学的帰納法を用いて証明するには、どのようにしたらよいのでしょうか？ ※使っても良い事実として、「2点以上の点からなる木では葉が存在する」というものがあります。 点の個数が2のときは明らかであることは分かるのですが、その後どのようにしたらよいのかが分かりません。 （もし、点の個数を使うときはn，辺の個数はeを用いて教えてください） よろしくお願いします。

  • e^x > Σ[k=0→n](x^k/k !) の証明です。

    e^x > Σ[k=0→n](x^k/k !) の証明です。 「x>0のとき、任意のn∈Nに対して、e^x>Σ[k=0→n]x^k/k !が成り立つことをTaylorの定理を用いずに示せ。」という問題です。Taylorの定理を使わない場合、どのように証明すればよろしいのでしょうか？ 宜しくお願い致します。

  • グラフの証明を教えてください

    背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをＧとします Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。 そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき Ｈの各頂点の次数は偶数である。 この証明を教えてください。

  • nが整数のとき,　2n^3+3n^2+n　は6の倍数であることを証明せ

    nが整数のとき,　2n^3+3n^2+n　は6の倍数であることを証明せよ。 上の解き方は,n(n+1)(2n+1)に因数分解し, 2の倍数かつ3の倍数であることを証明すればよいと思うのですが, 教科書には, 2の倍数であるというのは,n(n+1)が連続する2つの整数の積だから証明でき, 3の倍数であるというのは,　kを整数として 　n=3kのとき,n=3k+1のとき,n=3k+2のときに3×○の形にすれば証明できるとありました。 ここで質問なのですが, なぜ,n=3k　n=3k+1　n=3k+2　にするのでしょうか？ n=k　n=k+1　n=k+2　ではなぜ駄目なのか教えていただけませんか？ 　

  • グラフが木であるとき、この定義があります。点の個数ｎ　　枝の個数ｍ　　

    グラフが木であるとき、この定義があります。点の個数ｎ　　枝の個数ｍ　　そして　ｍ＝ｎ－１ 　この詳しい証明過程を教えていただけないでしょうか

  • Σk^2の証明

    Σk^2=n/6*(n+1)*(2n+1) の証明の途中で 1/6*n*(n+1)*(2*n+1)*(n+1)2 =1/6*(n+1)[n*(2n+1)+6(n+1)] という一節が出てくるのですが、この計算分かりません。 どうやってこの形にするのか、教えていただけないでしょうか？ よろしくお願いします。m(__)m

  • Σ(k^2)の証明

    学校の数学の教科書や、いろんなネット上のページでは、恒等式k^3-(k-1)^3=3k^3-3k+1を使って、 Σ(k^2)=1/6n(n+1)(2n+1)の公式を証明してます。しかし、k^3-(k-1)^3=3k^3-3k+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は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。

  • {9^(n+1)-8n-9}/64になる証明

    {9^(n+1)-8n-9}　(n=正の整数) という数字が64で割れることを二項定理を使って証明したいのですが、分かりません。 自分でやってみたところ、 (1+8)^n=…… ↓ 9^n-8n-1=64k ↓ 9^(n+1)-8n*9-9=64k*9 というところまで、できましたが次何すればいいのかわかりません。 回答お願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する