定义
对于任何关系R,R的传递闭包总是存在的。传递关系的任何家族的交集也是传递的。进一步的,至少存在一个包含R的传递关系,也就是平凡的。R传递闭包给出自包含R的所有传递关系的交集。
算法
针对在已有传递闭包的基础上新增序偶后的传递闭包求解问题,提出了一种基于新增序偶的传递闭包求解算法,并给出了详细证明过程。该算法在已有的传递闭包基础上,通过把新增序偶及该序偶的所有派生间接指向序偶添加到已有的传递闭包中实现求解过程,从而使算法的时间复杂度降低为O(n2),并且不受稀疏矩阵或序偶链的链长等不确定因素影响,最后通过一个实例说明了该算法的执行过程。
用途
注意两个传递关系的并集不必须是传递的。为了保持传递性,必须采用传递闭包。例如,这出现在取两个等价关系或预序的并的时候。为了获得新的等价关系或预序,必须选用传递闭包(自反性和对称性在等价关系的情况下是自动的)。
复杂性关系
在计算复杂性理论中,复杂度类NL严格对应于可使用一阶逻辑和传递闭包表达的逻辑句子的集合。这是因为传递闭包性质有密切关系于NL完全问题,找到在一个图的有向路径。类似的,L是一阶逻辑带有交换传递闭包。在向二阶逻辑增加了传递闭包的时候,我们得到PSPACe。