离散数学期末拿分顺序：关系矩阵、传递闭包与图论证明模板

简介面向计算机及相关专业本科生、专升本与考研复习人群的离散数学期末备考材料以一份附答案与解析的期末试卷为核心帮助读者在考前系统检验集合论、数理逻辑、图论、代数结构与格论等模块的掌握程度。压缩包内共1个PDF文件约1.13MB完整呈现填空、选择、证明与逻辑推演四类题型并对对称差集合表达式、主合取范式、关系自乘R²、偏序哈斯图、补图与自补图、二元运算的幺元与逆元、双射函数判定、图中长度为3的通路计数、树中4度结点求解以及彼得森图非平面性证明等考点给出对应答案与思路批注。已有3414人学习适合用于期末冲刺自测、对照订正错题也便于教师取用为课堂练习与讲评素材。1. 离散数学期末怎么考从填空选择到证明计算的拿分顺序离散数学期末考试题最怕的不是难题而是题型杂、定义多、会做却漏条件。集合论、关系、图论、代数结构、数理逻辑五块基本都会出现填空选择盯定义和反例证明题考性质推导计算题考关系矩阵、传递闭包、通路数与度数方程。附答案和含解析的卷子价值在于把每一步为什么成立写出来适合已经过完一遍教材、需要按考点查漏的人。拿分顺序建议先稳集合与逻辑小分再做关系矩阵和度数方程最后攻图论证明与群同态。每题先写定义再动笔哈斯图、补图、传递闭包都要留检查步骤。下面按考点模块拆开把高频题和答题模板直接落到笔头。2. 集合论与关系对称差、关系矩阵、传递闭包三类题的固定打法集合与关系是整张卷子的地基。填空里常出现文图阴影的集合表达式选择里常考二元关系个数、关系性质在复合下是否保持计算题则容易出关系矩阵和传递闭包。这一块的题不难但特别吃“定义有没有写全”。对称差、主合取范式、关系矩阵布尔乘法都是出题人喜欢设小坑的位置。答题时先把符号翻成元素归属再按矩阵或集合逐项核对比凭感觉画图稳。2.1 集合运算与主合取范式先化符号再验边界文图阴影题的第一步不是猜答案而是把阴影拆成“在哪些集合里、不在哪些集合里”。题目给出 A、B、C 三个集合阴影部分对应 B 与 C 的对称差再去掉 A写成(B⊕C)-A。对称差的定义是B⊕C(B-C)∪(C-B)也就是只属于 B 或只属于 C 的元素再减去 A等价于(B∪C)-(B∩C)-A。答题时建议在草稿上列四个区域只在 B、只在 C、B 与 C 都在、都不在再对照阴影。这样不容易把对称差写成并集或交集。主合取范式的题常以填空出现。主合取范式是若干极大项的合取每个极大项对应真值表里使公式为假的赋值变量取 0 时写原变量取 1 时写否定与主析取范式的取法相反。答题模板是先列真值表圈出成假行每行写一个极大项行内变量按“0 原、1 否”写最后把极大项用合取连接。检查时把得到的主合取范式代回一组成假赋值结果应为 0代回成真赋值结果应为 1。论域只有一个元素时量词题反而简单。设论域D{c}则∀xP(x)与P(c)同真值∃xP(x)也与P(c)同真值。题目给出解释 I 下真值为 1往往就是在考“全称和存在在单元素论域下退化成同一个命题”。这类填空不要展开长篇推理写清“论域单元素量词消去后看 P(c)”即可。若涉及多个量词按由外到内逐个消去别跳步。集合相等选择题要抓住“元素无序、重复不计、空集也是元素”。例如{4,3}与{3,4}相等{4,∅,3,3}去重后还是{4,∅,3}。答题时先去掉重复元素再看两边元素是否互相属于。含空集符号时尤其注意∅是一个元素还是空集本身取决于它出现在花括号内还是外。出题人常把{∅}和∅放在一起看到这种题先数括号层级。2.2 关系性质与关系矩阵自反、对称、传递逐项核对集合 A 上的二元关系个数是高频选择。若|A|n有序对共有n^2个每个有序对可选“在关系里”或“不在关系里”所以关系总数是2^(n^2)。A{1,2,3} 时是2^9512。选项里常出现2^3、3^2这类干扰项记法是“有序对个数做指数底数是 2”。答题时先写有序对总数再写指数别直接背数字。关系性质判断要按定义逐条看。自反每个x∈A都有x,x∈R反自反每个x,x都不在 R对称有x,y就有y,x反对称同时有x,y和y,x时只能xy传递有x,y、y,z就有x,z。选择题常问“R、S 都自反复合是否自反”。自反性在复合下保持因为x,x∈R且x,x∈S所以x,x∈R∘S。但反自反、对称、传递在复合下不一定保持答题时最好举一个小反例而不是只背结论。关系矩阵是这一块的計算核心。自反关系的矩阵主对角线全 1反自反主对角线全 0对称关系矩阵关于主对角线对称传递关系满足布尔乘法下M^2≤M即M^2中为 1 的位置在 M 中也必须为 1。题目给出关系图求R^2本质是找长度为 2 的路径从 i 到 j 有R^2边当且仅当存在 k使 i 到 k、k 到 j 都有 R 边。卷面答案R^2{(1,1),(1,3),(2,2),(2,4)}就是按“中间点 k”逐对找出来的。答题时先列邻接矩阵再按行扫中间点不要凭图直接猜。复合方向也容易翻车。R∘S通常表示先 S 后 R矩阵写法要按教材约定核对。遇到RS、SR的选项先看题目定义的是哪一种复合顺序再举一对具体元素验证。比如 R{3,3,6,2}、S{2,3}按先 S 后 R 可得6,3按先 R 后 S 则不同。答题时把复合顺序写在草稿上能避开大半错误。2.3 传递闭包计算矩阵乘法与布尔幂的合并传递闭包t(R)是包含 R 的最小传递关系。有限集 A 有 n 个元素时t(R)R∪R^2∪…∪R^n。计算时先求 R 的邻接矩阵 M再做布尔幂M^2,M^3,…,M^n最后逐位取“或”。布尔乘法与普通矩阵乘法的区别是加法用“或”乘法用“与”结果只取 0/1。下面这段 Python 把布尔乘法和闭包累加写在一起矩阵里的 1 表示有序对存在。def boolean_mul(A, B): n len(A) C [[0] * n for _ in range(n)] for i in range(n): for j in range(n): # 存在中间点 k使 i-k 与 k-j 同时成立则 i-j 成立 C[i][j] 1 if any(A[i][k] and B[k][j] for k in range(n)) else 0 return C def transitive_closure(M): n len(M) T [row[:] for row in M] # 先放入 R P [row[:] for row in M] # P 用来保存当前幂 for _ in range(1, n): # 最多累加到 R^n P boolean_mul(P, M) for i in range(n): for j in range(n): T[i][j] T[i][j] or P[i][j] return T M [ [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1], [0, 0, 0, 0] ] print(transitive_closure(M))这段代码里boolean_mul的any对应“存在中间点”T逐位累加对应集合的并。参数M是 n×n 的 0/1 邻接矩阵n是顶点数循环最多到 n 次因为长度为 n 以上的路径在有限集上不会产生新的传递边。输出矩阵中为 1 的位置就是t(R)的有序对。注意传递闭包不自动补主对角线除非原关系本身自反或题目明确要求自反闭包。很多失分是把t(R)写成了自反传递闭包多加了x,x。手算时建议按“幂次表”写先列 R再列 R^2再列 R^3每列完与前面并一次。若某次幂不再产生新有序对可以停止。答题纸上不要只写最终集合最好保留R^2、R^3的关键行证明不是抄答案。遇到矩阵较大时按行扫描中间点用“i 能到哪些 kk 能到哪些 j”列表比在图上乱画快。2.4 真题演练关系R^2与t(R)怎么不失分卷面给出 A{a,b,c,d} 上的关系 R要求用矩阵运算求传递闭包t(R)。这类题的答题骨架是四步写邻接矩阵、做布尔幂、逐次取并、按集合形式回写。以 R{a,b,b,c,c,d} 为例R^2{a,c,b,d}R^3{a,d}R^4为空所以t(R)R∪R^2∪R^3即{a,b,b,c,c,d,a,c,b,d,a,d}。回写时按字母顺序或按行顺序排列避免漏项。如果题目已经给出R^2的结果不要直接跳过矩阵。先把R^2的每个有序对解释成“存在中间点”再继续求R^3。例如a,c∈R^2说明存在 b 使a,b、b,c在 R 中求R^3时就把R^2与 R 复合。卷面上常见错误是只算到R^2就停或者把R^2中的a,c当成原关系继续做普通加法。检查方法是看最长链若关系像一条链 a→b→c→d传递闭包应补齐所有“前面到后面”的对共 6 个若答案少于链上可组合的对数就要回头补幂。关系图求R^2的题答题时可在图上标“两步可达”。从每个点出发走两步能到的点就写进R^2自己到自己若有两步回路也要写。题目给出R^2{(1,1),(1,3),(2,2),(2,4)}回写时按第一个坐标分组读卷更清楚。若要求t(R)再把R^2、R^3并进去。不要把R^2与R∘R的方向搞反也不要把布尔乘法的“或”写成普通加法后出现 2。3. 图论与偏序哈斯图、补图、通路数、树度数的得分模板图论在期末卷里通常是“选择 填空 证明”的组合。偏序关系看哈斯图和格补图看完全图边数通路数看邻接矩阵树看度数列方程欧拉图与哈密顿图看奇点和构造。这一块最怕把定义记混哈斯图不是关系图补图不是反向边欧拉回路不是哈密顿回路。答题时先写判定条件再套题目数据最后用一个小检查确认没有漏顶点或漏边。3.1 偏序关系与哈斯图自反闭包不要漏偏序关系要同时满足自反、反对称、传递。题目给出 A{a,b,c,d}偏序关系 R 的哈斯图后要求写出 R 的集合表达式。卷面答案把覆盖关系与自反对并在一起{(a,b),(a,c),(a,d),(b,d),(c,d)}∪{(a,a),(b,b),(c,c),(d,d)}。这里最容易漏的是自反对。哈斯图只画覆盖关系不画自反边也不画由传递性可推出的边但题目问“R”时R 是完整偏序必须把自反对补回去。画哈斯图的步骤是先去掉所有x,x再去掉可由传递性推出的边只保留覆盖关系然后按“小在下、大在上”分层连线不交叉。比如 a 小于 b、c、db 小于 dc 小于 d则 a 在最下层b、c 在中间d 在最上层a 连 b、a 连 cb 连 d、c 连 d。不要把 a 到 d 的传递边也画上否则哈斯图变成关系图。答题时用“覆盖”二字提醒自己只画没有中间元素的边。格的判定是偏序集里任意两个元素都有最小上界和最大下界。选择题给几个偏序集问“是格的为 c”答题时不要只看图形好不好看要逐对元素找上界集合和下界集合。若某一对元素没有最小上界或者有两个极小上界但不可比就不是格。常见非格图形是“V”形缺顶或“倒 V”形缺底两个元素有上界但没有最小上界。把每对元素的上下界列成小表比凭直觉可靠。偏序关系写集合时传递性容易补多。若 R 中有a,b、b,d传递闭包必须加a,d但若题目给的是哈斯图a,d可能已经在完整 R 中只是没画出来。反过来若题目只给覆盖关系要求写偏序 R就必须补自反和传递。答题时分两行写先写覆盖关系再写自反对最后合并去重。这样即使中间有错也能让阅卷看到思路。3.2 补图与自补图先补边再判断同构补图的定义是顶点集与原图相同边集由“原图没有的边”组成且不包含自环。若原图 G 有 n 个顶点、m 条边完全图 K_n 有n(n-1)/2条边则补图的边数是n(n-1)/2 - m。填空题给图求补图先数顶点、再数原边、再补边不要直接把原图边反向。无向图的补图里原图相邻的点在补图中不相邻原图不相邻的点在补图中相邻。答题时用“完全图减去原图边”这句话做检查。自补图是与其补图同构的图。判断自补图不能只看边数相等还要看结构是否同构。自补图若有 n 个顶点边数必须满足mn(n-1)/4所以 n 通常要满足n≡0或1 mod 4。但边数相等只是必要条件不是充分条件。答题时先算边数排除选项再尝试构造同构映射若题目只问“哪个是自补图”优先找顶点数 4 或 5 的小图画补图后比对连接关系。补图题的常见失分是把“补图”与“反向图”混了。有向图的补图不是把所有箭头反过来反向图是边方向取反补图是“完全有向图去掉原弧”或按题目定义补缺失的弧。期末卷里若无向图补图居多看到箭头要先确认题目定义。答题时把“顶点不变、缺失边补上、自环不补”写在草稿上能避免把补图边数算成原图边数。3.3 通路数与邻接矩阵长度3通路的计数法图中从 v1 到 v3 长度为 3 的通路数标准做法是写邻接矩阵 A计算A^3的第 1 行第 3 列元素。这里的矩阵乘法是普通乘法不是布尔乘法因为要数路径条数不同中间点要相加。若题目问“是否存在通路”才用布尔乘法问“有几条”必须用普通加法乘法。答题时先写邻接矩阵再手算A^2、A^3的目标元素不必把整个矩阵都算完。卷面题答案给 3 条并列出v1→v1→v1→v3、v1→v4→v1→v3、v1→v3→v1→v3。这三条路径说明图中允许重复顶点题目说的是“通路”而不是“简单路径”。若题目改成“简单通路”就不能重复顶点答案会变。答题时先看题目用词通路允许重复顶点和边简单路径不允许重复顶点基本路径通常不允许重复边。把词义写在草稿上能避免把 3 条算成 1 条。手算通路数可以用“分层扩展”从 v1 出发走一步能到哪些点第二步能到哪些点第三步落到 v3 的计数。每层写集合和次数最后汇总。若图有自环自环会让路径数增加不要忽略。矩阵法的好处是每步都有记录检查时看A^3的目标位置是否等于各条路径之和。答题纸上写“长度为 3 的通路数等于 (A^3)13”阅卷能直接看到方法分。3.4 树与度数列方程顶点数边数1的硬约束树的核心关系是顶点数边数1即ve1。结合握手定理Σdeg2e可以解度数类填空题。卷面题一棵树有 7 片树叶、3 个 3 度结点其余都是 4 度结点问 4 度结点有几个。设 4 度结点为 n则顶点数v73n10n边数ev-19n。度数和为7×13×34n164n又等于2e182n解得n1。答案选 A。这个方程不复杂关键是树叶按 1 度算不是 0 度。树的叶子定义为度数为 1 的顶点只有单点树才是 0 度。题目说“7 片树叶”就写 7 个 1 度说“3 个 3 度结点”就写 3 个 3其余是 4 度设 n 个。方程列完先合并常数再移项。检查时把 n 代回v11e10度数和794202e成立。若算出的 n 不是整数或为负说明树叶或度数读错回头检查。树的选择题还常考“树至少两片叶子”“树无回路且连通”“任意两点唯一路径”。遇到“删除一条边是否仍连通”“加一条边是否成圈”这类题用ev-1和连通性判断。树中任意两点间路径唯一所以加一条非边必产生唯一回路删一条边必不连通。答题时不要画太多图先写树的等价定义再套选项。3.5 真题演练欧拉图、哈密顿图与平面图判定欧拉图判定看连通性和奇点。无向连通图存在欧拉回路当且仅当所有顶点度数为偶数存在欧拉路径当且仅当恰有 0 个或 2 个奇点。选择题问“既不是欧拉图也不是哈密顿图”先数每个顶点度数有奇点就不是欧拉图再看能否构造经过所有顶点一次的回路。哈密顿图没有像欧拉图那样简单的充要条件期末常考小图判断和必要条件。答题时先排除欧拉图再对剩下的图尝试找哈密顿回路找不到时用割点、割边或二部图奇偶性说明。平面图用欧拉公式v-er2其中 r 是面数包括外部面。若每个面至少由 k 条边围成则2e≥kr代入re-v2得e≤k(v-2)/(k-2)k2。卷面证明彼得森图非平面用的就是围长 k5彼得森图 v10、e15若平面则e≤5(10-2)/(5-2)40/3≈13.3与 e15 矛盾所以非平面。答题时先写公式再代数据最后说明矛盾。不要只写“看起来交叉”就判定非平面。欧拉图与哈密顿图的对比可以列成小表答题前扫一眼避免混判定对象核心条件期末常用检查欧拉回路连通所有顶点度为偶数数奇点0 个奇点欧拉路径连通恰有 0 或 2 个奇点2 个奇点时为路径哈密顿回路经过每个顶点一次并回到起点小图构造割点排除平面图可画在平面上无边交叉欧拉公式与边数不等式欧拉图题不要漏“连通”。有孤立点时所有度数都是偶数但不连通不能算欧拉图。哈密顿图题不要看到“每个顶点度至少 n/2”就无条件选那是充分条件不是必要条件小图仍要尝试构造。平面图题注意 k 的取值三角形面 k3四边形面 k4彼得森图围长 5。把 k 找对不等式才有意义。4. 代数结构与逻辑幺元逆元、群同态、CP证明的答题骨架代数结构这一块看起来抽象期末却很有套路二元运算表找幺元和逆元群同态证明子群偏序与格判断最后落到数理逻辑的主合取范式和 CP 规则。答题时不要被符号吓住先把“幺元是哪一个”“逆元按表查”“子群证三件事”“CP 附加前提”写成固定骨架。代数题的分往往在步骤不在灵感。4.1 二元运算表幺元、逆元、群判定二元运算表题先找幺元。幺元 e 满足对任意 xe*xx*ex在运算表中表现为 e 所在的行与表头一致e 所在的列也与表头一致。卷面题给出运算表答案说幺元是 a有逆元的元素为 a,b,c,d逆元分别为 a,b,c,d。答题时不要凭“看起来像最大值”就下结论要按表查。若运算真是x*ymax{x,y}最小元才是幺元且只有幺元自己有逆元但卷面表若是循环表逆元就要按表找。表题的第一原则是“以表为准”。逆元的定义是x*ye且y*xe两个方向都要满足。找 x 的逆元时先在 x 所在行找 e再看对应列头 y然后回到 y 所在行确认 y*x 也是 e。只查一个方向容易错。若表中某行没有 e该元素无逆元。群要求封闭、结合、有幺元、每个元素有逆元运算表能直接看封闭和幺元、逆元结合律通常由题目背景保证或需另证。答题时写“封闭显然幺元为 a各元素逆元如下”比只写答案稳。选择题问“哪个代数系统是群”先排除没有幺元或逆元的选项再检查结合律。有限群还可以看运算表是否每行每列都是表头的排列这能快速发现不满足消去律的表。注意“有幺元”和“每个元素有逆元”要同时满足不能只看对角线。答题时把四个条件列成勾选表能避免漏项。4.2 群同态与子群C{x|f(x)g(x)}的证明群同态题常见形式f 和 g 都是群 G1 到 G2 的同态令C{x∈G1|f(x)g(x)}证明 C 是 G1 的子群。子群证明按三件事写非空、对运算封闭、对逆元封闭。非空通常取单位元 e1因为同态保持单位元f(e1)e2g(e1)所以 e1∈C。封闭任取 a,b∈C有 f(a)g(a)、f(b)g(b)于是f(ab)f(a)f(b)g(a)g(b)g(ab)所以 ab∈C。逆元任取 a∈C同态保持逆元f(a^{-1})f(a)^{-1}g(a)^{-1}g(a^{-1})所以 a^{-1}∈C。三步写完结论成立。这里的易错点是逆元运算方向。同态给的是f(ab)f(a)f(b)由此可推出f(a^{-1})f(a)^{-1}但不能写成f(a)^{-1}g(a)就结束要保留“g 也是同态”这一步。答题时把等式两边写全f(a^{-1})f(a)^{-1}又f(a)g(a)所以f(a)^{-1}g(a)^{-1}再由 g 同态得g(a)^{-1}g(a^{-1})。三行连起来方向不会反。子群证明不需要证结合律因为 G1 已经是群结合律继承。若题目要求证明 C 是子群而不是正规子群不要多证共轭。若 C 的定义换成{x|f(x)g(x)^{-1}}或其他形式先检查单位元是否满足再按同样三件事推。答题时先写“C 非空因为 e1∈C”再写封闭和逆元。每一步都引用同态性质不要跳步。4.3 命题逻辑与谓词逻辑主合取范式与CP规则主合取范式与主析取范式是逻辑填空的常客。主析取范式取成真赋值变量取 1 写原变量、取 0 写否定若干极小项析取主合取范式取成假赋值变量取 0 写原变量、取 1 写否定若干极大项合取。答题时先列真值表再按“成真/成假”选行。检查方法主合取范式在成假行应为 0在成真行应为 1若反了就是 0/1 取法弄反。CP 规则用于证明蕴涵式。要证P→Q可以把 P 作为附加前提加入推出 Q再用 CP 得P→Q。卷面谓词逻辑题要证∀x(P(x)→Q(x))与∀xP(x)推出∀xQ(x)可写成附加前提∀xP(x)用 US 得P(c)用 US 得P(c)→Q(c)用 MP 得Q(c)用 UG 得∀xQ(x)最后 CP 得∀xP(x)→∀xQ(x)。每一步注明规则US 全称例示UG 全称 generalizationMP 假言推理CP 条件证明。使用 UG 时要注意 c 是任意个体不能是前提中特殊的自由个体。期末题通常默认 c 任意但答题时写“c 任取”更稳。US 只能消去全称量词不能消去存在量词存在量词要用 EI且 EI 的个体常元要是新的。CP 的附加前提要在最后用 CP 收回不能把附加前提当成最终前提。答题纸上把每行编号右侧写规则阅卷能顺着看。4.4 真题演练真命题判断与双射识别真命题选择题常给几个带量词或集合符号的式子要求选真命题。答题时先判断量词顺序∀x∃y和∃y∀x真假不同再判断空集、全集、整数集等论域。遇到含→的命题可用“前件假则真”快速排除。卷面答案选 C、D说明至少有两个式子为真答题时不要只凭一个例子断定全称命题真全称命题要说明任意性存在命题给一个实例即可。双射题先看定义域和值域。卷面选项f:I→E, f(x)2x是双射单射因为2x2y得xy满射因为任意偶数2k都有原像k。f:N→N, f(n)n/2不是 N 到 N 的函数奇数无像f:R→I, f(x)[x]不是单射多个实数取整相同f:I→N, f(x)|x|不是单射正负同绝对值。答题时写“单射…满射…所以双射”不要只写“显然”。集合 A 上二元关系个数题|A|3时有序对 9 个关系数2^9512。选项可能写2^{3^2}要认出与 512 等价。集合相等题注意空集符号和重复元素。商集P(A)/R题先看等价关系定义再把幂集元素按等价类分组卷面答案 D 中的等价类包含空集、{2}、{2,3} 等说明 R 可能按“最小元素”或“基数”分组答题时要按题目定义分组不要按元素个数猜。包含关系的哈斯图按集合包含画空集在最下全集在最上去掉传递边。5. 易错点复盘离散数学期末最常见的5个失分点这一章只盯失分点。离散数学的题往往不是不会而是“定义少写一句、矩阵多算一位、哈斯图多画一条边”。下面五条按“错在哪→为什么错→怎么答对”拆开每条都配一个期末常见题面。复习时把每条当成检查清单做完一类题就对照一次比重复刷同类型题更有效。5.1 把对称差当成并集或交集错在哪文图阴影题里看到 B 和 C 重叠就写成B∪C或B∩C忽略“只属于一个集合”的对称差含义。比如题目要(B⊕C)-A有人写成(B∪C)-A把 B、C 都有的元素也留下。为什么错对称差是“恰在一个集合中”并集是“至少在一個”交集是“两个都在”。三个符号的元素归属不同画图时阴影区域也不同。怎么答对先写B⊕C(B-C)∪(C-B)再写减去 A 等价于(B∪C)-(B∩C)-A在草稿上列四个区域逐区判断是否在阴影里。最后取一个具体元素代入若元素同时在 B、C 且不在 A它应在B∪C但不在B⊕C用这个反例检查答案。5.2 哈斯图漏画自反边或传递边错在哪题目给哈斯图要求写偏序关系 R答案只写覆盖关系漏掉a,a等自反对或者反过来把传递边也画进哈斯图。为什么错哈斯图只画覆盖关系不画自反边和传递边但偏序关系 R 是完整关系包含自反性和传递性。两个对象的“图”和“关系”不是一回事。怎么答对分两行写先写覆盖关系{(a,b),(a,c),(b,d),(c,d)}再写自反对{(a,a),(b,b),(c,c),(d,d)}最后合并。若要求画哈斯图先去掉自反边再去掉可由传递推出的边只留覆盖边画完检查每个非自反对是否都能由覆盖边传递得到。5.3 关系矩阵布尔乘法混成普通加法错在哪求传递闭包时把矩阵乘法按普通加法算出现 2、3 等数字或者把M^2中为 1 的位置直接当成t(R)。为什么错关系矩阵乘法中“存在中间点”对应逻辑或“同时有边”对应逻辑与结果只应取 0/1传递闭包还要把R,R^2,…,R^n逐位取并不能只算一次平方。怎么答对写清布尔乘法规则C[i][j]∨_k(A[i][k]∧B[k][j])算完M^2后与 M 逐位或得T再算M^3继续或直到不再出现新 1。最后回写集合检查是否包含原关系所有有序对传递闭包不自动补对角线除非原关系自反。5.4 树度数列方程漏算树叶和内部结点错在哪题目说“7 片树叶、3 个 3 度结点其余 4 度”有人设 4 度结点为 n 后顶点数写成73忘了加 n或者把树叶按 0 度算。为什么错树叶是度数为 1 的顶点必须计入顶点数和度数和其余 4 度结点也是顶点不能漏。树的ve1与握手定理要同时用。怎么答对先设未知数 n写v73nev-19n度数和7×13×34n164n等于2e182n解方程得 n1。代回检查v11,e10,度数和20。若题目改成“其余都是 5 度”同样列方程不要凭感觉选。5.5 群同态证明中逆元运算方向写反错在哪证明 C 对逆元封闭时直接写f(a^{-1})g(a)^{-1}中间少了“f(a)g(a)”和“g 同态保持逆元”的衔接或者把f(a^{-1})写成f(a)^{-1}后忘记说明等于g(a^{-1})。为什么错同态保持运算也保持逆元但逆元等式要一步一步推先 f 同态再 f(a)g(a)再 g 同态。方向写反会让阅卷看不出依据。怎么答对写三行f(a^{-1})f(a)^{-1}因为 a∈Cf(a)g(a)所以f(a)^{-1}g(a)^{-1}因为 g 同态g(a)^{-1}g(a^{-1})。最后得f(a^{-1})g(a^{-1})所以 a^{-1}∈C。封闭性也按同样方式写全f(ab)f(a)f(b)g(a)g(b)g(ab)。6. 考场答题顺序与押题思路先拿稳集合关系再攻图论证明期末卷的时间分配比刷题更重要。建议先做填空选择里定义明确的题集合运算、关系个数、主合取范式、补图边数、树度数列方程。这些题单题分值不大但步骤短、检查快。关系矩阵和传递闭包放在中段因为要动笔算趁脑子清醒做。图论证明和群同态放后段先把模板句写上去再补细节。最后留十分钟专门检查哈斯图自反边、传递闭包对角线、树方程代回。题型建议时间交卷前检查填空选择3040 分钟对称差是否只取单边关系个数指数是否写对关系矩阵与闭包2025 分钟布尔乘法是否只取 0/1是否累加到不再新增图论计算2025 分钟通路数是否允许重复顶点树方程是否代回证明题2530 分钟子群三件事是否写全CP 是否收回附加前提检查10 分钟哈斯图自反边、补图边数、平面图 k 值押题思路可以按“高频小分 固定大题”准备。高频小分对称差表达式、主合取范式、关系个数2^(n^2)、补图边数、通路数、树度数列方程、幺元逆元。固定大题哈斯图与偏序关系、传递闭包矩阵、群同态子群证明、CP 规则证明、平面图不等式。复习时不要只背答案把每类题的“第一句”写成模板集合题先写元素归属关系题先写矩阵图论题先写判定条件证明题先写非空/封闭/逆元。模板句能保证即使算错步骤分也能拿到。我复习这类卷子时踩过一次坑传递闭包算到R^2就以为结束结果漏了R^3的传递边整道计算题白丢一半分。从那以后我每次做闭包都强制走一遍“列矩阵、算幂、逐位或、回写集合、查对角线”的流程哪怕题目看起来很简单也不跳步。希望帮到你。本文还有配套的精品资源点击获取