企业官网建设流程全解析

离散数学里讲到关系这一章，最难啃的往往不是概念本身，而是把自反、对称、传递这三条性质，连同闭包、Warshall 算法一起放进同一道综合性习题里。这三个性质是质检标准，闭包是补边工具，Warshall 则是处理传递闭包的高效算法。上一篇我们聊了关系的基本运算，这篇继续往深走，把判断性质和求闭包这两件事彻底讲透。适合正在复习离散数学、准备期末或考研，或者只是想把关系矩阵弄明白的同学；只要你能理解“有序对集合”和“矩阵”之间的对应关系，后面所有内容都可以照着本文一步步推出答案。

1. 先把这个章节的骨架搭起来：关系到底在研究什么

很多人一上来就背“自反、对称、传递”的定义，背得滚瓜烂熟，做题还是懵。原因是这三条性质不是孤立的三个定义，它们都是对“关系里有没有某种必备的有序对”做的检查。关系是一个集合，里面装的是有序对；关系性质就是在问：这个有序对集合够不够“整齐”。

1.1 关系的三种核心性质：定义不难，难在怎么用

设关系 R 是集合 A 上的关系。自反性说的是每个元素 a 都必须和自身有关系，也就是 (a,a) 都要在 R 里；对称性说的是只要 (a,b) 在，那 (b,a) 也必须要在；传递性说的是只要 (a,b) 和 (b,c) 都在，那 (a,c) 就必须也在。这三个定义单独拿出来都很好懂，但放进关系矩阵看，各有各的明显特征。

传递性的矩阵判断需要多说一句。关系矩阵 M 做一次布尔乘法得到 M²，其中 M²[i][j] 等于 1，表示存在某个中间节点 k，使得 i 能到 k，k 又能到 j，也就是存在长度为 2 的路径。传递性要求：只要存在这种两段路径，就必须存在一条“直达路径”。所以判断传递性，本质上就是在检查 M² 的每个 1 是否在 M 里同样也是 1。这个说法用代码来表达就是M²[i][j] == 1 ⇒ M[i][j] == 1，等价于 M 包含 M²。

这里有一个容易被忽略的边界情况：当集合 A 是空集时，空关系被认为具有自反性，因为定义里的“每个元素”一个都不存在，命题为空真。考试很少考到这个极端情况，但如果是做判断题，看清集合是否为空很重要。

1.2 闭包到底在干什么：从“有缺陷”到“完备”

闭包这个名字听起来抽象，实际就是一个“补丁”操作。已知关系 R 可能不自反、不对称、不传递，闭包就是在不删除 R 里任何原有有序对的前提下，往里面加最少的边，让 R 变得自反、对称或传递。

举个例子。假设关系是“朋友推荐”，1 认识 2，2 认识 3，但 1 不直接认识 3。如果题目要求这个关系具备传递性，就必须补上一条 1 到 3 的关系；但补的时候不能乱补，比如 3 到 1 不一定需要，要看是什么闭包。所谓“最小”，就是只补到刚好满足性质为止，多余的一条都不能加。

教材上给出了三个公式：自反闭包记作 r(R)，等于 R ∪ I_A，其中 I_A 是恒等关系，相当于把主对角线全部置 1；对称闭包记作 s(R)，等于 R ∪ R⁻¹，也就是把反向边全部补上；传递闭包记作 t(R)，等于 R ∪ R² ∪ R³ ∪ …，一直到 R 的 n 次幂。用“所有包含 R 且满足某性质的关系做交集”也能定义闭包，交出来的那个最小关系就是闭包。这个定义保证了唯一性，也让“最小”两个字有了严格的数学含义。

2. 判断性质之前，先让矩阵和关系对上号

做关系的习题，最忌讳只看文字不发散到矩阵或关系图。关系本身是有序对集合，关系矩阵和关系图只是它的两种等价表达。三种表达各有用处：文字直观但难做计算，矩阵适合机器运算和公式推导，关系图适合检查路径类问题。

2.1 三种表达方式互换：有序对、关系矩阵、关系图

后面所有例题我都会用同一个关系，先把基础打牢。设集合 A = {1, 2, 3, 4}，关系 R 用有序对表示是：

R = {(1,2), (2,3), (3,4), (4,1), (1,4)}

换成关系矩阵，行为起点，列为终点：

原始矩阵 R 1 2 3 4 1: 0 1 0 1 2: 0 0 1 0 3: 0 0 0 1 4: 1 0 0 0

矩阵第 1 行第 2 列为 1，表示 (1,2) 在关系里；第 1 行第 4 列为 1，表示 (1,4) 在关系里。整个关系图就是四条边：1→2，2→3，3→4，4→1，另外还有一条 1→4。画成有向图后，传递性问题可以直接从“有没有两条箭头首尾相接，却没有对应第三条捷径”来判断。

三种表达互转的方法并不复杂：从有序对集合画矩阵，逐对打勾；从矩阵读有序对，找所有值为 1 的位置；从矩阵画关系图，每个 1 就是一条有向边。做题时我自己的习惯是先把矩阵写出来，因为后面求闭包、跑 Warshall 全都要依赖矩阵，只盯着有序对集合容易漏。

2.2 自反、对称、传递的快速判定套路

用上面的 R 来走一遍完整判定流程。

自反性：看主对角线。R 矩阵第一行第一列是 0，说明 (1,1) 不在关系里，所以 R 不自反。哪怕只有对角线一个位置不是 1，自反性也不成立。

对称性：检查矩阵是否沿主对角线对称。看 (1,2) 在矩阵第 1 行第 2 列为 1，但第 2 行第 1 列是 0，说明 (2,1) 不在关系里，所以 R 不对称。这里要特别提醒：对称和反对称不是非此即彼的关系。一个关系可以既对称又反对称，比如只含自环的关系；也可以既不满足对称又不满足反对称，比如只含一个 (1,2) 的关系。判断时一定分清楚两个概念各自的条件。

传递性：检查所有长度为 2 的路径。1→2→3 是一个两段路径，那么必须有 1→3，可是矩阵第 1 行第 3 列是 0，所以 R 不传递。通过计算 M² 也能得到同样结论。自己刷题时，最稳的方法是逐行找“从 i 能一步到 k”，再找“从 k 能一步到 j”，然后确认 M[i][j] 是否为 1。这个过程就是手工版布尔乘法。

3. 三种闭包一次讲透：会用公式，更要会“最小构图”

闭包题看起来花样多，其实每个闭包都有固定的操作模板。自反闭包和对称闭包属于送分题，传递闭包才是拉开差距的地方。这一节先用同一个 R 求出三种闭包，再看传递闭包的几种求法。

3.1 自反闭包与对称闭包：对角线置 1 与“对称化”

自反闭包 r(R) 要做的事只有一个：把所有缺失的自环补上。公式是 R ∪ I_A，操作上就是把矩阵主对角线全部改成 1，其他位置原封不动。原关系里如果已经有 (a,a)，保持 1 即可，不会造成重复。R 的 r(R) 如下：

r(R) 1 2 3 4 1: 1 1 0 1 2: 0 1 1 0 3: 0 0 1 1 4: 1 0 0 1

对角线上全部是 1，其他位置的 1 和原来完全一致，没有多补一条边。

对称闭包 s(R) 要做的是把所有反向边补上。公式是 R ∪ R⁻¹，操作上就是把矩阵和它的转置做一次“或”运算。R 里有 (1,2) 但没有 (2,1)，所以补 (2,1)；有 (2,3) 没有 (3,2)，补 (3,2)；有 (3,4) 没有 (4,3)，补 (4,3)；R 里已经有 (4,1) 和 (1,4)，所以这一对不用补。

s(R) 1 2 3 4 1: 0 1 0 1 2: 1 0 1 0 3: 0 1 0 1 4: 1 0 1 0

这个矩阵明显沿主对角线对称。注意事项就一条：闭包只加边，绝不删边。如果原来 R 里某个 1 在求闭包后变成 0，那一定是算错了。

3.2 传递闭包的三种求法：从定义式到 Warshall

传递闭包 t(R) 的教材定义是 R ∪ R² ∪ R³ ∪ … ∪ Rⁿ。其中 R^k 表示经过 k 条边的路径关系。为什么最多到 n 次幂就够？因为集合只有 n 个元素，如果一条路径长度不小于 n，中间必然会经过重复节点，去掉中间环后可以得到更短的路径；所以超过 n 步的路径不会产生新的“可达对”。

第一种求法就是按定义硬算。对每个 k 算一次布尔矩阵乘法，然后把结果合并起来。这种方法适合节点很少的题，比如 3 个或 4 个节点，手算还能接受。对于我们的 R，R² 会包含 (1,3)、(1,1)、(2,4)、(3,1)、(4,2)、(4,4) 等边；不断乘下去，最终因为 1→2→3→4→1 形成一个大环，任意两个节点都互相可达，所以 t(R) 会变成全 1 矩阵。

第二种求法是画图看可达性。从每个顶点出发做一次遍历，凡是能到达的节点都置 1。这种方法直觉上最清楚，缺点是节点一多就容易画乱，不适合作为正规答题步骤。

第三种就是 Warshall 算法。它本质上还是在求所有可达对，但用一种特别适合矩阵“就地更新”的方式，迭代 n 轮后直接得到传递闭包。这也是考试和编程题里最常考的方法，下一节专门展开。

4. Warshall 算法手把手推导：4 个节点的完整推演

很多同学背 Warshall 伪代码背得很熟，一到让解释原理就卡住。其实它的核心想法只有一句话：依次允许 1 号、2 号、3 号……作为中转节点，逐步把间接路径“压缩”成直接路径。

4.1 算法的核心想法：用 k 当中转站

如果存在一条 i 到 j 的路径，路径中间可能经过很多节点。Warshall 的思路是让 k 从 1 到 n 依次“开放”。第 k 轮的意思是：在当前允许使用前 k 个节点作为中转的条件下，重新计算所有直接可达关系。实现上，只要第 i 行第 k 列为 1，也就是 i 能到 k，那么 i 就能顺着 k 到达 k 能到达的所有节点，所以把第 k 行逐位“或”到第 i 行上。

伪代码可以写成：

for k in range(n): for i in range(n): if matrix[i][k] == 1: for j in range(n): matrix[i][j] = matrix[i][j] or matrix[k][j]

外层必须是 k。每次处理时用到的 matrix[k][j] 是上一轮更新后的值，这正是算法高效的原因：允许中转的节点集合是逐步扩大的，前面几轮已经处理过的间接路径会在这一轮继续发挥“桥梁”作用。复杂度是 O(n³)，但实现非常简单，而且可以直接在原矩阵上改，不需要额外开一个大矩阵。

4.2 完整推演：从第一轮到最后一轮

用前面同一个 R 做 Warshall。初始矩阵再写一遍：

k = 0（初始矩阵） 1: 0 1 0 1 2: 0 0 1 0 3: 0 0 0 1 4: 1 0 0 0

k = 1：只看第 1 列。第 4 行第 1 列为 1，所以把第 1 行“或”到第 4 行上。第 1 行是 0 1 0 1，第 4 行原本是 1 0 0 0，逐位取或后变成 1 1 0 1。矩阵更新为：

k = 1 之后 1: 0 1 0 1 2: 0 0 1 0 3: 0 0 0 1 4: 1 1 0 1

这一步的意义是：4 能到 1，而 1 能到 2 和 4，所以 4 也能到 2，也能到 4。注意这里 4→4 是 1 到 4 的传递，不是自反性，不能和自反闭包混淆。

k = 2：只看第 2 列。当前第 1 行第 2 列为 1，第 4 行第 2 列也为 1。先处理第 1 行：第 1 行“或”上第 2 行。第 1 行是 0 1 0 1，第 2 行是 0 0 1 0，结果是 0 1 1 1。再处理第 4 行：第 4 行是 1 1 0 1，第 2 行是 0 0 1 0，逐位取或后变成 1 1 1 1。矩阵更新为：

k = 2 之后 1: 0 1 1 1 2: 0 0 1 0 3: 0 0 0 1 4: 1 1 1 1

现在第 4 行已经全 1，说明从 4 出发能到所有节点。

k = 3：只看第 3 列。当前第 1 行第 3 列为 1，第 2 行第 3 列为 1，第 4 行第 3 列也为 1。依次看：

• 第 1 行：0 1 1 1，“或”上第 3 行 0 0 0 1，结果还是 0 1 1 1；
• 第 2 行：0 0 1 0，“或”上第 3 行 0 0 0 1，变成 0 0 1 1；
• 第 4 行：已经是 1 1 1 1，再“或”上第 3 行不变。

k = 3 之后 1: 0 1 1 1 2: 0 0 1 1 3: 0 0 0 1 4: 1 1 1 1

第 2 行在第 3 轮补上了 2→4，因为 2 能到 3，3 能到 4。

k = 4：只看第 4 列。现在第 1 行、第 2 行、第 3 行、第 4 行的第 4 列全是 1，每一行都要“或”上第 4 行。第 4 行是全 1，所以把所有行全部变成全 1：

k = 4 之后（最终传递闭包 t(R)） 1: 1 1 1 1 2: 1 1 1 1 3: 1 1 1 1 4: 1 1 1 1

这个结果和用 R ∪ R² ∪ R³ ∪ R⁴ 算出来的结果完全一致。因为原关系里 1→2→3→4→1 构成强连通，所以整个集合任意两点互相可达，传递闭包自然是全 1。

4.3 手算与编程技巧：少踩坑，跑得快

手算 Warshall 有一个非常省事的流程：第 k 轮只扫描第 k 列，把这一列中所有值为 1 的行号记下来；对这些行，逐位和当前第 k 行做“或”运算。其他的行完全不用动。这样能减少漏算。

常见的手算错误有两个。第一个是用了旧矩阵，没有就地更新。Warshall 要求每一轮都在上一轮的结果上继续，如果回到初始矩阵重新计算，结果会少很多传递边。第二个是只处理第 k 行本身。有的同学以为第 k 轮只改第 k 行，实际上要看第 k 列，改的是那些“能到达 k 的行”。顺序一错，结果必然不对。

编程实现时我习惯用 Python 先快速验证：

def warshall(matrix): n = len(matrix) t = [row[:] for row in matrix] for k in range(n): for i in range(n): if t[i][k] == 1: for j in range(n): t[i][j] = t[i][j] or t[k][j] return t M = [ [0, 1, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0] ] for row in warshall(M): print(row)

运行结果就是四个全 1 的列表。我刷题时常用这个函数核对笔算答案，确认无误后再把推理过程写在草稿纸上。注意程序里的t[i][k]用的是当前更新后的矩阵，不能提前把第 k 行复制出来，否则结果和真正的 Warshall 不一致。

5. 常见错误与排查技巧：刷题避坑清单

闭包和 Warshall 的题目出错率非常高，而且错误模式很集中。下面这几类是我在实际辅导中反复看到的，每个都值得单独记一笔。

5.1 五个高频错误，每一个都很典型

第一个错误：判断自反性时只看“有没有自环”，不是看“每个元素都有自环”。比如关系里有 (1,1) 和 (2,2)，少了 (3,3)，它依旧不自反。自反性的要求是全部，不是存在。

第二个错误：把对称和反对称当成互斥关系。对称要求 (a,b) 在时 (b,a) 也必须在，反对称要求 (a,b) 和 (b,a) 不能同时存在除非 a=b。空关系既满足对称也满足反对称，对角线关系同样如此。一个关系可以同时两者都是，也可以两者都不是，这和直觉不太一样。

第三个错误：判断传递性只检查一组两跳路径。比如发现 1→2 和 2→3，检查了 1→3 存在就以为万事大吉。传递性要求的是所有长度为 2 的路径都必须有对应的第三条边，只要漏掉一组 (x,y),(y,z)，哪怕只有一组，传递性就不成立。还有更隐蔽的情况：如果 (1,2) 和 (2,1) 都在，那么 (1,1) 和 (2,2) 也必须都在，这种两跳回到起点的情况非常容易漏。

第四个错误：求传递闭包时用了算术矩阵乘法。R 的平方用布尔乘法，得到的矩阵只保留 0 和 1，不是把路径数相加。如果算出来矩阵里出现大于 1 的数字，说明用了普通乘法，需要立即纠正。

第五个错误：Warshall 的外层循环写错。外层必须是 k，不能是 i。外层循环一旦变成 i，算法就退化成一轮处理完所有中间节点，结果会漏掉大量传递关系。另外一个常见问题是同时求多个闭包时分不清顺序。如果题目要求先求对称闭包再求传递闭包，和先求传递闭包再求对称闭包，结果可能不一样，比如只有 (1,2) 的关系，s(t(R)) 和 t(s(R)) 就会差出两个自环。所以做题时第一步要看清楚闭包顺序。

5.2 结果自查：怎么判断算出来的闭包对不对

闭包题做完后，可以用三条规则快速自检。

第一条是“包含性”：原关系 R 中每一个 1，在闭包矩阵中必须仍然为 1。闭包只添边，不删边，看到任何一个原边丢失就可以直接判错。

第二条是“性质满足性”：算出的是自反闭包，就一定要检查主对角线全为 1；算出的是对称闭包，矩阵必须沿主对角线对称；算出的是传递闭包，就用 M² ≤ M 检查传递性。性质不满足，闭包一定不对。

第三条是“最小性”：新增的每个 1 都必须是“不得不加”的。自反闭包只能补对角线，对称闭包只能补反向边，传递闭包只能补两段路径对应的直达边。如果发现补了一条和性质无关的边，那整个闭包就大了，不是最小闭包。

此外，计算 t(R) 后可以用图遍历法复查。对每个节点做一次 BFS 或 DFS，把所有能到达的节点收集起来，和矩阵里的 1 做对照。这种验证方式虽然慢，但写题时能让人安心。

5.3 代码验证：把 Warshall 和闭包公式组合起来

如果题目要求同时求多种闭包，可以写一个简单程序做辅助，但核心逻辑要清楚。自反闭包就是把对角线全部改 1，对称闭包是矩阵与转置做或，传递闭包用 Warshall。下面这段代码把三种闭包放在一起，用于刷题验证很方便：

def reflexive_closure(M): n = len(M) t = [row[:] for row in M] for i in range(n): t[i][i] = 1 return t def symmetric_closure(M): n = len(M) t = [row[:] for row in M] for i in range(n): for j in range(n): if M[i][j] == 1: t[j][i] = 1 return t def transitive_closure(M): return warshall(M)

用程序验算时，我通常会故意把某个数据改成不对称、不自反的形态，确认函数确实会补边，而不是简单地原样返回。这样能避免因为测试用例选得太特殊而误判代码正确。

6. 最后分享一点个人体会

我自己的学习习惯是：碰到关系性质的题目，先画有向图，再写矩阵。画图能让我一眼看到两段路径，矩阵能让我准确执行 Warshall。判断传递性的时候，我不用眼睛乱扫，而是老老实实把所有长度为 2 的路径列一遍，逐条检查有没有对应的直达边。算闭包时，我会先想“哪些边是不得不补的”，再动手补，而不是拿起公式就盲目合并。

Warshall 我一开始也只是背流程，后来把一个 4 节点的小例子在纸上完整跑了三遍，才真正理解“k 当中间节点”的含义。理解了这一点之后，即使考试时忘记伪代码，也能现场推出来。这个方法后来在学图论、编译原理里的可达性分析时同样用得上，算是离散数学里少数学完还能反复复用的技能。如果你现在卡在 Warshall 上，别急着背代码，把本文那个 4 节点例子自己在草稿纸上走两轮，你会有一种突然通透了的感觉。