【２】木グラフ

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

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

　　　　・

　　　　｜

　　・−・−・

　　　／　＼

　　・　　　・

も可能となる．

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

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

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

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

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

　　ｖ＝ｅ＋１

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

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

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

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

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

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　このように同等でない木の総数はきれいで簡単な式で表現できる．ところが残念なことに位数ｋの同形でない木の総数ｇ（ｋ）を与える公式は知られていないという．

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

　　同等でない木の総数：１，１，３，１６，１２５，１２９６，・・・

　　同型でない木の総数：１，１，１，　２，　　３，　　　６，・・・

そこでせめて下界・上界だけでも求めておきたいと思う．

　位数ｋの同等でない木はｋ^(k-2)個ある．たとえばｋ＝４では各頂点にＡ，Ｂ，Ｃ，Ｄとラベルを付けた場合，同等でない木は１６種類あるというわけである．もし頂点にラベルがなければブタンとイソブタンのように同型の木は２種類あるわけであるから，同型でない木グラフの個数はこれよりもかなり少ない．

　同型になるものは高々ｋ！個である（上の例では４！個の同等でない木が存在するが同型なグラフは２個だけであり，数えすぎであるが・・・）．したがって，同値類の総数は

　　ｋ^(k-2)／ｋ！

以上になるので，ｋ頂点の木グラフで同型でないものの総数もこの値以上になる．

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