雑記: 穴を数える手続き

あなたは以下の図形  X にいくつ穴があるか求めるようお客様に要求されたとします。
灰色の部分は面で埋まっているとします。

f:id:cookie-box:20161204111813p:plain:w160
あなたはこう答えたいです。
 f:id:cookie-box:20161204115026p:plain:w130
だっても何も、図形  X の穴は V_1 V_2 V_3 がなす三角形の1個だからです。
しかし、これではお客様へ要件定義の説明責任を果たせません。というか要件定義していません。
あなたの出した結論が、バグがない、品質のよいものなのかどうか全くわかりません。
また、より複雑な図形になったとき、同じようには対応できないかもしれません。
そこで、再現可能な手続きでもって求め直したいと思います(以下)。

f:id:cookie-box:20161204110733p:plain:w460

  • まず頂点と辺と面を列挙してください。
  • チェイン複体を構成してください。C_0(X) は各頂点に係数を掛けて足したもののなす空間だと思ってください。図形 X には頂点が5つあるので  \mathbb{R}^5 になります。ここで、簡単のため & 今回の目的を満たすのに十分なため、係数のとりうる値は  \mathbb{R} としました。場合によっては \mathbb{Z} とか  \{ 0, 1\} かもしれないので気を付けてください。
    境界作用素 \partial _1 , \; \partial _2 は、「辺の係数空間から頂点の係数空間への写像 \mathbb{R}^6 から  \mathbb{R}^5 への写像)」「面の係数空間から辺の係数空間への写像 \mathbb{R} から  \mathbb{R}^6 への写像)」とでもいうべき写像ですが、ここでは上のように行列表示できるものと定義します。なぜこうしたのかは、何となくわかるかもしれませんが、 \partial _1 の1列目が「辺  V_0 V_1 は頂点  V_0 と頂点  V_1 を境界としてもつ」に対応しています。これはチェイン複体の境界作用素への要請  \partial _n \circ \partial _{n+1} = 0 を満たします。
    ここで便宜上、写像 \partial _1 , \; \partial _2 を行列であるかのように書いています。
  • あとは1次ホモロジーH_1(X) の次元を求めてください。線形代数の基礎知識によります。
    • 剰余群をとる操作は、集合「 Z_1 (X) = 図形 X に含まれる全ての(係数の重み付き)閉じたループ(辺のセット)」の元の中で、集合「 B_1 (X) = 図形 X に含まれる(係数の重み付き)閉じたループであって面で埋まっているもの」の元の差しかないものを同一視することに相当します。H_1(X) の元を数えるとは、全ての閉じた(係数の重み付き)ループをカウントするが、中が面で埋まったループがくっついているかどうかの違いしかない場合は重複してカウントしない、ということになります。H_1(X) の元の数をそのまま見てしまうと各辺に係数の重みを課す分無数にあるので、穴の数をとるには係数空間の次元を取ります。
    • 同様に、{\rm dim}\bigl(H_0(X)\bigr)=1 で連結成分の数、{\rm dim}\bigl(H_2(X)\bigr)=0 で空洞の数も求まる。というより、「図形 X の連結成分の数」「図形 X の穴の数」「図形 X の空洞の数」をこの量で定義した、といった方が正しい。

参考文献