查看“︁传递闭包”︁的源代码

{{About|二元关系的传递闭包|集合的传递闭包|传递集合}} 

{{roughtranslation|time=2017-04-14T19:30:07+00:00}}
[[数学]]中，[[集合 (数学)|集合]]''X''上的[[二元关系]] ''R'' 的'''传递闭包'''是包含''R''的''X''上的最小的[[遞移關係]]。

例如，如果 ''X'' 是由人组成的集合（不论人活着与否）而''R''是关系“为父子”，则 ''R'' 的传递闭包是关系“''x'' 是 ''y'' 的祖先”。再比如，如果 ''X'' 是空港的集合而关系 ''xRy'' 为“从空港 ''x'' 到空港 ''y'' 有直航”，则 ''R'' 的传递闭包是“可能经一次或多次航行从 ''x'' 飞到 ''y''”。

==存在性和描述==

对于任何关系 ''R''，''R'' 的传递闭包总是存在的。传递关系的任何[[家族 (数学)|家族]]的[[交集]]也是传递的。进一步地，至少存在一个包含 ''R'' 的传递关系，也就是平凡的: ''X'' &times; ''X''。''R'' 传递闭包给出自包含 ''R'' 的所有传递关系的交集。

我们可以用更具体术语来描述 ''R'' 的传递闭包如下。定义在 ''X'' 上的一个关系 ''T''，称 ''xTy'' [[当且仅当]]存在[[有限集合|有限]]的元素(''x''<sub>''i''</sub>)[[序列]]，使得 ''x'' = ''x''<sub>0</sub> 并且

:''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> 和 ''x''<sub>''n''</sub>''Ry''
形式上写为
:<math>T = \bigcup_{i \in \omega} R^i</math>
容易检查出关系 ''T'' 是传递的并且包含 ''R''。进一步地，任何包含 ''R'' 的传递关系也包含 ''T''，所以 ''T'' 是 ''R'' 的传递闭包。

==证实 ''T'' 是包含 ''R'' 的最小传递关系==

设 ''A'' 是任何元素的集合。

假定: <math>\exists</math>''G<sub>A</sub>'' 传递关系 ''R<sub>A</sub>''<math>\subseteq</math>''G<sub>A</sub>'' <math>\wedge</math> ''T<sub>A</sub>''<math>\not\subseteq</math>''G<sub>A</sub>''。所以 <math>\exists</math>''(a,b)''<math>\not\in</math>''G<sub>A</sub>''<math>\wedge</math>''(a,b)''<math>\in</math>''T<sub>A</sub>''. 所以，特定的 ''(a,b)''<math>\not\in</math>''R<sub>A</sub>''。

现在通过 ''T'' 的定义，我们知道了 <math>\exists</math>''n''<math>\in \mathbb{N}</math> ''(a,b)''<math>\in</math>''R<sup>n</sup><sub>A</sub>''。接着，<math>\forall</math>''i''<math>\in \mathbb{N}</math>, ''i''<math><</math>''n'' <math>\Rightarrow</math> ''e<sub>i</sub>''<math>\in</math>''A''。所以，有从 ''a'' 到 ''b'' 路径如下: ''aR<sub>A</sub>e<sub>1</sub>R<sub>A</sub>...R<sub>A</sub>e<sub>(n-1)</sub>R<sub>A</sub>b''。

但是，通过 ''G<sub>A</sub>'' 在 ''R<sub>A</sub>'' 上的传递性，<math>\forall</math>''i''<math>\in \mathbb{N}</math>, ''i''<math><</math>''n'' <math>\Rightarrow</math> ''(a,e<sub>i</sub>)''<math>\in</math>''G<sub>A</sub>''，所以，''(a,e<sub>(n-1)</sub>)''<math>\in</math>''G<sub>A</sub>'' <math>\wedge</math> ''(e<sub>(n-1)</sub>,b)''<math>\in</math>''G<sub>A</sub>''，所以通过 ''G<sub>A</sub>'' 的传递性，我们得到了 ''(a,b)''<math>\in</math>''G<sub>A</sub>''。'''矛盾于 ''(a,b)''<math>\not\in</math>''G<sub>A</sub>''。'''

因此，<math>\forall</math>''(a,b)''<math>\in</math>''A''<math>\times</math>''A'', ''(a,b)''<math>\in</math>''T<sub>A</sub>'' <math>\Rightarrow</math> ''(a,b)''<math>\in</math>''G<sub>A</sub>''。这意味着 ''T''<math>\subseteq</math>''G''，对于任何包含 ''R'' 的传递的 ''G''。所以，''T'' 是包含 ''R'' 的'''最小'''传递闭包。

===推论===

如果 ''R'' 是传递的，则 ''R'' = ''T''。

==用途==

注意两个传递关系的[[并集]]不必须是传递的。为了保持传递性，必须采用传递闭包，例如在取两个[[等价关系]]或[[预序]]的并的时候。为了获得新的等价关系或预序，必须选用传递闭包（自反性和对称性在等价关系的情况下是自动的）。

[[有向无环图]](DAG)的传递闭包是 DAG 的[[可到达性]]关系和一个[[严格偏序]]。

== 与复杂性的关系 ==

在[[计算复杂性理论]]中，[[复杂度类]] [[NL (复杂性)|NL]] 严格对应于可使用[[一阶逻辑]]和传递闭包表达的逻辑句子的集合。这是因为传递闭包性质有密切关系于 [[NL-完全]]问题 [[STCON]]，找到在一个图中的[[有向路径]]。类似的，类 [[L (复杂性)|L]] 是一阶逻辑带有交换传递闭包。在向[[二阶逻辑]]增加了传递闭包的时候，我们得到 [[PSPACE]]。

== 有关概念 ==

* 关系 ''R'' 的[[传递简约]]是有 ''R'' 作为它的传递闭包的最小关系。一般来说它不唯一。

== 算法 ==
计算图的传递闭包的有效算法可见于 [http://www.cs.hut.fi/~enu/thesis.html here] {{Wayback|url=http://www.cs.hut.fi/~enu/thesis.html |date=20200321022744 }}。最简单的技术是[[Floyd-Warshall算法]]。

== 引用 ==
* Lidl, R. and Pilz, G., 1998, ''Applied abstract algebra'', 2nd edition, Undergraduate Texts in Mathematics,  Springer, ISBN 0-387-98290-6

== 外部連結 ==

* "[http://www.cs.sunysb.edu/~algorith/files/transitive-closure.shtml Transitive closure and reduction] {{Wayback|url=http://www.cs.sunysb.edu/~algorith/files/transitive-closure.shtml |date=20140723213142 }}", The Stony Brook Algorithm Repository, Steven Skiena  . 

[[Category:数学关系]]
[[Category:闭包算子]]
[[Category:图算法]]