■筋交い問題と冗長性（その３）
【１】木グラフ
位数ｋに対して同等でない木はいくつあるのか？・・・これがケーリーの考えた問題であり，同等でない木の総数を与える公式（ケーリーの公式）が知られている．ケーリーの公式とは「位数ｋの完全グラフのすべての異なる全域木の総数はｋ^(k-2)で与えられる」というものである．
位数ｋ ：１，２，３， ４， ５， ６，ｋ
同等でない木の総数：１，１，３，１６，１２５，１２９６，ｋ^(k-2)
［補］位数ｋのグラフでどの２点も隣接しているとき完全グラフという．正ｋ角形＋すべての対角線をイメージすればよく，ｖ＝ｋ，ｅ＝kＣ2である．
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
このように同等でない木の総数はきれいで簡単な式で表現できる．ところが残念なことに位数ｋの同形でない木の総数ｇ（ｋ）を与える公式は知られていないという．
位数ｋ ：１，２，３， ４， ５， ６，・・・
同等でない木の総数：１，１，３，１６，１２５，１２９６，・・・
同型でない木の総数：１，１，１， ２， ３， ６，・・・
そこでせめて下界・上界だけでも求めておきたいと思う．
位数ｋの同等でない木はｋ^(k-2)個ある．たとえばｋ＝４では各頂点にＡ，Ｂ，Ｃ，Ｄとラベルを付けた場合，同等でない木は１６種類あるというわけである．もし頂点にラベルがなければブタンとイソブタンのように同型の木は２種類あるわけであるから，同型でない木グラフの個数はこれよりもかなり少ない．
同型になるものは高々ｋ！個である（上の例では４！個の同等でない木が存在するが同型なグラフは２個だけであり，数えすぎであるが・・・）．したがって，同値類の総数は
ｋ^(k-2)／ｋ！
以上になるので，ｋ頂点の木グラフで同型でないものの総数もこの値以上になる．
下界の漸近挙動を調べるために，スターリングの公式
ｋ！〜（２π）^(1/2)ｋ^(k+1/2)ｅｘｐ（−ｋ）
を用いると
ｋ^(k-2)／ｋ！〜（２π）^(-1/2)ｋ^(-2-1/2)ｅｘｐ（ｋ）
となって，ｋが大きいときはほぼ指数関数的ｅｘｐ（ｋ）に増加することが理解される．
なお，ｋ＞１に対して，不等式
ｅ（ｋ／ｅ）^k≦ｋ！≦ｅｋ（ｋ／ｅ）^k
が成り立つから
ｋ^(k-2)／ｋ！≧ｅｘｐ（ｋ−１）／ｋ^3
となって，下界は少なくともｅｘｐ（ｋ−１）／ｋ^3である．
また，上界については，同型でないｋ頂点の木グラフは高々４^kしかないことが証明できて，以上のことをまとめると
ｅｘｐ（ｋ−１）／ｋ^3≦ｇ（ｋ）≦４^k
となることがわかるのである．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】一般のグラフ
ここでは木グラフの場合も含んで一般のグラフについて考えることにする．すなわち閉路を含んでもよいし連結でなくてもよいものとする．
ｖ＝ｋの場合，異なるグラフの総数は２^(kC2)であるが，同形でないグラフの個数はこれよりもかなり少ない．たとえばｋ＝３のときは８個のグラフがあるが，同型でないものは４つしかない．ｋ＝４の同型でないグラフの個数は１１個である．
位数ｋ ：１，２，３， ４，・・・
同等でないグラフの総数：１，２，８，６４，・・・
同型でないグラフの総数：１，２，４，１１，・・・
前節と同様の議論により，同値類の総数は
２^(kC2)／ｋ！
以上になるので，ｋ頂点のグラフで同型でないものの総数もこの値以上になる．
ｌｏｇ（２^(kC2)／ｋ！）＝kＣ2−ｌｏｇｋ！
≧ｋ^2／２−ｋ／２−ｋｌｏｇｋ
＝ｋ^2／２（１−１／ｋ−２ｌｏｇｋ／ｋ）
ｋが大きいときｌｏｇ（２^(kC2)／ｋ！）はｋ^2／２とほぼ同じ振る舞いをすることがわかる（この相対誤差はｋ→∞のとき０に収束する）．すなわち，ｋ頂点の同型でないグラフの総数はｅｘｐ（ｋ^2）のオーダーで増加し，たとえば２^kよりもずっと大きいことがわかる．また，２^(kC2)に較べそれほどゆっくり増加するわけでもないこともわかるだろう．
これは漸近評価であるが，グラフの正確で実用的な数え上げに関しては，ポリアが化学者から高分子の異性体がいくつあるかを求めることを依頼されて，有名なポリアの数え上げ理論を発見している．ここではポリアの定理の詳細については記さないが，置換群によってもたらされる同値類の個数（バーンサイドの定理）に基づいて数え上げを行うものである．
群の概念は，代数方程式の解の置換の研究として誕生した歴史をもつが，今日では自然科学の多くの分野に応用され，たとえば，化学における分子構造やタンパク質やＤＮＡの配列の決定に関しても，群論が重要な役割を果たしていることはご存知であろう．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
