离散数学 1 第 7 章：关系的运算——复合、闭包与沃舍尔算法
这一章把第 6 章"缺哪条边"的观察变成算法。复合、逆、幂是三种基本运算，三种闭包是"给关系补性质"的标准操作，沃舍尔算法则是把传递闭包从 O(n⁴) 压到 O(n³) 的那一步。学这一章最容易出错的不是算法本身，而是复合的顺序：先把"谁先作用"钉死，再谈矩阵乘法怎么写，否则布尔积乘反了，后面闭包全错。
一、复合运算
设 R⊆A×B，S⊆B×C，则 R 与 S 的复合
R∘S = {
读法是：先走 R，再走 S。这里必须提醒一句：不同教材对 R∘S 的书写顺序约定相反，有的写成 S∘R 表示先 R 后 S。做题时先看题目给的定义式，不要凭记忆套。本文统一采用上式，即
矩阵写法：设 M_R 是 m×n 布尔矩阵、M_S 是 n×p 布尔矩阵，则
(M_{R∘S})[i][j] = ∨_{k=1..n} ( M_R[i][k] ∧ M_S[k][j] )
这就是布尔积，与线性代数的矩阵乘法同形，只是把"乘"换成 ∧、把"加"换成 ∨。写代码时最容易错的是下标顺序：布尔积不满足交换律，M_R⊙M_S 与 M_S⊙M_R 一般不同（连形状都可能不匹配）。
手工算一个：A = {1,2,3}，R = {<1,2>, <2,3>}，S = {<2,1>, <3,3>}。找 x 经 R 到 y、再经 S 到 z：x=1 时 y=2，S 从 2 只能到 1，得 <1,1>；x=2 时 y=3，S 从 3 到 3，得 <2,3>。所以 R∘S = {<1,1>, <2,3>}。x=3 在 R 里没有出边，自然不产生结果——复合不会凭空造出信息，结果必然落在 A×C 之内。
图上的解释最直观：R∘S 中的边
复合的代数性质：
- 结合律成立：(R∘S)∘T = R∘(S∘T)。
- 交换律不成立，一般 R∘S ≠ S∘R。
- 恒等关系是单位元：I_A∘R = R∘I_B = R。
- 对并双向分配：R∘(S∪T) = (R∘S)∪(R∘T)。
- 对交只有单向：R∘(S∩T) ⊆ (R∘S)∩(R∘T)，反向不成立。
二、逆关系与幂运算
逆关系 R⁻¹ = {
性质：(R⁻¹)⁻¹ = R；(R∘S)⁻¹ = S⁻¹∘R⁻¹（顺序必须反转，与穿脱外套同序）；(R∪S)⁻¹ = R⁻¹∪S⁻¹；(R∩S)⁻¹ = R⁻¹∩S⁻¹。还有一条判定：R 对称当且仅当 R = R⁻¹。
幂运算递归定义：R⁰ = I_A，R^{n+1} = Rⁿ∘R。于是 R¹=R、R²=R∘R、R³=R²∘R。
- 指数相加：R^m∘R^n = R^{m+n}；指数相乘：(R^m)^n = R^{mn}。
- 矩阵上是布尔幂：M_{R^n} = (M_R)^n。
- 图上：
这条图解释是后面求闭包的钥匙：传递闭包要的正是"任意长度 ≥1 的通路"，于是
t(R) = R ∪ R² ∪ R³ ∪ … ∪ Rⁿ（|A| = n）
为什么到 n 就够？因为任何长度超过 n 的通路必然重复经过某个结点，把重复段剪掉，能得到一条更短的通路，所以长度 ≥ n 的可达性都已被前 n 次幂覆盖。换个角度也能看出来：A 上只有 2^(n²) 个不同的关系，幂序列 R⁰、R¹、R²、… 必然会重复，不会无限产生新关系。
三、三种闭包
闭包的定义统一为：包含 R 的、具有性质 P 的最小关系（"最小"按集合包含 ⊆ 理解）。存在性与唯一性由这个"最小"保证。
| 闭包 | 定义式 | 矩阵操作 | 图操作 |
|---|---|---|---|
| 自反闭包 r(R) | R ∪ I_A | 主对角线全部置 1 | 每个结点加一个自环 |
| 对称闭包 s(R) | R ∪ R⁻¹ | M ∨ Mᵀ | 每条边加一条反向边 |
| 传递闭包 t(R) | R ∪ R² ∪ … ∪ Rⁿ | M ∨ M² ∨ … ∨ Mⁿ | 所有长度 ≥2 的通路补捷径边 |
三者都不改变原有边，只增不减，这从定义式一眼可见。注意 r(R)、s(R) 可以一步写出，t(R) 不行——直接用幂并集要算 n 次布尔积，代价 O(n⁴)，这就是需要沃舍尔算法的原因。
闭包的定义里还有一条常被忽略的要求：最小性。要证明某个关系 C 就是 r(R)，必须证两件事——C 自反且包含 R；任何包含 R 的自反关系都包含 C。第二句才是"最小"的实质，只写第一句要丢一半分。
三个算子的次序也值得说清：r 与 s 可交换，r(s(R)) = s(r(R))；但只要 t 参与，次序就影响结果。取 R = {<1,2>}，t(s(R)) 补出自环，得到 {<1,2>,<2,1>,<1,1>,<2,2>}；而 s(t(R)) 只有 {<1,2>,<2,1>}。要一次性得到同时满足自反、对称、传递的关系，按 r→s→t 逐层加厚即可。
四、沃舍尔算法
思路是逐步放开中间结点：第 k 轮只允许路径经过编号 ≤ k 的结点作为中间点，把新接通的可达关系写进矩阵。
// M 为 n×n 布尔矩阵，初始为 R 的关系矩阵
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
M[i][j] = M[i][j] || (M[i][k] && M[k][j]);
不变式：第 k 轮结束后，M[i][j] = 1 当且仅当存在一条从 i 到 j、且中间结点全部取自 {1,…,k} 的通路。k 走到 n 时，"中间结点"不再受限，矩阵就是传递闭包。循环变量 k 必须放最外层，这是算法正确性的关键，交换顺序就会算错。
手工演示：A = {1,2,3,4}，R = {<1,2>, <2,3>, <3,4>}。
| 轮次 k | 新增的 1 | 原因 |
|---|---|---|
| k=1 | 无 | 第 1 列全 0，结点 1 没有入边 |
| k=2 | M[1][3] | 借 2 接通 1→2→3 |
| k=3 | M[1][4]、M[2][4] | 借 3 接通 1→3→4、2→3→4 |
| k=4 | 无 | 结点 4 没有出边 |
最终 t(R) = {<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}。可以看到第 3 轮一次性补了两条，因为第 2 轮已经把 1→3 接通，这一轮才能顺着用——按 k 递增的顺序推进，前面补的边会被后面轮次继续利用，这正是算法只需 O(n³) 的原因。手算时建议每轮把矩阵抄一遍并标出新增的 1，出错时能立刻定位是哪一轮接错了路径。
复杂度：时间 O(n³)，空间 O(n²) 且可原地。作为对比，幂并集法要算 n 次布尔积，是 O(n⁴)。沃舍尔算法与求最短路的 Floyd 算法结构完全同构，只是把 min/+ 换成 ∨/∧。
| 方法 | 做法 | 复杂度 | 适用场景 |
|---|---|---|---|
| 幂并集 | R∪R²∪…∪Rⁿ | O(n⁴) | 手算小规模、验算答案 |
| 沃舍尔 | 三重循环，原地更新矩阵 | O(n³) | 通用，代码实现首选 |
| 图搜索 | 从每个结点做一次 DFS/BFS | O(n·(n+e)) | 稀疏图、只需要可达性 |
易错点
- 复合顺序：R∘S 按本文约定是"先 R 后 S"，换教材要先核对定义式；矩阵上是 M_R⊙M_S，不能写反。
- (R∘S)⁻¹ = S⁻¹∘R⁻¹，顺序必须反转，写成 R⁻¹∘S⁻¹ 是错的。
- t(R) 的幂并集里从 R¹ 开始，不含 R⁰ = I_A；若把 R⁰ 并进去，算出来的是自反传递闭包，多了一堆自环。
- 沃舍尔算法的 k 必须是最外层循环，写成 i 在最外层就退化成错误的松弛。
- 闭包只增边不减边；如果算出的闭包比原关系"少"了元素，一定是某步覆盖写错了。
这一章在整门课里的位置
本章的三种运算全部建立在第 5 章的关系矩阵与关系图上，判定依据则来自第 6 章的五条性质——闭包就是"按性质补边"。第 8 章的等价关系要求自反、对称、传递三条同时成立，等价类其实就是 r、s、t 依次作用后的连通块；而偏序的哈斯图，是把传递闭包里那些"多余"的边再删回去。
本文是《离散数学 1：数理逻辑与集合论》第 7 章的知识点摘要。完整板书与例题见 课程页；上一章 关系的性质，下一章 偏序关系。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 离散数学 1：数理逻辑与集合论 14 讲
- 离散数学 2：图论 10 讲