传递闭包

数学术语

传递闭包、即在数学中，在集合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 当且仅当存在有限的元素( )序列，使得并且

, , …, 和

形式上写为

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

有关概念

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

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

证明

设 A 是任何元素的集合。

假定: GA 传递关系 RAGA TAGA。所以 (a,b)GA(a,b)TA. 所以，特定的 (a,b)RA。

现在通过 T 的定义，我们知道了 n (a,b)RnA。接着，i, in eiA。所以，有从 a 到 b 路径如下: aRAe1RA...RAe(n-1)RAb。

但是，通过 GA 在 RA 上的传递性，i, in (a,ei)GA，所以，(a,e(n-1))GA (e(n-1),b)GA，所以通过 GA 的传递性，我们得到了 (a,b)GA。矛盾于 (a,b)GA。

因此，(a,b)AA, (a,b)TA (a,b)GA。这意味着 TG，对于任何包含 R 的传递的 G。所以，T 是包含 R 的最小传递闭包。

推论

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

用途

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

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

与复杂性的关系

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

算法

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

Floyd-Warshall算法

单独一条边的路径也不一定是最佳路径。从任意一条单边路径开始。所有两点之间的距离是边的权的和，(如果两点之间没有边相连, 则为无穷大）。对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。不可思议的是，只要按排适当，就能得到结果。// dist(i,j) 为从节点i到节点j的最短距离

For i←1to n do

For j←1to n do

dist(i,j) = weight(i,j)

For k←1to n do// k为“媒介节点”{一定要先枚举媒介节点}

For i←1to n do

For j←1to n do

if(dist(i,k) + dist(k,j) < dist(i,j))then// 是否是更短的路径？

dist(i,j) = dist(i,k) + dist(k,j)

这个算法的效率是O(V^3)。它需要邻接矩阵来储存图。

这个算法很容易实现，只要几行。

即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间，时间上就没问题)。

计算每一对顶点间的最短路径（floyd算法）