推移閉包
推移閉包（すいいへいほう、英: transitive closure）は、集合 X における二項関係 R に対して、R を含む X 上の最小の推移関係 R+ を意味する[1]。
たとえば X を人間（生死は問わない）の集合とし、「x は y の親である」という関係 xRy を考えると、その推移閉包は「x は y の先祖である」という関係 xR+y である。あるいは X を空港の集合とし、「x から y への直通便が存在する」という関係 xRy を考えると、その推移閉包は「x から y まで一回または複数の航空便で行くことができる」という関係 xR+y である。
Contents
解説
任意の関係 R について、R の推移閉包は常に存在する。これを示すため、任意の推移関係の族の共通部分が推移的であることに注意する。さらに少なくとも1つの自明な R を含む推移関係 X × X が存在する。R の推移閉包は、R を含む全ての推移関係の共通部分である。
推移閉包はより構成的に次のようにも記述できる。X 上の関係 R+ を xR+y となるのが X の要素の有限列 (x0, …, xn) （ただし n ≥ 1）が存在し、2条件
- x = x0, y = xn かつ
- x0Rx1, x1Rx2, …, xn−1Rxn
を満たすことと定義する。これは関係の合成を Rn のように表すことにすれば[2]、端的に
- [math]R^+ = \bigcup_{n \ge 1} R^n[/math]
と書き下すこともできる。関係 R+ が R を含み、かつ推移的であるかどうかを調べるのは容易である。さらに、R を含む任意の推移関係は R+ も含むので、R+ は R の推移閉包である[3]。
計算複雑性との関連
計算複雑性理論において、複雑性クラス NL は一階述語論理に推移閉包を追加した論理で表される論理式と正確に対応している。これは、推移閉包の属性が NL完全な問題である STCON 問題（グラフ内の経路を求める問題）と密接に関係しているためである。同様にクラス Lは、一階述語論理に可換な推移閉包を加えたものである。推移閉包を二階述語論理に加えると、PSPACEが得られる。
アルゴリズム
グラフの推移閉包を計算する効率的アルゴリズムがこちらにある。最も単純な技法としてはワーシャル-フロイド法がある。
脚注
参考文献
- 『チューリングマシンと計算量の理論』 培風館〈情報数理シリーズ〉、1997年。ISBN 4-563-01492-3。