Javaアプレット(56) オイラーの公式

石の死活を考えるときの石の部分集合に群という概念があります。同じ色の石が縦横に接続したものを連と呼びますが、連同士がつながった集合を群といいます。群が死活を判定する単位になります。
ある群の死活を考える上で、まず単純にその群が眼を2つ以上持っていれば無条件に活きです。そこで群の眼を数えることが死活計算の第一歩になるのですが、かの有名な数学者オイラーが発見した頂点と辺と面（領域）の数の関係を示したオイラーの公式が群の眼の数を数えるのに役立つのです。
オイラーの公式とは頂点 (vertex) の数 v 、辺 (edge) の数 e と面 (region) の数 r の間に、
　v – e + r = 2
という関係が成り立つというものです。 面の数を求めるように変形すると、
　r = e – v + 2
となります。例えば3路盤の格子の場合、頂点の数 v = 9 、辺の数 e = 12 なので、面の数は、
　r = e – v + 2 = 12 – 9 + 2 = 5
になります。これは格子のマス目が4つと外側の領域を合わせて5ということです。つまり、外側の領域を除けば、
　r = e – v + 1
が成り立ちます。これを群の眼を数えることに応用するとどうなるでしょうか。下図の局面を例に考えてみましょう。

【図79 ある局面】
この局面の左上の白石の群を考えてみます。この群をグラフとして表現したのが下図です。

【図80 群のグラフ表現】
この図では頂点の数 v = 7 、辺の数 e = 9 なので、面の数は、
　r = e – v + 1 = 9 – 7 + 1 = 3
になります。これがこの群が囲っている閉領域の数になります。
それにしても、オイラーの公式は不思議な公式です。頂点の数と辺の数で面の数が決まってしまうわけですから、同じ数の頂点と辺をどうつないでも面の数は変わらないということになります。ということは同じ頂点の数であれば、辺の数を増やしたほうが面の数が増えるということ。図79の白14手目の隅に打った手は頂点 +1 に対し、辺を +2 にできたために面を +1 できたことになります。
この原理をBWモデルに当てはめたのが、別ページの式になります。また、今回これらの式をプログラムにしました。GraphGo_0_16 として公開します。この中の NumericAnalysis.java で上記局面の計算を実際に行っています。
ただし死活の計算自体にはまだ反映していません。もう少し他の論文も読んでみようと思います。
（つづく）