木とアルカンの構造異性体 - Red cat の数学よもやま話

もう一つ、グラフ理論ネタにお付き合いを。
連結で、閉路を持たないグラフを木(tree)と言います。
あるグラフが木かどうかを判定する方法はいくつか知られていますが、その一つに「連結かつ辺の数が (頂点の個数) - 1」というものがあります。
さて、分子式 ${\rm C}_n{\rm H}_{2n+2}$ で表される有機化合物(アルカン)を考えます。これの分子構造は、一種のグラフとみなせます。すなわち、C (炭素原子)に対応するのが次数 4 の頂点、H (水素原子)に対応するのが次数 1 の頂点です。このグラフは頂点の個数が
$n+(2n+2)=3n+2$ (個)
で、握手補題を使うと、辺の数は
$\frac12\{4n+(2n+2)\}=3n+1$ (個)
ですから、上記の事実より、 ${\rm C}_n{\rm H}_{2n+2}$ に対応するグラフは木になることが分かります。
すると、同じ分子式 ${\rm C}_n{\rm H}_{2n+2}$ を持つアルカンの構造異性体を、具体的に数え上げる方法が作れます。それはズバリ「n 個の頂点を持つ木を全て列挙する」です。つまり、炭素原子に対応する頂点だけを考えて木を作り、そこに、C に対応する頂点の次数が 4 になるように、H に対応する頂点、及び辺を付け加えれば良いのです。興味のある方は、実際に ${\rm C}_4{\rm H}_{10},{\rm C}_5{\rm H}_{12},{\rm C}_6{\rm H}_{14}$ で表される分子の構造異性体を列挙してみてください。
ちなみに、O (酸素原子)に対応する頂点の次数は 2 なので、アルコール ${\rm C}_n{\rm H}_{2n+1}{\rm OH}$ も、対応するグラフはやはり木になります。
前回までの「一筆書き問題」もこの問題も、かなり古くから研究され、結果がわかっているもので、グラフ理論の応用としては初歩的なものです。グラフ理論はこの他にも様々な問題に応用されています。興味を持たれた方は、ぜひ、前回挙げた参考書を手にとってみてください。