【２】木グラフ

　グラフとは点（頂点ｖ）とそれらを結ぶ線（辺ｅ）とからできている１次元図形のことであるが，そのうち，閉路を含まない連結グラフのことを木（グラフ）と呼ぶ．

　炭素の原子値は４であるが，そのような制限を取り除けば，

　　　　・

　　　　｜

　　・−・−・

　　　／　＼

　　・　　　・

も可能となる．

　これも木グラフであるから，同型でない木グラフの総数をｇ（ｋ）とおくと

　　位数　　：１，２，３，４，５，６，　７，　８，　９，　１０，　１１，１２，　　　１３，・・・，ｋ，・・・

　　ｇ（ｋ）：１，１，１，２，３，６，１１，２３，４７，１０６，２３５，５５１，１３０１，・・・，ｇ（ｋ），・・・

となる．ともあれ，制限のついた飽和炭化水素の構造異性体数ｆ（ｋ）よりも木グラフの総数ｇ（ｋ）の数え上げの方がより一般的な問題であると考えられる．そこでｆ（ｋ）を求める代わりにｇ（ｋ）を求めてみることにする．

１８５７年，ケーリーは知り合いの化学者からの依頼でＣkＨ2k+2の構造異性体の数を数えようとしていたときに多くの「木グラフ」の性質を発見した．木の性質のひとつとして，木の頂点数をｖ，辺数をｅとすると

　　ｖ＝ｅ＋１

が成り立つが，これはオイラーの定理：ｖ−ｅ＋ｆ＝１においてｆ＝０としたものである．すなわち，連結でありかつ閉路を含まないという必要十分条件を満たしていて，飽和炭化水素の場合，ｖ＝３ｋ＋２であるからｅ＝３ｋ＋１で与えられるという意味にほかならない．

　位数ｋに対して同等でない木はいくつあるのか？・・・これがケイリーの考えた問題であり，同等でない木の総数を与える公式（ケイリーの公式）が知られている．ケイリーの公式とは「位数ｋの完全グラフのすべての異なる全域木の総数はｋ^(k-2)で与えられる」というものである．

　　位数ｋ　　　　　　：１，２，３，　４，　　５，　　　６，ｋ

　　同等でない木の総数：１，１，３，１６，１２５，１２９６，ｋ^(k-2)

［補］位数ｋのグラフでどの２点も隣接しているとき完全グラフという．正ｋ角形＋すべての対角線をイメージすればよく，ｖ＝ｋ，ｅ＝kＣ2である．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

[1]ｎ個の頂点を持つラベル付き木全体のなす集合の元の個数はn^(n-2)である。木とはサイクルを持たない連結なグラフ、その頂点に相異なる名前が付けられているときラベル付きという。

[2]ｎ個の頂点を持つラベル付き単純グラフ全体のなす集合の元の個数は2^n(n-1)/2である。単純グラフとはループも多重辺も持たないものをいう。

[3]ｎ個の頂点を持つラベル付き連結単純グラフ全体のなす集合の元の個数はlog(Σ(2^n(n-1)/2)/k!・x^k)のベキ」級数展開におけるx^nの係数のn!倍に等しい。連結＝どの２頂点も道で結ぶことができるとき

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝