本节对应原书 PDF 第 111–119 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

4.3.1 关系性质的定义和判别

本节涉及的关系都是指某个集合 A 上的关系，所讨论的关系的性质是：自反性、反自反性、对称性、反对称性和传递性. 下面给出定义.

定义 4.14 设 R 是集合 A 上的关系，

（1）如果 \forall x(x \in A \rightarrow \langle x, x \rangle \in R)，则称 R 在 A 上自反.

（2）如果 \forall x(x \in A \rightarrow \langle x, x \rangle \notin R)，则称 R 在 A 上反自反.

易见，恒等关系 I_A，全域关系 E_A，小于等于关系 L_A，整除关系 D_A 都是给定集合 A 上的自反关系. 空关系 \varnothing，小于关系是 A 上反自反的关系.

对于非空的集合 A，根据关系是否具有自反性和反自反性可以将关系划分为 3 类：自反但不是反自反的，反自反但不是自反的，既不是自反的也不是反自反的.

解读：自反与反自反并不是一对互补的性质——它们讨论的都是「每个元素与自身的关系」，只是要求恰好相反。只要有一个元素缺自环，自反性就失败；只要有一个元素有自环，反自反性就失败。因此两者可以同时为假，却不能同时为真。

例 4.11 设 A = \{a, b, c\}，

R_1 = \{\langle a, a \rangle, \langle b, b \rangle, \langle b, c \rangle, \langle c, c \rangle\}
R_2 = \{\langle a, b \rangle\}
R_3 = \{\langle a, a \rangle, \langle a, b \rangle\}

这里 R_1 是自反的但不是反自反的，R_2 是反自反的但不是自反的，R_3 既不是自反的也不是反自反的.

对于任何集合 A，最大的自反关系是 E_A，最小的自反关系是 I_A，最大的反自反关系是 E_A - I_A，最小的反自反关系是空关系 \varnothing. 可以证明：A 上任何自反关系 R 都满足 I_A \subseteq R，A 上任何反自反关系 R 都满足 R \cap I_A = \varnothing.

从关系矩阵的特点来看，自反关系的关系矩阵的主对角线元素全是 1，反自反关系的关系矩阵的主对角线元素全是 0. 主对角线元素有 1 也有 0 的关系既不是自反的也不是反自反的.

从关系图的特点来看，自反关系的关系图中每个结点都有过自身的环（从某个结点出发到自己的边），反自反关系图中每个结点都没有环. 如果有的结点有环，有的结点没有环，那么这个关系既不是自反的也不是反自反的.

定义 4.15 设 R 是集合 A 上的关系，

（1）如果 \forall x \forall y(x, y \in A \wedge \langle x, y \rangle \in R \rightarrow \langle y, x \rangle \in R)，则称 R 在 A 上对称.

（2）如果 \forall x \forall y(x, y \in A \wedge \langle x, y \rangle \in R \wedge \langle y, x \rangle \in R \rightarrow x = y)，则称 R 在 A 上反对称.

空关系 \varnothing，恒等关系 I_A，全域关系 E_A 都是 A 上对称的关系. 空关系 \varnothing 和恒等关系 I_A 也是 A 上反对称的关系. 小于等于关系、小于关系、整除关系、包含关系等都是相应集合上的反对称关系.

A 上的反对称关系 R 也可以定义为

\forall x \forall y(x, y \in A \wedge \langle x, y \rangle \in R \wedge x \neq y \rightarrow \langle y, x \rangle \notin R)

这就是说，对于不同的元素 x 和 y，如果 x 与 y 有这种关系，那么 y 与 x 就一定没有这种关系. 比如说对于两个不同的数 x 和 y，如果 x < y，那么一定不会有 y < x. 可以证明这个定义和定义 4.15(2) 是等价的.

对于非空的集合 A，根据关系是否具有对称性和反对称性可以将关系划分为 4 类：对称但不是反对称的，反对称但不是对称的，既是对称的又是反对称的，既不是对称的也不是反对称的.

解读：反对称常被误读成「对称的反面」，其实它只禁止互相的有序对同时出现：若 x \neq y，则 \langle x, y \rangle 与 \langle y, x \rangle 至多存其一。恒等关系 I_A 就是「既对称又反对称」的例子——它根本没有 x \neq y 的有序对，两条性质都空真成立。

例 4.12 设 A = \{a, b, c\}，

R_1 = \{\langle a, a \rangle, \langle b, b \rangle, \langle b, c \rangle, \langle c, b \rangle\}
R_2 = \{\langle a, b \rangle, \langle c, a \rangle\}
R_3 = \{\langle a, a \rangle, \langle b, b \rangle\}
R_4 = \{\langle a, b \rangle, \langle b, a \rangle, \langle a, c \rangle\}

这里 R_1 是对称的但不是反对称的，R_2 是反对称的但不是对称的，R_3 既是对称的又是反对称的，R_4 既不是对称的也不是反对称的.

对于集合 A，最小的对称关系是空关系 \varnothing，最大的对称关系是全域关系 E_A，最小的反对称关系也是空关系 \varnothing. 可以证明 A 上任何对称关系 R 都满足 R = R^{-1}，任何反对称关系 R 都满足 R \cap R^{-1} \subseteq I_A.

从关系矩阵的特点来看，对称关系 R 的关系矩阵 M_R 也是对称的. 即矩阵 M_R 的转置矩阵 M_R^{T} = M_R. 在反对称关系 R 的关系矩阵 M_R 中，处于对称位置的两个不同元素不能同时为 1. 换句话说，当 i \neq j 时，i 行 j 列的元素 r_{ij} 与 j 行 i 列的元素 r_{ji} 可以同时为 0，可以是一个 1 和一个 0，但是不能同时为 1. 不难看出，如果一个关系矩阵只在主对角线位置的元素有 1，其他元素都是 0，那么这个关系既是对称的也是反对称的.

从关系图的特点来看，在对称关系图的两个结点之间如果有边，一定是一对方向相反的边. 类似地，在反对称关系图的两个结点之间如果有边，一定是一条单方向的边. 如果在一个关系图中，两个结点之间既有单向的边，也有双向的边，那么这个关系既不是对称的也不是反对称的. 如果关系图中任意两个结点之间都没有边（可以存在过一个结点的环），那么这个关系既是对称的也是反对称的.

定义 4.16 设 R 是集合 A 上的关系，如果

\forall x \forall y \forall z(x, y, z \in A \wedge \langle x, y \rangle \in R \wedge \langle y, z \rangle \in R \rightarrow \langle x, z \rangle \in R)

则称 R 是传递的.

集合 A 上的空关系 \varnothing，恒等关系 I_A，全域关系 E_A，小于等于关系 L_A，整除关系 D_A，包含关系等都是传递关系.

解读：传递性只对「链」提出要求：只要有 x \to y \to z 两段边，就必须补上 x \to z。如果压根找不到这样的两段边（如例 4.13 的 R_3、R_4），蕴涵式前件为假，性质自动成立。

例 4.13 设 A = \{a, b, c\}，

R_1 = \{\langle a, b \rangle, \langle b, c \rangle, \langle a, c \rangle\}
R_2 = \{\langle a, b \rangle, \langle b, a \rangle\}
R_3 = \{\langle a, a \rangle, \langle b, b \rangle\}
R_4 = \{\langle a, b \rangle\}

则 R_1，R_3 和 R_4 是传递的，R_2 不是传递的. 考察 R_2，存在 \langle a, b \rangle 和 \langle b, a \rangle 属于 R_2，但是 \langle a, a \rangle 和 \langle b, b \rangle 不属于 R_2. 对于 R_3 和 R_4，无论选什么不同的元素都不能使定义 4.16 中蕴涵式的前件为真. 根据蕴涵式真值的规定，前件为假的蕴涵式是真命题，因此关系满足定义 4.16 的条件.

可以证明 A 上的关系 R 具有传递性的充分必要条件就是 R \circ R \subseteq R，容易验证例 4.13 的 R_2 不满足这个条件. 类似地也可以根据 R 的关系矩阵 \boldsymbol{M}_R 来判断关系的传递性. 首先计算 \boldsymbol{M}_R 的平方 \boldsymbol{M} = \boldsymbol{M}_R^2，然后针对 \boldsymbol{M} 中元素为 1 的每个位置检查 \boldsymbol{M}_R 中相应的位置是否为 1. 如果在 \boldsymbol{M}_R 中相应的位置都是 1，那么 R 是传递的. 考虑例 4.13 中的关系 R_1，R_1 的关系矩阵 \boldsymbol{M}_{R_1} 和它的平方是

\boldsymbol{M}_{R_1} = \begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}, \quad \boldsymbol{M} = \boldsymbol{M}_{R_1}^2 = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}

其中 \boldsymbol{M} 中只有 r_{13} = 1，而 \boldsymbol{M}_{R_1} 中的 r_{13} 也是 1，因此 R_1 是传递的.

根据关系图同样可以判断关系是否具有传递性. 设 A = \{x_1, x_2, \cdots, x_n\}，A 上关系 R 的关系图为 G_R. 依次考察 G_R 的每个结点 x_i，i = 1, 2, \cdots, n，如果 x_i 经过两步长的有向路径到达 x_j，那么在 G_R 中应该有一条从 x_i 到 x_j 的边. 注意，如果 i = j，那么这条边就变成一个过 x_i 的环. 如果找到某个结点不满足这个要求，那么 R 就不是传递的；如果不存在这样的结点，R 就是传递的. 请看下面的例子.

例 4.14 设 A 上关系 R, S, T 的关系图如图 4.4 所示，分析它们的性质.

原书图4.4 R,S,T 关系图

解 R 是自反的、反对称的. S 是反自反的、对称的. T 是反对称的、传递的. 怎样判断传递性呢？在 R 的关系图中有 c 到 a 的边，a 到 b 的边，但是缺少 c 到 b 的边，因此 R 不是传递的. 在 S 的关系图中有 a 到 b 的边，有 b 到 a 的边，但是缺少过 a 及过 b 的环. 而在 T 的关系图中没有破坏传递性质的情况出现.

上述关于关系性质的判别方法总结在表 4.2 中.

表 4.2

关系表示 \ 关系性质自反性反自反性对称性反对称性传递性
集合表达式I_A \subseteq RR \cap I_A = \varnothingR = R^{-1}R \cap R^{-1} \subseteq I_AR \circ R \subseteq R
关系矩阵主对角线元素全是 1主对角线元素全是 0矩阵是对称矩阵若 r_{ij} = 1，且 i \neq j，则 r_{ji} = 0对 \boldsymbol{M}^2 中 1 所在位置，\boldsymbol{M} 中相应位置都是 1
关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边，一定是一对方向相反的边（无单边）如果两点之间有边，一定是一条有向边（无双向边）如果顶点 x_i 到 x_j 有边，x_j 到 x_k 有边，则从 x_i 到 x_k 也有边

下面考虑关系的性质和运算的联系. 设 R_1 和 R_2 都是集合 A 上的关系，可以证明以下命题：

（1）如果 R_1 和 R_2 都是自反的，则 R_1^{-1}，R_1 \cap R_2，R_1 \cup R_2，R_1 \circ R_2 也是自反的.

（2）如果 R_1 和 R_2 都是反自反的，则 R_1^{-1}，R_1 \cap R_2，R_1 \cup R_2，R_1 - R_2 也是反自反的.

（3）如果 R_1 和 R_2 都是对称的，则 R_1^{-1}，R_1 \cap R_2，R_1 \cup R_2，R_1 - R_2 也是对称的.

（4）如果 R_1 和 R_2 都是反对称的，则 R_1^{-1}，R_1 \cap R_2，R_1 - R_2 也是反对称的.

（5）如果 R_1 和 R_2 都是传递的，则 R_1^{-1}，R_1 \cap R_2 也是传递的.

关于这些命题的结果可以总结成表 4.3. 对于保持性质的命题，就在表中相应的位置打「\surd」，否则打「\times」. 对于每个「\surd」，都可以给出证明；对于每个「\times」，都可以举出反例.

表 4.3

关系运算 \ 关系性质自反性反自反性对称性反对称性传递性
R_1^{-1}\surd\surd\surd\surd\surd
R_1 \cap R_2\surd\surd\surd\surd\surd
R_1 \cup R_2\surd\surd\surd\times\times
R_1 - R_2\times\surd\surd\surd\times
R_1 \circ R_2\surd\times\times\times\times

例 4.15 （1）证明：如果 R_1 和 R_2 都是反对称的，则 R_1 \cap R_2 也是反对称的.

（2）设 R_1 和 R_2 都是传递的，举出反例说明 R_1 \circ R_2 不一定是传递的.

解 （1）证明：任取 \langle x, y \rangle，\langle y, x \rangle

\begin{aligned} \langle x, y \rangle \in R_1 \cap R_2 \wedge \langle y, x \rangle \in R_1 \cap R_2 \\ \Rightarrow \langle x, y \rangle \in R_1 \wedge \langle x, y \rangle \in R_2 \wedge \langle y, x \rangle \in R_1 \wedge \langle y, x \rangle \in R_2 \\ \Rightarrow \langle x, y \rangle \in R_1 \wedge \langle y, x \rangle \in R_1 \\ \Rightarrow x = y \quad (\text{因为 } R_1 \text{ 是反对称的}) \end{aligned}

因此 R_1 \cap R_2 也是反对称的.

（2）反例如下：

A = \{1, 2, 3\}，R_1 = \{\langle 1, 1 \rangle, \langle 2, 3 \rangle\}，R_2 = \{\langle 1, 2 \rangle, \langle 3, 3 \rangle\} 都是传递的，R_1 \circ R_2 = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle\} 不是传递的.

解读：表 4.3 的每一格都能自己验算：\surd 靠集合表达式逐项推，\times 靠一个两三个元素的小反例。最反直觉的是「两个传递关系的复合不一定传递」，例 4.15(2) 给出的 R_1 \circ R_2 = \{\langle 1, 2 \rangle, \langle 2, 3 \rangle\} 正好缺了 \langle 1, 3 \rangle。

关系性质判定器：勾选关系矩阵自动判别

4.3.2 关系的闭包

设 R 是集合 A 上的关系. 如果 R 不具有某些性质，比如说对称性，那么可以通过在 R 中加入最少数量的有序对来扩充 R，使得扩充后的 R 具有对称性. 这种经过扩充的 R 称作 R 的对称闭包. 类似地也可以构造 R 的自反和传递闭包. 下面给出闭包定义.

定义 4.17 设 R 是非空集合 A 上的关系，R 的自反（对称或传递）闭包是 A 上的关系 R'，使得 R' 满足以下条件：

（1）R' 是自反的（对称的或传递的）.

（2）R \subseteq R'.

（3）对 A 上任何包含 R 的自反（对称或传递）关系 R'' 有 R' \subseteq R''.

一般将 R 的自反闭包记作 r(R)，对称闭包记作 s(R)，传递闭包记作 t(R).

根据闭包定义不难看出，如果 R 已经具有所需要的性质，比如说 R 是对称的，那么 R 的对称闭包就是 R 自身，即 s(R) = R. 对于自反闭包和传递闭包也有类似的性质.

怎样构造关系的闭包呢？根据关系的 3 种表示方法：集合表达式、关系矩阵和关系图可以得到计算闭包的 3 种方法.

解读：定义 4.17 的第 (3) 条才是「闭包」区别于「随便加几条边」的关键——它要求加得最少，即任何别的合法扩充都包含它。所以自反闭包就是在原关系上补所有缺失的自环，一个都不多补。

定理 4.7 设 R 为 A 上的关系，则有

（1）r(R) = R \cup R^0.

（2）s(R) = R \cup R^{-1}.

（3）t(R) = R \cup R^2 \cup R^3 \cup \cdots.

证明 这里只证（1）和（3）.（2）的证明与（1）类似.

（1）只需证明 R \cup R^0 满足闭包定义.

显然 R \cup R^0 包含了 R，由 I_A \subseteq R \cup R^0 可知 R \cup R^0 在 A 上是自反的. 下面证明 R \cup R^0 是包含 R 的最小的自反关系. 假设 R' 是包含 R 的自反关系，那么 I_A \subseteq R'，R \subseteq R'，因此

R \cup R^0 = I_A \cup R \subseteq R'

（3）先证明 t(R) \subseteq R \cup R^2 \cup R^3 \cup \cdots. 根据闭包定义，这里只需证明 R \cup R^2 \cup R^3 \cup \cdots 具有传递性. 任取 \langle x, y \rangle 和 \langle y, z \rangle

\begin{aligned} \langle x, y \rangle \in R \cup R^2 \cup R^3 \cup \cdots \wedge \langle y, z \rangle \in R \cup R^2 \cup R^3 \cup \cdots \\ \Rightarrow \exists t(\langle x, y \rangle \in R^t) \wedge \exists s(\langle y, z \rangle \in R^s) \\ \Rightarrow \langle x, z \rangle \in R^t \circ R^s \Rightarrow \langle x, z \rangle \in R^{t+s} \\ \Rightarrow \langle x, z \rangle \in R \cup R^2 \cup R^3 \cup \cdots \end{aligned}

下面证明 R \cup R^2 \cup R^3 \cup \cdots \subseteq t(R). 为此只需证明 R^n \subseteq t(R)，其中 n 代表任意正整数. 这里对 n 进行归纳证明.

n = 1 时显然为真. 假设对于 n = k 时为真，那么对于任意 \langle x, y \rangle

\begin{aligned} \langle x, y \rangle \in R^{k+1} &\Rightarrow \langle x, y \rangle \in R^k \circ R \\ &\Rightarrow \exists t(\langle x, t \rangle \in R^k \wedge \langle t, y \rangle \in R) \\ &\Rightarrow \exists t(\langle x, t \rangle \in t(R) \wedge \langle t, y \rangle \in t(R)) \\ &\Rightarrow \langle x, y \rangle \in t(R) \qquad (\text{由于 } t(R) \text{ 是传递的}) \end{aligned}

可以证明，对于有穷集合 A 上的关系 R，t(R) = R \cup R^2 \cup R^3 \cup \cdots \cup R^s，其中 s 不超过 A 中的元素数.

例 4.16 设 A = \{a, b, c, d\}，

R = \{\langle a, b \rangle, \langle a, c \rangle, \langle b, c \rangle, \langle c, d \rangle, \langle d, c \rangle\}

求 r(R)，s(R)，t(R).

解 根据定理 4.7 有

r(R) = R \cup R^0 = \{\langle a, a \rangle, \langle a, b \rangle, \langle a, c \rangle, \langle b, b \rangle, \langle b, c \rangle, \langle c, c \rangle, \langle c, d \rangle, \langle d, c \rangle, \langle d, d \rangle\}

s(R) = R \cup R^{-1} = \{\langle a, b \rangle, \langle b, a \rangle, \langle a, c \rangle, \langle c, a \rangle, \langle b, c \rangle, \langle c, b \rangle, \langle c, d \rangle, \langle d, c \rangle\}

R^2 = \{\langle a, c \rangle, \langle a, d \rangle, \langle b, d \rangle, \langle c, c \rangle, \langle d, d \rangle\}

R^3 = \{\langle a, d \rangle, \langle a, c \rangle, \langle b, c \rangle, \langle c, d \rangle, \langle d, c \rangle\}

R^4 = \{\langle a, c \rangle, \langle a, d \rangle, \langle b, d \rangle, \langle c, c \rangle, \langle d, d \rangle\}

t(R) = R \cup R^2 \cup R^3 \cup R^4 = \{\langle a, b \rangle, \langle a, c \rangle, \langle a, d \rangle, \langle b, c \rangle, \langle b, d \rangle, \langle c, c \rangle, \langle c, d \rangle, \langle d, c \rangle, \langle d, d \rangle\}

可以用关系矩阵直接计算关系的自反、对称和传递闭包的矩阵. 设关系 R 及 r(R)，s(R)，t(R) 的矩阵分别为 \boldsymbol{M}，\boldsymbol{M}_r，\boldsymbol{M}_s，\boldsymbol{M}_t，则

\boldsymbol{M}_r = \boldsymbol{M} + \boldsymbol{E}
\boldsymbol{M}_s = \boldsymbol{M} + \boldsymbol{M}''
\boldsymbol{M}_t = \boldsymbol{M} + \boldsymbol{M}^2 + \boldsymbol{M}^3 + \cdots

这些公式实际上就是定理 4.7 中公式的直接结果. 考虑例 4.16 中的关系，相关的关系矩阵 \boldsymbol{M}，\boldsymbol{M}_r，\boldsymbol{M}_s，\boldsymbol{M}_t 是

\boldsymbol{M} = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}, \quad \boldsymbol{M}_r = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}, \quad \boldsymbol{M}_s = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}
\boldsymbol{M}_t = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}

也可以利用关系图计算关系的闭包. 设关系 R 及 r(R)，s(R)，t(R) 的关系图分别为 G，G_r，G_s，G_t. 为了构造 G_r，只需在图 G 中缺少环的每个结点加一个环. 为了构造 G_s，只需将 G 中的单向边变成双向边，即对于 G 中的任意两个不同的结点 x 和 y，如果只存在从 x 到 y 的边，那么在图 G_s 中加一条从 y 到 x 的边. 为从图 G 得到 G_t，需要检查每个结点的可达性. 考虑结点 x，如果从 x 经过至多 n（n 是图 G 中的结点数）步长的有向路径到达结点 y，并且 G 中缺少从 x 到 y 的有向边，那么就在 G_t 中加上一条从 x 到 y 的边. 当所有的结点都检查完以后，就得到图 G_t. 注意，当 y = x 时，增加的边 \langle x, x \rangle 实际上是过结点 x 的环. 例如，在例 4.16 的关系中，从 a 可达 b，c，d，但在 R 的关系图中缺少从 a 到 d 的边，因此在传递闭包的关系图中加上从 a 到 d 的边；类似地还可以加上从 b 到 d 的边，从 c 到 c 的边和从 d 到 d 的边. 图 4.5 给出了 3 个闭包的关系图.

原书图4.5 关系 R 及其 3 个闭包的关系图

不难看出，在传递闭包 t(R) 的关系图中，从结点 x 到 y 有一条边，当且仅当在 R 的关系图中从结点 x 到 y 存在一条长度至少为 1 的有向路径. 即在图 G 中可以从 x 连通到 y. 关系 R 的传递闭包实际上就是图 G 的连通关系 R^*，其中 R^* 定义如下：

R^* = \{\langle x, y \rangle \mid \text{在 } G \text{ 中存在一条从 } x \text{ 到 } y \text{ 的有向路径}\}

图的连通性问题是图论研究的重要问题之一，在实际中有着广泛的应用. 例如通信网络的连通问题，运输路线的规划问题等等都涉及图的连通性. 因此传递闭包的计算需要一个高效率的算法. 一个著名的算法就是沃舍尔（Warshall）算法.

考虑 n+1 个矩阵的序列 \boldsymbol{M}_0，\boldsymbol{M}_1，\cdots，\boldsymbol{M}_n，将矩阵 \boldsymbol{M}_k 的 i 行 j 列的元素记作 \boldsymbol{M}_k[i, j]. 对于 k = 0, 1, \cdots, n，\boldsymbol{M}_k[i, j] = 1 当且仅当在 R 的关系图中存在一条从 x_i 到 x_j 的路径，并且这条路径除端点外中间只经过 \{x_1, x_2, \cdots, x_k\} 中的顶点. 不难看出 \boldsymbol{M}_0 就是 R 的关系矩阵，而 \boldsymbol{M}_n 就对应了 R 的传递闭包. Warshall 算法从 \boldsymbol{M}_0 开始，顺序计算 \boldsymbol{M}_1，\boldsymbol{M}_2，\cdots 直到 \boldsymbol{M}_n 为止.

假设 \boldsymbol{M}_k 已经计算完毕，如何计算 \boldsymbol{M}_{k+1} 呢？这需要对于每组 i, j，确定 \boldsymbol{M}_{k+1}[i, j] 是否为 1. \boldsymbol{M}_{k+1}[i, j] = 1 当且仅当在 R 的关系图中存在一条从 x_i 到 x_j 并且中间只经过 \{x_1, x_2, \cdots, x_k, x_{k+1}\} 中顶点的路径. 可以将这种路径分成两类：第一类是只经过 \{x_1, x_2, \cdots, x_k\} 中顶点的路径，这时 \boldsymbol{M}_k[i, j] = 1. 第二类是经过顶点 x_{k+1} 的路径. 因为回路可以从路径中删除，因此只需考虑经过 x_{k+1} 一次的路径. 这条路径可以分成两段，从 x_i 到 x_{k+1}，再从 x_{k+1} 到 x_j，因此有 \boldsymbol{M}_k[i, k+1] = 1 和 \boldsymbol{M}_k[k+1, j] = 1. 对于第二类路径的判别，可以利用下面的条件：

\boldsymbol{M}_{k+1}[i, j] = 1 \Leftrightarrow \boldsymbol{M}_k[i, k+1] = 1 \wedge \boldsymbol{M}_k[k+1, j] = 1

算法 4.1 Warshall 算法.

输入：\boldsymbol{M}（R 的关系矩阵）.

输出：\boldsymbol{M}_t（t(R) 的关系矩阵）.

  1. \boldsymbol{M}_t \leftarrow \boldsymbol{M}
  1. for k \leftarrow 1 to n do
  1. \quad for i \leftarrow 1 to n do
  1. \quad\quad for j \leftarrow 1 to n do
  1. \quad\quad\quad \boldsymbol{M}_t[i, j] \leftarrow \boldsymbol{M}_t[i, j] + \boldsymbol{M}_t[i, k] \cdot \boldsymbol{M}_t[k, j]

注意，上述算法中矩阵加法和乘法中的元素相加都使用逻辑加. 考虑例 4.16 中的关系 R. 利用 Warshall 算法计算的矩阵序列如下所示.

\boldsymbol{M}_0 = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}, \quad \boldsymbol{M}_1 = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}, \quad \boldsymbol{M}_2 = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix},
\boldsymbol{M}_3 = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}, \quad \boldsymbol{M}_4 = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix}

Warshall 算法与前面的矩阵表示法计算所得到的结果是一致的，但是 Warshall 方法效率更高. 下面进行分析. 估计算法效率常用的方法是针对问题选择一个基本运算，然后统计该算法所需要的基本运算的次数，通常认为运算次数较少的算法效率比较高.

以矩阵元素之间的 1 次乘法作为 1 次基本运算，考察一般的矩阵计算方法. 在公式

\boldsymbol{M}_t = \boldsymbol{M} + \boldsymbol{M}^2 + \boldsymbol{M}^3 + \cdots + \boldsymbol{M}^n

中，为计算 \boldsymbol{M}^2，\boldsymbol{M}^3，\cdots，\boldsymbol{M}^n，每次都要做两个 n 阶矩阵相乘的运算，例如 \boldsymbol{M}^3 = \boldsymbol{M}^2 \boldsymbol{M}，\boldsymbol{M}^4 = \boldsymbol{M}^3 \boldsymbol{M}，\cdots. 两个 n 阶矩阵相乘需要做多少次元素的乘法运算呢？不难看出，为得到结果矩阵的每个元素 r_{ij}，需要做 n 次元素之间的相乘. 即 r_{ij} = r_{i1} r_{1j} + r_{i2} r_{2j} + \cdots + r_{in} r_{nj}. 由于矩阵中有 n^2 个元素，总共要做 n^3 次乘法. 因此，利用上述公式直接计算 \boldsymbol{M}_t，需要的乘法次数是 (n-1)n^3. 相反，在 Warshall 算法中，第 2 行、3 行、4 行都是 n 步的循环，因此第 5 行总共被执行 n^3 次，而每次只做 1 次乘法，因此 Warshall 算法总共执行 n^3 次乘法.

最后需要说明的是计算具有多种性质闭包的运算次序问题. 对于 A 上的关系 R，如果求 R 的同时具有自反、对称、传递 3 种性质的闭包，那么可以采用下面的次序：先计算 R 的自反闭包 r(R)，然后计算 r(R) 的对称闭包 sr(R)，最后计算 sr(R) 的传递闭包 tsr(R). 可以证明 tsr(R) 就是 R 的自反、对称、传递闭包. 例如，A = \{1, 2, 3\}，R = \{\langle 1, 2 \rangle, \langle 1, 3 \rangle\}，那么

r(R) = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 1, 3 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle\}

sr(R) = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 1, 3 \rangle, \langle 3, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle\}

tsr(R) = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 1, 3 \rangle, \langle 2, 1 \rangle, \langle 2, 2 \rangle, \langle 2, 3 \rangle, \langle 3, 1 \rangle, \langle 3, 2 \rangle, \langle 3, 3 \rangle\}

注意，千万不要颠倒对称和传递闭包的计算次序. 如果先计算传递闭包，然后再计算对称闭包，那么在计算对称闭包时有可能将传递性丢失. 考虑上面的例子. 如果采用如下的计算过程：

r(R) = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 1, 3 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle\}

tr(R) = r(R)

str(R) = sr(R) = \{\langle 1, 1 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 1, 3 \rangle, \langle 3, 1 \rangle, \langle 2, 2 \rangle, \langle 3, 3 \rangle\}

那么最终得到的关系 str(R) 就不是传递的，因为其中存在有序对 \langle 3, 1 \rangle，\langle 1, 2 \rangle，但是没有 \langle 3, 2 \rangle.

解读：次序不可颠倒的原因很直观：补对称边会引入新的边，而这些新边可能又制造出需要补的传递边。所以「对称化」必须排在「传递化」前面；反过来先做传递闭包，再补对称边，新补的边就再也没机会参与传递推演了。