推移閉包

推移閉包（すいいへいほう、英: Transitive closure）は、集合 X における二項関係 R に対して、R を含む X 上の最小の推移関係を意味する。

例えば、X が人間（生死を問わない）の集合、R が親子関係としたとき、R の推移閉包とは「x は y の先祖である」という関係である。あるいは、X が空港の集合、xRy が「空港 x から空港 y への直通便が存在する」ことを意味するとき、R の推移閉包は「x から y まで一回または複数の航空便で行くことができる」という関係である。

解説

任意の関係 R について、R の推移閉包は常に存在する。これを示すため、任意の推移関係の族の積集合が推移的であることに注意する。さらに少なくとも1つの自明な R を含む推移関係 X × X が存在する。R の推移閉包は、R を含む全ての推移関係の積集合である。

R の推移閉包は次のように厳密に記述される。X 上の関係 T を xTy としたとき、x = x₀ であるような要素 (x_i) の有限列が存在し、次が成り立つ。

x₀Rx₁, x₁Rx₂, …, x_n−1Rx_n, かつ x_nRy

形式記述: $R^+ = \bigcup_{i=1,2,..} R^i$

関係 T が R を含み、かつ推移的であるかどうかを調べるのは容易である。さらに、R を含む任意の推移関係は T も含むので、T は R の推移閉包である。

計算複雑性との関連

計算複雑性理論において、複雑性クラス NL は一階述語論理に推移閉包を追加した論理で表される論理式と正確に対応している。これは、推移閉包の属性が NL完全な問題である STCON 問題（グラフ内の経路を求める問題）と密接に関係しているためである。同様にクラス Lは、一階述語論理に可換な推移閉包を加えたものである。推移閉包を二階述語論理に加えると、PSPACEが得られる。

アルゴリズム

グラフの推移閉包を計算する効率的アルゴリズムがこちらにある。最も単純な技法としてはワーシャル-フロイド法がある。