二項関係とグラフ

"transitive disclosure"（推移閉包）について調べていたら、グラフは二項関係の宝庫だなーと思ったのでメモしておく。

例えば、グラフの頂点集合Vについて二項関係R1を頂点間に辺があると定義する。

例えば上のグラフだと、R1 = {(1,4),(1,6),(2,3), (2,4), (3,2), (3,5), (3,6), (4,1), (4,2), (4,5), (5,3), (5,4), (6,1), (6,3)}である。ここで、集合と順序対の表記の違いについて書いておく。集合は、{}で書かれる。順序対は()で書かれる。集合の場合は、要素の順序や重複は関係ない。つまり、{1,2,3}は、{3,2,1}と同じであり、{1,3,5}は、{1,1,3,3,3,5,5}と同じである。これに対しては、順序対は要素の順序、重複ともに意味がある。

さて、二項関係には特徴的な法則がいくつかある。（詳細はこちら）

• Reflexivity
• Symmetricity
• Anti-Symmetricity
• Transitivity

これらの法則は満たされる場合もあるが、満たされない場合もある。例えば、上記のR1の場合。Symmetricityが満たされる。頂点(v, w)間に枝がある場合は、頂点(w, v)間にも枝がある。無効グラフなので当然である。

次に、以下の有向グラフを考える。

頂点vからwに有向枝が存在するという二項関係をR2と定義する。R2 = {(1,2), (2,3),(3,4)}である。このR2はtransitivity（x R y ⋀ y R z →　x R z）を満たしていない。しかし、(1, 3), (2, 4), (1, 4)の3つの順序対をR2に追加すると、これはtransitivityを満たす。

このように、二項関係Rに要素を追加してある特性pが満たされるようになった場合、この拡張された集合R'をRの特性pに対する閉包と呼ぶ。但し、R'を閉包と呼ぶためには、拡張される要素集合R' - Rは最小である必要がある。

上の例だと、R2がtransitivityを満たすようにするには、最低でもV = {(1, 3), (2, 4), (1, 4)}を追加しないといけないので、R3 := R2 ∨ VはR2の推移閉包であると言える。さてこのR3は(v, w)間に有効路が存在する（v -> wに到達可能）であるという関係になっている。

プログラミング上では、R2はグラフの隣接行列で表される。R3はR2からWarshall-Floydで出すことができる。

const int N = 128;   // number of  verticies
bool conn[N][N];
void transitive_disclosure() {
    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                conn[i][j] |= conn[i][k] && conn[k][j];
}

この推移閉包には、おもしろい性質がある。ある二項関係Rの推移閉包は以下のように表さる。

transitive disclosure(R) = R^1 ∨ R^2 ∨ R^3 …

ここで、R^1 = R、R^{i+1} = R^i ◦ Rです。この◦は、compositionの記号で、Haskellとかでやるfunction compositionと同様のものです。二項関係におけるcompositionはここに定義されているとおり。Warshall-Floydのアルゴリズムもよく考えるとこの性質を使っている。