离散数学的关系这一章很多同学都是上课听懂了做题就懵。教材上自反、对称、传递三个性质各占一两行看起来无比清晰可一旦面对具体的关系矩阵和关系图各种犹豫全冒出来了。闭包更是重灾区自反闭包、对称闭包还好说传递闭包一出现不少人就开始怀疑人生——为什么要一遍遍复合Warshall算法更是被当成背代码题来对待循环嵌套记住就完事了完全没搞清楚它到底在解决什么问题。这篇习题解析是关系专题的第二篇接着上一篇的内容往下走。上一篇我们把关系的基本概念、关系的表示方式集合、矩阵、关系图和关系的复合运算过了一遍这一篇直接进入关系专题里最核心、也是考试占比最重的几个考点三种基本性质的判定、闭包构造、以及Warshall算法。这一篇重点解决三件事一是把自反、对称、传递三种基本性质的判定标准彻底理清列出最容易踩的坑二是讲明白闭包为什么存在、每一种闭包到底怎么构造三是把Warshall算法的原理、手算过程和代码实现串在一起让你不只是会背步骤而是真的知道每一步在干什么。适合正在学离散数学、准备期末考试的在校同学也适合需要快速回顾这部分内容的考研复习党。1. 三种基本性质判定标准与常见混淆1.1 自反性每个点都得有自己到自己自反性的定义只有一句话对任意a∈A都有(a,a)∈R。但这句话在实际判定时经常被理解歪。先看判定标准。从关系矩阵的角度看自反性等价于矩阵主对角线上的元素全部为1。注意是全部不是存在。从关系图的角度看每个顶点都必须有自环。我在改作业时见过最多的错误就是看到某个关系里有(1,1)、(2,2)就说它是自反的完全没注意到集合A里还有一个3而(3,3)并不在关系里。所以拿到一道自反性判断题第一步一定是把集合A的所有元素列出来逐个检查(a,a)是否都在R中。另外有一个很容易被忽略的点空集关系是不是自反的答案是当A为空集时空关系自反当A非空时空关系不自反。这个边界条件在选择题里出现过不少次原理其实很简单——自反性要求对任意a∈A如果A为空那这个任意是空真成立只要A里有一个元素就必须有对应的(a,a)空关系显然没有。还有一个概念要打包记住反自反。反自反要求对任意a∈A都有(a,a)∉R。这里有个经典误区很多同学以为不自反就是反自反这俩根本不是非此即彼的关系。举个例子A{1,2,3}R{(1,1),(1,2)}这个关系既不自反缺(2,2)和(3,3)也不反自反因为有(1,1)。所以判定的时候要分清楚题目问的是自反还是反自反问的是是否自反和是否满足反自反是两个不同的命题。1.2 对称性与反对称性一对容易吵架的兄弟对称性的定义是若(a,b)∈R则(b,a)∈R。判断对称性时矩阵视角非常好用如果关系矩阵关于主对角线对称即对任意i、j都有M[i][j] M[j][i]那这个关系就是对称的。用关系图看更直观任何两个不同顶点之间如果有一条有向边那就必须有反向的另一条有向边。这里我必须强调一个特别容易混的点对称和反对称并不是互斥的。反对称的定义是若(a,b)∈R且(b,a)∈R则一定有ab。翻译成人话就是关系里可以出现(a,a)但绝不允许出现a≠b时(a,b)和(b,a)同时存在。所以一个关系完全可以既对称又反对称——这样的关系只能是恒等关系I_A的子集也就是说里面只能含有(a,a)这种有序对。举个例子A{1,2}R{(1,1),(2,2)}它是不是对称的检查所有出现的有序对都是自己到自己逆元也就是自己所以对称。它是不是反对称的检查有没有a≠b且两个方向的边同时存在没有所以也是反对称的。这个结论在判断题里频繁出现最好直接记住空关系、恒等关系、以及恒等关系的任意子集都是既对称又反对称的。我自己的一个小习惯是判断对称性用矩阵扫一眼是不是对称矩阵就完事判断反对称性用关系图检查有没有一对反向平行边不包括自环。这个组合拳速度快而且不容易出错。1.3 传递性隐藏最深的那个性质传递性是三种性质里最麻烦的一个也是考试丢分的重灾区。定义是若(a,b)∈R且(b,c)∈R则(a,c)∈R。注意这里的关键点是中间元素b必须存在而且我们要对集合里的所有可能的b都做检查。很多同学判断传递性时只看相邻的元素这是最大的坑。比如A{1,2,3}R{(1,2),(2,3)}很多人觉得有1到22到3那就有传递——但实际上这个关系是不传递的因为(1,2)和(2,3)存在需要(1,3)却没有。类似地A{1,2,3}R{(1,2)}大家觉得只有一个关系应该不传递吧其实它是传递的因为它根本不存在某个a到b、同时b到c的组合无从验证命题空真成立。这个空真的理解直接决定了传递性的判断对不对。从关系图的角度看传递性等价于任意一条长度为2的路径都必须存在一条捷径长度为1的边连接起点和终点。换句话说不允许出现两步能走通但一步走不通的情况。这个视角在解题时特别实用尤其是给关系图让你判断性质的题型直接找有没有断头两步路就行。还有一个验证技巧一个关系R是传递的当且仅当R∘R⊆R也就是R²包含于R。这个充要条件在证明题里经常用到后面我们在习题部分会实际推一遍。2. 闭包给关系打补丁的正确姿势2.1 闭包的定义到底在说什么我们先想一个问题为什么需要闭包这个东西在现实中我们拿到的关系往往是残缺的——它可能不自反、不对称、不传递。但很多场景下我们希望它具备某个性质。比如可达性本质上要求传递如果已知A能到B、B能到C但关系里没有直接给出A到C我们就希望补上这条边。闭包的定义包含三个条件第一R⊆R第二R具有性质P第三对于任何包含R且具有性质P的关系R都有R⊆R。第三条是最小性翻译成人话就是R是在不丢失R中已有关系的前提下为了获得性质P而需要添加的最少的有序对。记住这一点很重要因为题目一旦问求自反闭包本质就是让你找那个最小的自反超关系。有个生活化的类比你有一份不完整的通讯录要求是每个人都必须能联系到自己。自反闭包就是给缺失的每个人补上一条自己联系自己的记录别的什么都不动。对称闭包则是只要A联系了B那B也必须能联系A所以把漏掉的反向联系方式全补上。传递闭包更狠A能通过B联系C那就直接把A联系C也加上一直加到不能再加为止。这个类比你可以在脑子里留着做概念题时很有帮助。2.2 自反闭包与对称闭包直接并上去就对了自反闭包和对称闭包的构造非常直接公式分别是自反闭包 r(R) R ∪ I_A其中I_A是集合A上的恒等关系即I_A {(a,a) | a∈A}。对称闭包 s(R) R ∪ R⁻¹其中R⁻¹是R的逆关系即R⁻¹ {(b,a) | (a,b)∈R}。用矩阵来看更清楚。自反闭包把关系矩阵的主对角线全部置为1其他位置不变。对称闭包把矩阵和它的转置矩阵做一次逐元素的逻辑或运算写成公式就是M_{s(R)} M ∨ Mᵀ。为什么逻辑或就行因为如果某个位置原来就是1保留原来是0但转置位置是1说明对应的反向有序对存在需要补上两个位置都是0那当然维持0。这两个闭包很简单但有一个共同的要点不能删除或修改原有关系。自反闭包只需要加对角线哪怕R里已经有一个(a,a)也不需要额外操作对称闭包只需要补逆元不能因为添加了(b,a)就把(a,b)删掉。这些操作都是纯粹的加法。2.3 传递闭包为什么需要复合到无穷传递闭包的公式长这样t(R) R ∪ R² ∪ R³ ∪ ...。也就是说把所有正幂次的复合结果都并起来。很多同学第一次看到这个公式时是懵的为什么要把R的平方、立方甚至更高次都并起来用路径解释就通了。如果(a,b)∈R²说明存在某个c使得(a,c)∈R且(c,b)∈R即a可以通过两步走到b。为了让关系具备传递性a和b之间就必须补上一条直接边。同理(a,b)∈R^k说明a可以通过k步走到b。传递闭包要做的就是把所有通过有限步可到达的关系全部补上。问题来了到底需要复合到多少次才够这里有一个关键结论集合A有n个元素时t(R) R ∪ R² ∪ ... ∪ Rⁿ不少教材写的是并到第n次。原理是如果a能到达b那么存在一条从a到b的路径去掉其中的环路后路径上的顶点互不重复所以路径长度最多是n-1条边如果考虑回到自身的环并到n幂也不会出错因为多余项都已经被前面的并集覆盖了。所以有限集上计算传递闭包时不需要真的复合无限次最多并到n次幂就够了。在矩阵操作上传递闭包的计算就涉及到布尔矩阵乘法。布尔矩阵乘法和普通矩阵乘法逻辑类似但加法是逻辑或1∨11乘法是逻辑与1∧11。你可以把它想成找中间人C[i][j] 对所有的k判断是否存在一个k使得A[i][k]1且B[k][j]1。如果存在C[i][j]就是1。这一步是后面Warshall算法的基石一定要理解透。3. Warshall算法手算、代码与原理一次讲透3.1 算法思想动态规划式的中转点引入直接按照定义反复做布尔矩阵乘法再取并当然可以求出传递闭包但效率太低每做一次矩阵乘法就要三重循环乘完还要取并计算量很大。Warshall算法的价值就在于它用一种更聪明的顺序只做一轮三重循环就完成了传递闭包的计算。算法的核心思想是动态规划。我们定义这样一个状态W_k[i][j]表示从i到j是否存在一条路径使得路径上的所有中间顶点都来自前k个顶点按某种顺序编号。注意这里说的是中间顶点起点和终点可以是任意顶点但路径中经过的中间点只能从前k个里选。然后考虑递推W_k[i][j]怎么由W_{k-1}得到分两种情况。第一种情况从i到j的路径根本不需要经过第k个顶点那W_k[i][j]直接继承W_{k-1}[i][j]。第二种情况从i到j的路径需要经过第k个顶点那这条路径可以拆成两段先从i到k中间顶点只允许前k-1个再从k到j同样中间顶点只允许前k-1个。于是递推式就是W_k[i][j] W_{k-1}[i][j] ∨ (W_{k-1}[i][k] ∧ W_{k-1}[k][j])这个递推式是不是看着很眼熟对和Floyd算法的递推式结构一模一样只是把求最短路换成了判断是否可达。实际实现时可以原地更新因为每一轮k的更新只涉及第k行和第k列的读取而更新过程中第k行和第k列本身在这一轮不会因为被更新而改变该轮所需的信息。打个比方你往通讯录里加新朋友加的时候只需要用到旧通讯录里的信息不会出现刚加完又马上被当成旧信息读的混乱情况。3.2 完整手算演示一个4阶矩阵的逐步变化说一千道一万不如完整算一遍。我们取集合A{1,2,3,4}关系R的关系矩阵如下1 2 3 4 1 | 1 0 0 1 2 | 1 0 0 0 3 | 0 1 0 0 4 | 0 0 1 0先看一眼这个关系图1→42→13→24→3再加上1→1的自环。整条路径是2→1→4→3→2其实是一个大环1能直接到44能到33能到22能回到1。所以直觉上这个关系最终会把所有点都连通。我们用Warshall验证一下。第一轮k1也就是把顶点1作为允许的中间点。看第1列记住我们说的第1列对应顶点1哪些行的第1列是1第1行和第2行。于是拿第1行去或给这些行。第1行是[1,0,0,1]所以第1行不变第2行从[1,0,0,0]变成[1,0,0,1]。这时矩阵变成1 2 3 4 1 | 1 0 0 1 2 | 1 0 0 1 3 | 0 1 0 0 4 | 0 0 1 0这一步的含义是允许经过顶点1时2能到达4了因为2→1→4。第二轮k2允许中间点包含顶点2。看第2列哪些行的第2列是1只有第3行。于是拿第2行去或给第3行。第2行现在是[1,0,0,1]第3行从[0,1,0,0]变成[1,1,0,1]。矩阵变成1 2 3 4 1 | 1 0 0 1 2 | 1 0 0 1 3 | 1 1 0 1 4 | 0 0 1 0这一步的含义是允许经过2时3能到达1和4了因为3→2→13→2→1→4。第三轮k3允许中间点包含顶点3。看第3列哪些行的第3列是1只有第4行。于是拿第3行去或给第4行。第3行现在是[1,1,0,1]第4行从[0,0,1,0]变成[1,1,1,1]。矩阵变成1 2 3 4 1 | 1 0 0 1 2 | 1 0 0 1 3 | 1 1 0 1 4 | 1 1 1 1第四轮k4允许所有中间点。看第4列哪些行的第4列是1第1、2、3、4行全是1。于是把第4行[1,1,1,1]分别或给所有这些行。结果所有行都变成全11 2 3 4 1 | 1 1 1 1 2 | 1 1 1 1 3 | 1 1 1 1 4 | 1 1 1 1最终矩阵全1传递闭包t(R)就是A×A。回头再看关系图因为所有点都在同一个环上绕一圈总能从任意点走到任意点所以这个结果是完全合理的。通过这个例子你可以直观感受到Warshall算法逐步放开中间点限制的传播过程。3.3 Python实现、复杂度分析与使用注意Warshall算法的代码非常简单几行就能写完。这里给出一个Python实现def warshall(M): 输入n阶0-1矩阵M表示关系R的矩阵 输出传递闭包的矩阵原地修改并返回 n len(M) # 复制一份避免直接改动原始矩阵 R [row[:] for row in M] for k in range(n): # k是允许的中间点编号 for i in range(n): # i是路径起点 if R[i][k] 1: # i能到k才能借助k转发 for j in range(n): # j是路径终点 R[i][j] R[i][j] or R[k][j] return R三个嵌套循环时间复杂度是O(n³)空间复杂度O(n²)。对于n几百甚至上千的稠密关系矩阵这个算法完全够用代码本身也不容易出错。但我提醒一个细节在写代码判断if R[i][k] 1时很多初学会写成if R[k][i] 1这就是行列搞反了。R[i][k]的意思是从i出发能到达kk是中间点而R[k][i]是从k出发能到达i完全不是一回事。画一下关系图或者在心里默念起点在前终点在后就不会写反。另外一个常见疑问是Warshall算法求出来的是传递闭包不是自反传递闭包。也就是说对角线上的元素不会自动变成1。如果你需要自反传递闭包有两种做法要么在初始矩阵里把对角线全部置1再跑Warshall要么跑完之后再和单位矩阵做逻辑或。这个点很多教材没有特别强调但考试判断题非常爱出。4. 典型习题实战从判断题到证明题4.1 性质判定一道综合题讲透判定流程我们用一个综合案例把它串起来。设A{1,2,3,4}关系R{(1,1),(1,2),(2,3),(3,4),(4,2)}判断R是否自反、对称、传递。自反性需要(1,1)、(2,2)、(3,3)、(4,4)全部在R中。现在只有(1,1)缺(2,2)、(3,3)、(4,4)所以R不自反。对称性检查每个有序对是否有逆元。R里有(1,2)需要(2,1)但(2,1)不在R中所以R不对称。这里只要找到一个反例就够了不需要把所有有序对全部检查完。传递性需要检查所有可能的两步路径。由于(1,2)∈R且(2,3)∈R按照传递性必须有(1,3)∈R但(1,3)并不在R中所以R不传递。注意一个逻辑上的不对称证明不满足只需一个反例但证明满足就必须对所有情况逐一验证。考试时如果判断结果是满足你最好在草稿纸上把检查过程写出来比如枚举所有中间元素b1,2,3,4逐一验证没有断头路。这既是严谨性的要求也能防止自己漏检。4.2 闭包计算手算传递闭包的完整过程继续用上面的关系R。先求自反闭包和对称闭包这两个很直接r(R) R ∪ {(2,2),(3,3),(4,4)} {(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(4,2),(4,4)}s(R) R ∪ {(2,1),(3,2),(4,3),(2,4)} {(1,1),(1,2),(2,1),(2,3),(2,4),(3,2),(3,4),(4,2),(4,3)}重点看传递闭包。按定义t(R) R ∪ R² ∪ R³ ∪ ...我们先求R²。R²包含所有这样的有序对(a,c)存在b使得(a,b)∈R且(b,c)∈R。逐个组合一遍(1,1)和(1,2)组合得到(1,1)、(1,2)(1,2)和(2,3)组合得到(1,3)(2,3)和(3,4)组合得到(2,4)(3,4)和(4,2)组合得到(3,2)(4,2)和(2,3)组合得到(4,3)所以R² {(1,1),(1,2),(1,3),(2,4),(3,2),(4,3)}。继续求R³ R²∘R也就是把R²中的有序对与R中的有序对再做一次复合。算完可以得到R³ {(1,1),(1,2),(1,3),(1,4),(2,2),(3,3),(4,4)}。细心的同学会发现这时新增了(1,4)、(2,2)、(3,3)、(4,4)。再算R⁴时会发现新产生的有序对全部已经出现在前面R、R²、R³的并集里不再产生新元素所以传递闭包收敛了。因此t(R) R ∪ R² ∪ R³写成矩阵形式为1 2 3 4 1 | 1 1 1 1 2 | 0 1 1 1 3 | 0 1 1 1 4 | 0 1 1 1这个结果很有规律原因也不难理解1是总开关能到2、3、4而2、3、4内部通过R的几条边互相连通所以在传递闭包里互相可达。你可以自己画一下关系图把这个结果和图中路径可达性对照一下会非常有感觉。4.3 证明题思路几个必须掌握的小证明证明题在闭包这个考点里也经常出现我拆两个最常见的证明思路。第一个经典结论如果R是自反且传递的则R² R。证明分两步。第一步证明R²⊆R因为R传递所以任意(a,c)∈R²都意味着存在b使得(a,b)∈R且(b,c)∈R由传递性可得(a,c)∈R所以R²⊆R。第二步证明R⊆R²因为R自反对任意(a,b)∈R(a,a)∈R于是(a,a)∈R且(a,b)∈R这说明(a,b)∈R²所以R⊆R²。两边一夹R²R得证。这个证明里自反性提供起点回环传递性提供路径压缩的分工一定要看清很多类似证明题都是这个套路。第二个要掌握的是传递闭包的性质t(R)确实是一个传递关系。证明思路是如果(a,b)∈t(R)且(b,c)∈t(R)那么(a,b)属于某个R^p(b,c)属于某个R^q那么(a,c)属于R^{pq}而R^{pq}在t(R)的定义并集里所以(a,c)∈t(R)。这个证明的核心就是把步数相加。同样你可以用这个思路去证明t(R)是包含R的最小传递关系无非是再证一下最小性——任何包含R的传递关系都必须包含所有R^k用归纳法就行。5. 常见错误与考点陷阱速查5.1 概念理解上的四个坑做题做到现在我把最常见的概念性错误整理成一张表希望你在复习时对照着自查。常见误区正确理解关系里存在(a,a)就说R自反集合A中每个元素都必须有对应的(a,a)不自反就等于反自反两者不互斥存在既不自反也不反自反的关系对称和反对称只能二选一既对称又反对称的关系完全存在空关系和恒等关系子集空关系不自反也不传递空关系恒对称、恒传递但A非空时不自反第4个坑要多说一句。空关系的传递性来自空真也就是不存在任何需要验证的路径。我在改卷时看到有同学判断空关系不传递理由是没有任何关系怎么传递——这恰恰是把数学命题的语义搞拧了。若p则q这种蕴含命题只要p为假整个命题就是真的。5.2 Warshall算法实操的易错点手算Warshall算法时最容易栽在下面几个地方。第一是行列反了。判断i到k是否可达要查的是第i行第k列也就是M[i][k]不是M[k][i]。很多同学在纸面上写的时候第k行算着算着就串行了。我的建议是用起点在左中间点在右的口诀来记每次更新前先在心里标出我现在的起点是i中间点是k。第二是内层循环的范围。标准写法中j必须从0循环到n-1不能只循环到k。因为把第k行或到第i行时第i行的每一个位置都可能被影响包括那些编号小于k的列。如果只更新一部分列就会漏掉路径导致结果错误。第三是原地更新的理解。实现时可以原地更新矩阵这也是Warshall算法的特点但很多人在手动模拟时容易被刚更新的行要不要再参与本轮更新弄糊涂。其实规则很清楚每轮k的更新只用第k行去更新其他行而第k行本身在这一轮不会被其他行更新。所以你只需要关注哪些行的第k列是1把这些行分别和第k行做逻辑或。按这个规则一步一步来就不会乱。第四是别忘了传递闭包不自动加自反边。比如集合A{1,2,3}R{(1,2),(2,3)}R的传递闭包是{(1,2),(2,3),(1,3)}里面并没有(1,1)、(2,2)、(3,3)。如果你需要自反传递闭包一定要手动把对角线补上。5.3 备考复习建议离考试不远时这部分内容怎么快速复习我给一个自己的操作清单。性质判断先画关系图然后用眼睛检查自环自反性、平行反向边对称性、断头两步路传递性。如果关系比较复杂就用矩阵辅助。一定要把判断不满足只需一个反例判断满足必须全查这个观念刻在脑子里。闭包计算自反闭包和对称闭包直接套公式几秒钟搞定。传递闭包优先用Warshall算法因为它不容易漏。但如果关系图很稀疏、路径短直接枚举路径反而更快。我自己考试时常用两种方法互验先用Warshall算再用路径法检验几个关键点。Warshall算法手算熟练度很重要。建议找3-4个不同形态的矩阵练手尤其是包含环状路径的矩阵和链状路径的矩阵感受一下每轮更新的传播波。练熟了你会发现这个算法其实就像推多米诺骨牌一轮一轮地把可达性向远处推。我在实际给学生讲这部分内容时最深的体会是凡是能把Warshall算法中间点逐步放开这个动态规划思想真正看透的同学后面学图论里的Floyd算法几乎不用再费力气两者本质上是同一个思维框架。所以不要只顾着背代码多花点时间想清楚每一轮k到底在做什么。最后再分享一个小技巧手算Warshall时每更新完一轮停一下看一眼矩阵发生了什么变化想想这些新出现的1对应关系图中的哪条新路径。你会在这种观察里逐渐建立起对关系闭包的直觉而这种直觉恰恰是考试时又快又准的真正底气。