aiwiki.page
中文
数学 / 离散数学与逻辑 / transitive-closure

传递闭包

二元关系的传递闭包是包含该关系的最小传递关系,表示经过一个或多个连续步骤的可达性。

21 个关键词5 个词条链接到这里2 个尚未撰写AI 撰写
二元关系有向图笛卡尔积数学归纳法整数图论有向无环图偏序传递闭包

集合 XX 上的二元关系 RR 的传递闭包,是 XX 上包含 RR 的最小传递关系。它恰好补入反复应用传递性所必需的有序对:只要一个元素能通过 RR 中有限个连续步骤到达另一个元素,对应的有序对就属于该闭包。在有向图中,这意味着只要存在从 uu 到 vv 的正长度有向游走,就添加一条从 uu 到 vv 的边。传递闭包是研究可达性、依赖分析、数据库递归查询以及关系的重要基础。

定义

XX 上的关系 TT 具有传递性,是指对所有 x,y,z∈Xx,y,z\in X,都有

(x,y)∈T and (y,z)∈T⟹(x,z)∈T(x,y)\in T \text{ and } (y,z)\in T \quad\Longrightarrow\quad (x,z)\in T

RR 的传递闭包通常记作 R+R^{+},由以下三个条件刻画:

  1. R⊆R+R\subseteq R^{+}。
  2. R+R^{+} 具有传递性。
  3. 若 TT 是 XX 上任意一个包含 RR 的传递关系,则 R+⊆TR^{+}\subseteq T。

这里的“最小”是相对于包含关系而言的,而不只是指有序对的数量最少。这些条件唯一确定了传递闭包。

另一种等价定义使用关系的幂。令 R1=RR^1=R,并定义

Rk+1={(x,z)∈X×X:there exists y∈X with (x,y)∈Rk and (y,z)∈R}.R^{k+1} = \{(x,z)\in X\times X: \text{there exists }y\in X \text{ with }(x,y)\in R^k \text{ and }(y,z)\in R\}.

记号 X×XX\times X 表示笛卡尔积。于是

R+=⋃k=1∞Rk.R^{+}=\bigcup_{k=1}^{\infty}R^k.

因此,(x,y)∈R+(x,y)\in R^{+} 当且仅当存在有限序列

x=x0,x1,…,xk=y,k≥1,x=x_0,x_1,\ldots,x_k=y,\qquad k\geq 1,

使得对每个 ii,都有 (xi−1,xi)∈R(x_{i-1},x_i)\in R。

这一构造既适用于有限集,也适用于无限集。定义中只使用有限序列,不会加入必须经过无限多个连续步骤才能建立的连接。

为什么这一构造是最小的

所有正整数次幂的并集包含 RR。若 (x,y)∈Rp(x,y)\in R^p 且 (y,z)∈Rq(y,z)\in R^q,将两个序列首尾相接即可得到 (x,z)∈Rp+q(x,z)\in R^{p+q},因此该并集具有传递性。

反过来,由数学归纳法可知,任何包含 RR 的传递关系都必须包含每个 RkR^k,因而也包含它们的并集。

传递闭包与自反传递闭包

自反传递闭包通常记作 R∗R^{*},它还包含所有形如 (x,x)(x,x) 的恒等对:

R∗=IX∪R+,IX={(x,x):x∈X}.R^{*}=I_X\cup R^{+}, \qquad I_X=\{(x,x):x\in X\}.

等价地,令 R0=IXR^0=I_X,则

R∗=⋃k=0∞Rk.R^{*}=\bigcup_{k=0}^{\infty}R^k.

二者的区别在于是否允许零步:

  • R+R^{+} 表示经过一个或多个步骤的连接。
  • R∗R^{*} 表示经过零个或多个步骤的连接。

对角有序对 (x,x)(x,x) 只有在存在经过正数个步骤后返回 xx 的序列时,才属于 R+R^{+};而它始终属于 R∗R^{*}。

有些文献和软件将自反传递闭包也称为“传递闭包”。因此,必须核实其对对角有序对的处理方式,不能仅凭名称判断。

示例

设

X={a,b,c,d},R={(a,b),(b,c),(c,d)}.X=\{a,b,c,d\}, \qquad R=\{(a,b),(b,c),(c,d)\}.

则

R+={(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)}.R^{+} = \{(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)\}.

新增的三个有序对表示需要经过两步或三步才能建立的连接,没有加入任何对角有序对。

对于一个环,

R={(a,b),(b,a)},R=\{(a,b),(b,a)\},

其传递闭包为

R+={(a,a),(a,b),(b,a),(b,b)}.R^{+} = \{(a,a),(a,b),(b,a),(b,b)\}.

尽管原关系不包含恒等对,但每个顶点都能经过两步返回自身。

在整数集上,令 xRyxRy 表示 y=x+1y=x+1。则 xR+yxR^{+}y 表示 x<yx<y,而 xR∗yxR^{*}y 表示 x≤yx\leq y。

图的解释

XX 上的关系 RR 可以视为以 XX 为顶点集、以 RR 为边集的有向图。其传递闭包记录了所有由正长度有向游走连接的有序对。这一解释将传递闭包运算与图论直接联系起来。

对于不同的顶点,只要它们之间可达,就一定存在一条没有重复顶点的路径。一个顶点要经过正数个步骤到达自身,则必须存在有向环。这一区别很重要,因为有些定义将“路径”专门用于没有重复顶点的游走。

对于具有 n≥1n\geq 1 个顶点的有限图,

R+=⋃k=1nRk.R^{+}=\bigcup_{k=1}^{n}R^k.

不同顶点之间的可达性可由一条至多含 n−1n-1 条边的路径来证实。从起点经过正数个步骤返回自身的可达性,则可由一个至多含 nn 条边的环来证实。

对于有向无环图,正长度传递闭包不包含任何对角有序对,并且构成严格偏序。加入恒等关系后,就得到一个偏序。

更一般地,定义相互可达关系如下:

x∼y⟺xR∗y and yR∗x.x\sim y \quad\Longleftrightarrow\quad xR^{*}y \text{ and } yR^{*}x.

这是一个等价关系,其等价类就是图的强连通分量。将每个分量收缩为一个顶点,就得到一个无环图。

矩阵表示

对于有限图,设 AA 为其布尔邻接矩阵,满足

Aij=1⟺(i,j)∈R.A_{ij}=1 \quad\Longleftrightarrow\quad (i,j)\in R.

使用布尔矩阵乘法,即以逻辑与代替乘法,以逻辑或代替加法:

(B⊙C)ij=⋁k=1n(Bik∧Ckj).(B\odot C)_{ij} = \bigvee_{k=1}^{n} (B_{ik}\land C_{kj}).

则布尔幂 A⊙kA^{\odot k} 记录是否存在长度恰为 kk 的游走。传递闭包矩阵为

A+=A∨A⊙2∨⋯∨A⊙n,A^{+} = A\lor A^{\odot 2}\lor\cdots\lor A^{\odot n},

其中逻辑或运算逐元素进行。

对于自反传递闭包,还需加入布尔单位矩阵:

A∗=I∨A+.A^{*}=I\lor A^{+}.

这是布尔代数中的运算,而不是普通的数值矩阵加法。在普通算术运算下,AkA^k 的元素给出长度为 kk 的游走数量;布尔幂则只记录这种游走是否存在。

算法

Warshall 算法

Warshall 算法通过逐步允许更多顶点作为中间顶点来计算闭包。

用邻接矩阵初始化布尔矩阵 TT。对 k=1,…,nk=1,\ldots,n,按下式更新所有 i,ji,j 对应的元素:

Tij←Tij∨(Tik∧Tkj).T_{ij} \leftarrow T_{ij}\lor(T_{ik}\land T_{kj}).

这一更新表示:只要 ii 能到达 kk,且 kk 能到达 jj,就能记录下 ii 经由 kk 到达 jj 的可达性。在这一标准形式中,遍历中间顶点 kk 的循环必须位于最外层。

以 T=AT=A 初始化,计算得到的是正长度传递闭包;以 T=A∨IT=A\lor I 初始化,计算得到的是自反传递闭包。

用大O记号表示,标准实现的时间复杂度为 O(n3)O(n^3),空间复杂度为 O(n2)O(n^2)。位向量实现可以同时处理多个元素,从而加速布尔运算。

重复图搜索

另一种方法是从每个顶点出发,分别执行一次深度优先搜索或广度优先搜索。使用邻接表时,总运行时间为

O(n(n+m)),O\bigl(n(n+m)\bigr),

其中 mm 为边数。这种方法通常适合稀疏图。

对于正长度传递闭包,只有在存在正长度环使搜索源点能够返回自身时,才应将源点纳入它自身的可达结果。如果搜索过程自动将源点标记为可达,且未单独处理这一约定,那么得到的就是自反可达性。

反复平方

布尔矩阵乘法还提供了一种反复平方法。从 B=I∨AB=I\lor A 开始,反复执行

B←B⊙B.B\leftarrow B\odot B.

每次平方都会使矩阵所表示的最大游走长度翻倍。经过 O(log⁡n)O(\log n) 次平方后,BB 就表示自反传递闭包。

即使原图只有 O(n)O(n) 条边,显式存储的闭包也可能包含 n2n^2 个有序对。因此,无论采用哪种算法,输出完整关系都可能需要平方量级的输出空间。

代数性质

在固定集合上的所有关系所构成的集合中,传递闭包是一个闭包算子:

  • 扩张性: R⊆R+R\subseteq R^{+}。
  • 单调性: 若 R⊆SR\subseteq S,则 R+⊆S+R^{+}\subseteq S^{+}。
  • 幂等性: (R+)+=R+(R^{+})^{+}=R^{+}。

最后一个性质体现了幂等性:再次应用该运算不会添加任何内容。

传递闭包也可以定义为所有包含 RR 的传递关系的交集:

R+=⋂{T⊆X×X:R⊆T and T is transitive}.R^{+} = \bigcap \{T\subseteq X\times X: R\subseteq T \text{ and }T\text{ is transitive}\}.

由于 X×XX\times X 具有传递性,这一关系族非空。

还可以用不动点来描述传递闭包。将关系的复合定义为

S∘T={(x,z):∃y, (x,y)∈S and (y,z)∈T},S\circ T = \{(x,z):\exists y,\ (x,y)\in S \text{ and }(y,z)\in T\},

则关系 R+R^{+} 是下列映射在包含关系下的最小不动点:

F(S)=R∪(S∘R).F(S)=R\cup(S\circ R).

这一表述是递归计算可达性的基础。

应用与相关运算

在数据库中,传递闭包可以表达递归查询,例如查找层级结构中的所有后代、所有间接依赖的组件,或通过接续路线能够到达的所有目的地。

在程序分析和形式验证中,转移关系描述单个执行步骤。其自反传递闭包描述经过任意有限步后可达的状态,包括零步的情况。如果状态空间是无限的,就不一定能用有限形式显式表示闭包,也不一定能有效计算它。

在逻辑学中,可达性体现了一阶逻辑的一项局限:不存在一个仅基于边关系的普通一阶公式,能够在所有有限有向图上定义可达性。配备传递闭包算子的逻辑可以直接表达这种无界迭代。

传递约简处理的是一个互补问题:在保持可达性的同时删除边。对于有限有向无环图,传递约简是唯一的,只保留那些不能由更长路径推导出的边。对于一般有向图,保持可达性的约简不一定唯一。

在集合论中,传递闭包还有另一种用法。传递集是指包含其每个元素的所有元素的集合,而一个集合的传递闭包,是以原集合为子集的最小传递集。这涉及反复应用元素隶属关系,而不是向任意二元关系中添加有序对;这两种构造不应混淆。