State Complex
もともとはロボットアームの状態遷移を記述するためのものだったと思われるが、意外と応用がありそうなものに Configuration Space と State Complex と呼ばれる概念がある。グラフの場合に特化して、簡単に要約してみる。
グラフ G があるとする。向きはついていないものとする。
k = 0,1,2,3,... について G の Discrete Configuration Space を以下のように定義する。
- グラフ G の頂点または辺からなる k 個の列
- 辺の端点と、頂点はすべて異なる
たとえば、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)
辺が含まれている個数を次数として複体を定義することができる。
境界作用素は辺に対して、その端点を与えるものとする。
係数は で考える。グラフが向きつきの場合は、向きに応じて符号を与えて、係数を で考えることができる。
この複体を State Complex という。これを図形として実体化したもの(2次元の複体を四角形とするような Cube Complex)を Configuration Space という。この例の場合、四角形が 4 個、線分が 16 個、頂点が 12 個あるような図形になる。下の図の赤い点を張り合わせたような図形である。