传递闭包

传递闭包
术语名称	传递闭包
英语名称	transitive closure

传递闭包(transitive closure)是指对集合上的一个二元关系，包含该关系的最小传递关系。

定义

传递闭包
运算名称	传递闭包
运算符号	[math]\displaystyle{ \operatorname{t}() }[/math],[math]\displaystyle{ ^+ }[/math]
Latex	\operatorname{t}(), ^+
运算对象	关系
运算元数	1
运算结果	关系
定义域	[math]\displaystyle{ \mathcal{P}(X\times X) }[/math]
陪域	[math]\displaystyle{ \mathcal{P}(X\times X) }[/math]

对集合 [math]\displaystyle{ X }[/math] 上的二元关系 [math]\displaystyle{ R }[/math] ，定义满足以下条件的所有关系 [math]\displaystyle{ S }[/math]：

• [math]\displaystyle{ S }[/math] 是传递关系；
• [math]\displaystyle{ S \supseteq R }[/math] 。

其中必有一个关系是其他所有关系的子集，称为关系 [math]\displaystyle{ R }[/math] 的传递闭包(transitive closure)，记作 [math]\displaystyle{ \operatorname{t}(R) }[/math] 或 [math]\displaystyle{ R^+ }[/math]。

性质

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

关系
定义属性	前域、后域、定义域 [math]\displaystyle{ \operatorname{dom} }[/math]、值域 [math]\displaystyle{ \operatorname{ran} }[/math]、域 [math]\displaystyle{ \operatorname{fld} }[/math]
特殊关系	空关系 [math]\displaystyle{ \varnothing }[/math]、恒等关系 [math]\displaystyle{ I }[/math]、全关系 [math]\displaystyle{ A\times B }[/math]
二元齐次关系类型	自反、反自反、对称、反对称、传递
运算	集合运算	交 [math]\displaystyle{ \cap }[/math]、并 [math]\displaystyle{ \cup }[/math]、补 [math]\displaystyle{ \bar{\bullet} }[/math]、差 [math]\displaystyle{ \setminus }[/math]
	类映射运算	转置/逆 [math]\displaystyle{ \bullet^\mathrm{T}/\bullet^{-1} }[/math]、复合 [math]\displaystyle{ \circ }[/math]（幂 [math]\displaystyle{ \bullet^n }[/math]）、限制 [math]\displaystyle{ \bullet_{|\bullet} }[/math]
	闭包运算	自反 [math]\displaystyle{ \operatorname{r}() }[/math]/[math]\displaystyle{ \bullet^= }[/math]、对称 [math]\displaystyle{ \operatorname{s}() }[/math]/[math]\displaystyle{ \bullet^\sim }[/math]、传递 [math]\displaystyle{ \operatorname{t}() }[/math]/[math]\displaystyle{ \bullet^+ }[/math]、自反传递 [math]\displaystyle{ \bullet^* }[/math]、等价 [math]\displaystyle{ \bullet^\equiv }[/math]