传递闭包

  此條目介紹的是二元关系的传递闭包。关于集合的传递闭包，请见「传递集合」。

数学中，集合X上的二元关系 R 的传递闭包是包含R的X上的最小的遞移關係。

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

存在性和描述

对于任何关系 R，R 的传递闭包总是存在的。传递关系的任何家族的交集也是传递的。进一步地，至少存在一个包含 R 的传递关系，也就是平凡的: X × X。R 传递闭包给出自包含 R 的所有传递关系的交集。

我们可以用更具体术语来描述 R 的传递闭包如下。定义在 X 上的一个关系 T，称 xTy 当且仅当存在有限的元素(x_i)序列，使得 x = x₀ 并且

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

形式上写为

${\displaystyle T=\bigcup _{i\in \omega }R^{i}}$ 

容易检查出关系 T 是传递的并且包含 R。进一步地，任何包含 R 的传递关系也包含 T，所以 T 是 R 的传递闭包。

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

设 A 是任何元素的集合。

假定: ${\displaystyle \exists }$ G_A 传递关系 R_A${\displaystyle \subseteq }$ G_A ${\displaystyle \wedge }$  T_A${\displaystyle \not \subseteq }$ G_A。所以 ${\displaystyle \exists }$ (a,b)${\displaystyle \not \in }$ G_A${\displaystyle \wedge }$ (a,b)${\displaystyle \in }$ T_A. 所以，特定的 (a,b)${\displaystyle \not \in }$ R_A。

现在通过 T 的定义，我们知道了 ${\displaystyle \exists }$ n${\displaystyle \in \mathbb {N} }$  (a,b)${\displaystyle \in }$ Rⁿ_A。接着，${\displaystyle \forall }$ i${\displaystyle \in \mathbb {N} }$ , i${\displaystyle <}$ n ${\displaystyle \Rightarrow }$  e_i${\displaystyle \in }$ A。所以，有从 a 到 b 路径如下: aR_Ae₁R_A...R_Ae_(n-1)R_Ab。

但是，通过 G_A 在 R_A 上的传递性，${\displaystyle \forall }$ i${\displaystyle \in \mathbb {N} }$ , i${\displaystyle <}$ n ${\displaystyle \Rightarrow }$  (a,e_i)${\displaystyle \in }$ G_A，所以，(a,e_(n-1))${\displaystyle \in }$ G_A ${\displaystyle \wedge }$  (e_(n-1),b)${\displaystyle \in }$ G_A，所以通过 G_A 的传递性，我们得到了 (a,b)${\displaystyle \in }$ G_A。矛盾于 (a,b)${\displaystyle \not \in }$ G_A。

因此，${\displaystyle \forall }$ (a,b)${\displaystyle \in }$ A${\displaystyle \times }$ A, (a,b)${\displaystyle \in }$ T_A ${\displaystyle \Rightarrow }$  (a,b)${\displaystyle \in }$ G_A。这意味着 T${\displaystyle \subseteq }$ G，对于任何包含 R 的传递的 G。所以，T 是包含 R 的最小传递闭包。

推论

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

用途

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

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

与复杂性的关系

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

有关概念

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

算法

计算图的传递闭包的有效算法可见于 here （页面存档备份，存于互联网档案馆）。最简单的技术是Floyd-Warshall算法。

引用

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

外部連結

• "Transitive closure and reduction （页面存档备份，存于互联网档案馆）", The Stony Brook Algorithm Repository, Steven Skiena .