State Complex - tkenichi の日記

f:id:tkenichi:20121124155518j:plain

もともとはロボットアームの状態遷移を記述するためのものだったと思われるが、意外と応用がありそうなものに Configuration Space と State Complex と呼ばれる概念がある。グラフの場合に特化して、簡単に要約してみる。

グラフ G があるとする。向きはついていないものとする。
k = 0,1,2,3,... について G の Discrete Configuration Space $\cal{D}^{k}(G)$ を以下のように定義する。

グラフ G の頂点または辺からなる k 個の列

辺の端点と、頂点はすべて異なる

たとえば、Gとして、下のようなグラフを

f:id:tkenichi:20121216233704p:plain

考えると $\cal{D}^{2}(G)$ は次のようになる。

(e0,e2) (e1,e3) (e2,e0) (e3,e1)

(e0,v2) (e0,v3) (e1,v3) (e1,v0) (e2,v0) (e2,v1) (e3,v1) (e3,v2)

(v2,e0) (v3,e0) (v3,e1) (v0,e1) (v0,e2) (v1,e2) (v1,e3) (v2,e3)

(v0,v1) (v0,v2) (v0,v3) (v1,v0) (v1,v2) (v1,v3) (v2,v0) (v2,v1) (v2,v3) (v2,v0) (v3,v1) (v3,v2)

辺が含まれている個数を次数として複体を定義することができる。

$C_2( \cal{D}^{2}(G) ) = \{ (ei,ej) \}$
$C_1( \cal{D}^{2}(G) ) = \{ (ei,vj), (vi,ej) \}$
$C_0( \cal{D}^{2}(G) ) = \{ (vi,vj) \}$

境界作用素は辺に対して、その端点を与えるものとする。

$\partial : C_{k+1} \to C_k$
$\partial (e0,e2) = (e0,v2) + (e0,v3) + (v0,e2) + (v1,e2)$

係数は $\bf{Z}_2$ で考える。グラフが向きつきの場合は、向きに応じて符号を与えて、係数を $\bf{Z}$ で考えることができる。

この複体を State Complex という。これを図形として実体化したもの（２次元の複体を四角形とするような Cube Complex）を Configuration Space という。この例の場合、四角形が 4 個、線分が 16 個、頂点が 12 個あるような図形になる。下の図の赤い点を張り合わせたような図形である。

f:id:tkenichi:20121217001503p:plain

このホモロジー群は State Complex から計算されるホモロジー群と一致する。