传递闭包

传递闭包、即在数学中，在集合 上的二元关系 的传递闭包是包含 的 上的最小的传递关系。

例如，如果 是(生或死)人的集合而 是关系“为父子”，则 的传递闭包是关系“ 是 的祖先”。再比如，如果 是空港的集合而关系 为“从空港 到空港 有直航”，则 的传递闭包是“可能经一次或多次航行从 飞到 ”。

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

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

形式上写为

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

设 是任何元素的集合。

假定: ${\displaystyle \mathrm{\exists <!--\; \exists \; -->}}$ 传递关系 ${\displaystyle \subseteq <!--\; \subseteq \; -->}$ ${\displaystyle \wedge <!--\; \wedge \; -->}$${\displaystyle ⊈}$。所以 ${\displaystyle \mathrm{\exists <!--\; \exists \; -->}}$${\displaystyle \notin }$${\displaystyle \wedge <!--\; \wedge \; -->}$${\displaystyle \in <!--\; \in \; -->}$. 所以，特定的 ${\displaystyle \notin }$。

现在通过 的定义，我们知道了 ${\displaystyle \mathrm{\exists <!--\; \exists \; -->}}$${\displaystyle \in <!--\; \in \; -->\mathbb{N}}$${\displaystyle \in <!--\; \in \; -->}$。接着，${\displaystyle \mathrm{\forall <!--\; \forall \; -->}}$${\displaystyle \in <!--\; \in \; -->\mathbb{N}}$ ${\displaystyle \Rightarrow <!--\; \Rightarrow \; -->}$${\displaystyle \in <!--\; \in \; -->}$。所以，有从 到 路径如下: 。

但是，通过 在 上的传递性，${\displaystyle \mathrm{\forall <!--\; \forall \; -->}}$${\displaystyle \in <!--\; \in \; -->\mathbb{N}}$ ${\displaystyle \Rightarrow <!--\; \Rightarrow \; -->}$${\displaystyle \in <!--\; \in \; -->}$，所以，${\displaystyle \in <!--\; \in \; -->}$ ${\displaystyle \wedge <!--\; \wedge \; -->}$${\displaystyle \in <!--\; \in \; -->}$，所以通过 的传递性，我们得到了 ${\displaystyle \in <!--\; \in \; -->}$。矛盾于 ${\displaystyle \notin }$。

因此，${\displaystyle \mathrm{\forall <!--\; \forall \; -->}}$${\displaystyle \in <!--\; \in \; -->}$${\displaystyle \times <!--\; \times \; -->}$, ${\displaystyle \in <!--\; \in \; -->}$ ${\displaystyle \Rightarrow <!--\; \Rightarrow \; -->}$${\displaystyle \in <!--\; \in \; -->}$。这意味着 ${\displaystyle \subseteq <!--\; \subseteq \; -->}$，对于任何包含 的传递的 。所以， 是包含 的最小传递闭包。

如果 是传递的，则 = 。

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

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

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

计算图的传递闭包的有效算法可见于 here。最简单的技术是Floyd-Warshall算法。