推移閉包のソースを表示

{{Expand English|Transitive closure|date=2024年5月}}
'''推移閉包'''（すいいへいほう、{{lang-en-short|transitive closure}}）は、[[集合]] ''X'' における[[二項関係]] ''R'' に対して、''R'' を含む ''X'' 上の最小の[[推移関係]] ''R''{{sup|+}} を意味する{{sfn|守屋|1997|p=7}}。

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

== 解説 ==
任意の関係 ''R'' について、''R'' の推移閉包は常に存在する。これを示すため、任意の推移関係の[[族 (数学)|族]]の[[共通部分 (数学)|共通部分]]が推移的であることに注意する。さらに少なくとも1つの自明な ''R'' を含む推移関係 ''X'' &times; ''X'' が存在する。''R'' の推移閉包は、''R'' を含む全ての推移関係の共通部分である。

推移閉包はより構成的に次のようにも記述できる。''X'' 上の関係 ''R''{{sup|+}} を ''xR{{sup|+}}y'' となるのが ''X'' の要素の有限[[列 (数学)|列]] (''x''{{sub|0}}, &hellip;, ''x''{{sub|''n''}}) （ただし ''n'' &ge; 1）が存在し、2条件
* ''x'' = ''x''{{sub|0}}, ''y'' = ''x''{{sub|''n''}} かつ
* ''x''<sub>0</sub>''Rx''<sub>1</sub>, ''x''<sub>1</sub>''Rx''<sub>2</sub>, &hellip;, ''x''<sub>''n''&minus;1</sub>''Rx''<sub>''n''</sub>
を満たすことと定義する。これは[[関係の合成]]を ''R{{sup|n}}'' のように表すことにすれば<ref>つまり ''R''{{sup|1}} = ''R'' かつ ''R''{{sup|''n'' + 1}} = { (''x'', ''y'') &isin; ''X'' &times; ''X'' | &exist;z &isin; ''X'', (''x'', ''z'') &isin; ''R'' &and; (''z'', ''y'') &isin; ''R{{sup|n}}'' } </ref>、端的に
:<math>R^+ = \bigcup_{n \ge 1} R^n</math>
と書き下すこともできる。関係 ''R''{{sup|+}} が ''R'' を含み、かつ推移的であるかどうかを調べるのは容易である。さらに、''R'' を含む任意の推移関係は ''R''{{sup|+}} も含むので、''R''{{sup|+}} は ''R'' の推移閉包である{{sfn|守屋 |1997|p=8|loc=定理1.2}}。

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

== アルゴリズム ==
グラフの推移閉包を計算する効率的アルゴリズムが[http://www.cs.hut.fi/~enu/thesis.html こちら]にある。最も単純な技法としては[[ワーシャル-フロイド法]]がある。

== 脚注 ==
{{reflist}}

== 参考文献 ==
* {{cite book
    |和書
    |last1              = 守屋
    |first1             = 悦朗
    |year               = 1997
    |title              = チューリングマシンと計算量の理論
    |series             = 情報数理シリーズ
    |publisher          = [[培風館]]
    |isbn               = 4-563-01492-3
    |ref                = harv
}}

{{DEFAULTSORT:すいいへいほう}}
[[Category:二項関係]]
[[Category:グラフアルゴリズム]]
[[Category:閉包作用素]]
[[Category:数学に関する記事]]