集合 X 上的二元关系 R 的传递闭包,是 X 上包含 R 的最小传递关系。它恰好补入反复应用传递性所必需的有序对:只要一个元素能通过 R 中有限个连续步骤到达另一个元素,对应的有序对就属于该闭包。在有向图中,这意味着只要存在从 u 到 v 的正长度有向游走,就添加一条从 u 到 v 的边。传递闭包是研究可达性、依赖分析、数据库递归查询以及关系的重要基础。
定义
X 上的关系 T 具有传递性,是指对所有 x,y,z∈X,都有
(x,y)∈T and (y,z)∈T⟹(x,z)∈T
R 的传递闭包通常记作 R+,由以下三个条件刻画:
- R⊆R+。
- R+ 具有传递性。
- 若 T 是 X 上任意一个包含 R 的传递关系,则 R+⊆T。
这里的“最小”是相对于包含关系而言的,而不只是指有序对的数量最少。这些条件唯一确定了传递闭包。
另一种等价定义使用关系的幂。令 R1=R,并定义
Rk+1={(x,z)∈X×X:there exists y∈X with (x,y)∈Rk and (y,z)∈R}.
记号 X×X 表示笛卡尔积。于是
R+=k=1⋃∞Rk.
因此,(x,y)∈R+ 当且仅当存在有限序列
x=x0,x1,…,xk=y,k≥1,
使得对每个 i,都有 (xi−1,xi)∈R。
这一构造既适用于有限集,也适用于无限集。定义中只使用有限序列,不会加入必须经过无限多个连续步骤才能建立的连接。
为什么这一构造是最小的
所有正整数次幂的并集包含 R。若 (x,y)∈Rp 且 (y,z)∈Rq,将两个序列首尾相接即可得到 (x,z)∈Rp+q,因此该并集具有传递性。
反过来,由数学归纳法可知,任何包含 R 的传递关系都必须包含每个 Rk,因而也包含它们的并集。
传递闭包与自反传递闭包
自反传递闭包通常记作 R∗,它还包含所有形如 (x,x) 的恒等对:
R∗=IX∪R+,IX={(x,x):x∈X}.
等价地,令 R0=IX,则
R∗=k=0⋃∞Rk.
二者的区别在于是否允许零步:
- R+ 表示经过一个或多个步骤的连接。
- R∗ 表示经过零个或多个步骤的连接。
对角有序对 (x,x) 只有在存在经过正数个步骤后返回 x 的序列时,才属于 R+;而它始终属于 R∗。
有些文献和软件将自反传递闭包也称为“传递闭包”。因此,必须核实其对对角有序对的处理方式,不能仅凭名称判断。
示例
设
X={a,b,c,d},R={(a,b),(b,c),(c,d)}.
则
R+={(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)}.
新增的三个有序对表示需要经过两步或三步才能建立的连接,没有加入任何对角有序对。
对于一个环,
R={(a,b),(b,a)},
其传递闭包为
R+={(a,a),(a,b),(b,a),(b,b)}.
尽管原关系不包含恒等对,但每个顶点都能经过两步返回自身。
在整数集上,令 xRy 表示 y=x+1。则 xR+y 表示 x<y,而 xR∗y 表示 x≤y。
图的解释
X 上的关系 R 可以视为以 X 为顶点集、以 R 为边集的有向图。其传递闭包记录了所有由正长度有向游走连接的有序对。这一解释将传递闭包运算与图论直接联系起来。
对于不同的顶点,只要它们之间可达,就一定存在一条没有重复顶点的路径。一个顶点要经过正数个步骤到达自身,则必须存在有向环。这一区别很重要,因为有些定义将“路径”专门用于没有重复顶点的游走。
对于具有 n≥1 个顶点的有限图,
R+=k=1⋃nRk.
不同顶点之间的可达性可由一条至多含 n−1 条边的路径来证实。从起点经过正数个步骤返回自身的可达性,则可由一个至多含 n 条边的环来证实。
对于有向无环图,正长度传递闭包不包含任何对角有序对,并且构成严格偏序。加入恒等关系后,就得到一个偏序。
更一般地,定义相互可达关系如下:
x∼y⟺xR∗y and yR∗x.
这是一个等价关系,其等价类就是图的强连通分量。将每个分量收缩为一个顶点,就得到一个无环图。
矩阵表示
对于有限图,设 A 为其布尔邻接矩阵,满足
Aij=1⟺(i,j)∈R.
使用布尔矩阵乘法,即以逻辑与代替乘法,以逻辑或代替加法:
(B⊙C)ij=k=1⋁n(Bik∧Ckj).
则布尔幂 A⊙k 记录是否存在长度恰为 k 的游走。传递闭包矩阵为
A+=A∨A⊙2∨⋯∨A⊙n,
其中逻辑或运算逐元素进行。
对于自反传递闭包,还需加入布尔单位矩阵:
A∗=I∨A+.
这是布尔代数中的运算,而不是普通的数值矩阵加法。在普通算术运算下,Ak 的元素给出长度为 k 的游走数量;布尔幂则只记录这种游走是否存在。
算法
Warshall 算法
Warshall 算法通过逐步允许更多顶点作为中间顶点来计算闭包。
用邻接矩阵初始化布尔矩阵 T。对 k=1,…,n,按下式更新所有 i,j 对应的元素:
Tij←Tij∨(Tik∧Tkj).
这一更新表示:只要 i 能到达 k,且 k 能到达 j,就能记录下 i 经由 k 到达 j 的可达性。在这一标准形式中,遍历中间顶点 k 的循环必须位于最外层。
以 T=A 初始化,计算得到的是正长度传递闭包;以 T=A∨I 初始化,计算得到的是自反传递闭包。
用大O记号表示,标准实现的时间复杂度为 O(n3),空间复杂度为 O(n2)。位向量实现可以同时处理多个元素,从而加速布尔运算。
重复图搜索
另一种方法是从每个顶点出发,分别执行一次深度优先搜索或广度优先搜索。使用邻接表时,总运行时间为
O(n(n+m)),
其中 m 为边数。这种方法通常适合稀疏图。
对于正长度传递闭包,只有在存在正长度环使搜索源点能够返回自身时,才应将源点纳入它自身的可达结果。如果搜索过程自动将源点标记为可达,且未单独处理这一约定,那么得到的就是自反可达性。
反复平方
布尔矩阵乘法还提供了一种反复平方法。从 B=I∨A 开始,反复执行
B←B⊙B.
每次平方都会使矩阵所表示的最大游走长度翻倍。经过 O(logn) 次平方后,B 就表示自反传递闭包。
即使原图只有 O(n) 条边,显式存储的闭包也可能包含 n2 个有序对。因此,无论采用哪种算法,输出完整关系都可能需要平方量级的输出空间。
代数性质
在固定集合上的所有关系所构成的集合中,传递闭包是一个闭包算子:
- 扩张性: R⊆R+。
- 单调性: 若 R⊆S,则 R+⊆S+。
- 幂等性: (R+)+=R+。
最后一个性质体现了幂等性:再次应用该运算不会添加任何内容。
传递闭包也可以定义为所有包含 R 的传递关系的交集:
R+=⋂{T⊆X×X:R⊆T and T is transitive}.
由于 X×X 具有传递性,这一关系族非空。
还可以用不动点来描述传递闭包。将关系的复合定义为
S∘T={(x,z):∃y, (x,y)∈S and (y,z)∈T},
则关系 R+ 是下列映射在包含关系下的最小不动点:
F(S)=R∪(S∘R).
这一表述是递归计算可达性的基础。
应用与相关运算
在数据库中,传递闭包可以表达递归查询,例如查找层级结构中的所有后代、所有间接依赖的组件,或通过接续路线能够到达的所有目的地。
在程序分析和形式验证中,转移关系描述单个执行步骤。其自反传递闭包描述经过任意有限步后可达的状态,包括零步的情况。如果状态空间是无限的,就不一定能用有限形式显式表示闭包,也不一定能有效计算它。
在逻辑学中,可达性体现了一阶逻辑的一项局限:不存在一个仅基于边关系的普通一阶公式,能够在所有有限有向图上定义可达性。配备传递闭包算子的逻辑可以直接表达这种无界迭代。
传递约简处理的是一个互补问题:在保持可达性的同时删除边。对于有限有向无环图,传递约简是唯一的,只保留那些不能由更长路径推导出的边。对于一般有向图,保持可达性的约简不一定唯一。
在集合论中,传递闭包还有另一种用法。传递集是指包含其每个元素的所有元素的集合,而一个集合的传递闭包,是以原集合为子集的最小传递集。这涉及反复应用元素隶属关系,而不是向任意二元关系中添加有序对;这两种构造不应混淆。