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

[[分类:二元关系]]{{DEFAULTSORT:chuan2di4bi4bao1}}
{{#seo:
|keywords=传递闭包, 闭包运算, 传递关系
|description=本文介绍自反闭包的定义、计算方法及其在二元关系理论中的性质，包括自反闭包与恒等关系的关系及其在各种运算下的行为。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2023-04-26
}}
{{InfoBox
|name=传递闭包
|eng_name=transitive closure
}}
'''传递闭包'''('''transitive closure''')是指对[[集合]]上的一个二元[[关系]]，包含该关系的最小[[传递关系]]。

== 定义 ==

{{Operation
|name=传递闭包
|symbol=<math>\operatorname{t}()</math>,<math>^+</math>
|latex=\operatorname{t}(),^+
|operand=关系
|operand_num=1
|result=关系
|domain=<math>\mathcal{P}(X\times X)</math>
|codomain=<math>\mathcal{P}(X\times X)</math>
}}
对集合 <math>X</math> 上的二元关系 <math>R</math> ，定义满足以下条件的所有关系 <math>S</math>：
* <math>S</math> 是传递关系；
* <math>S \supseteq R</math> 。
其中必有一个关系是其他所有关系的子集，称为关系 <math>R</math> 的'''传递闭包'''('''transitive closure''')，记作 <math>\operatorname{t}(R)</math> 或 <math>R^+</math>。

== 性质 ==

* 基本性质
** 计算： <math>\operatorname{t}(R) = \bigcup_{i=1}^\infty R^i = R \cup R^2 \cup R^3 \cup \dots</math> 。
*** 在有限集合 <math>X</math> 上（<math>\operatorname{card}X = n</math>），由于 <math>n</math> 个顶点的图中任何长度超过 <math>n</math> 的路径必然包含重复顶点，传递闭包可在有限步内计算：<math>\operatorname{t}(R) = \bigcup_{i=1}^n R^i</math> 。
** 传递关系的传递闭包是其自身。
** 传递闭包是包含 <math>R</math> 的最小传递关系。
** 传递闭包是向 <math>R</math> 上添加最少有序对构成的传递关系。
* 运算性质
** 传递闭包运算是[[幂等性（一元运算）|幂等]]的： <math>\operatorname{t}(\operatorname{t}(R)) = \operatorname{t}(R)</math> 。
** 传递闭包运算是[[单调性|单调]]的：如果 <math>R \subseteq S</math> ，则 <math>\operatorname{t}(R) \subseteq \operatorname{t}(S)</math> 。
** 传递闭包与[[并关系|并]]运算的关系： <math>\operatorname{t}(R \cup S) \supseteq \operatorname{t}(R) \cup \operatorname{t}(S)</math> 。
** 传递闭包与[[逆关系]]可交换： <math>\operatorname{t}(R^{-1}) = (\operatorname{t}(R))^{-1}</math> 。
* 与其他闭包运算的关系
** 传递闭包与[[自反闭包]][[可交换]]。
*** 传递闭包和自反闭包复合得到[[自反传递闭包]]： <math>\operatorname{t}(\operatorname{r}(R)) = R^*</math> 。
** 传递闭包与[[对称闭包]]'''不一定'''可交换。
* 特殊关系的传递闭包
** [[空关系]]的传递闭包是其自身： <math>\operatorname{t}(\varnothing) = \varnothing</math> 。
** [[恒等关系]]的传递闭包是其自身： <math>\operatorname{t}(I_X) = I_X</math> 。
** [[全关系]]的传递闭包是其自身： <math>\operatorname{t}(X \times X) = X \times X</math> 。
* 表示
* 关系图
** 传递闭包的关系图中，存在从a到b的边当且仅当在原关系图中存在从a到b的路径
** 传递闭包对应于图的[[可达性]]关系
** 在[[有向图]]中，传递闭包给出了所有顶点对之间的可达性信息
* 关系矩阵
** 传递闭包的关系矩阵可通过 [[Warshall 算法]]计算


{{关系}}