传递闭包


数学中,集合X上的二元关系 R传递闭包是包含RX上的最小的递移关系

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

存在性和描述

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

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

x0Rx1, x1Rx2, …, xn−1RxnxnRy

形式上写为

 

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

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

A 是任何元素的集合。

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

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

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

因此, (a,b) A A, (a,b) TA   (a,b) GA。这意味着 T 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, 编辑