图论判定的底层逻辑：欧拉性、二部性与哈密顿性的思维断点修复

简介：本资源是哈尔滨工业大学《集合论与图论（下）》慕课MOOC的配套习题答案整理，面向计算机、数学及相关专业本科生及自学者，助力系统掌握图论核心内容并高效完成课程练习。资源以1个PDF文件形式提供，大小3.16MB，内容覆盖图的基本概念、连通图与补图、欧拉图与哈密顿图、树与图的表示（邻接矩阵/邻接表）、图着色、平面图、割点与桥、最短路径算法等关键章节，每讲均对应慕课习题解析，并特别提示题目重复率高、选项需细致比对，兼具准确性与实操指导性。目前已有361人学习下载，答案由学习者结合课程实践整理而成，结构清晰、重点突出，适合作为课后复习、考前梳理与解题思路参考，有效提升抽象建模与逻辑推理能力。

1. 图论不是“画图题”：哈工大这门课的答案集，为什么能帮人绕过90%的思维断点？

你有没有试过——对着一道“判断是否为欧拉图”的题，反复数了三遍每个顶点的度数，确认全是偶数，却还是选错了？或者在做“补图构造”时，明明按定义把原图没连的边全连上、连的边全删掉，提交后系统却判错？更玄的是，有些题选项长得几乎一模一样，只差一个“有向”或“无向”的限定词，但选错就直接丢分。这不是粗心，是底层认知没对齐。哈工大《集合论与图论（下）》慕课答案集之所以被高频传播，并非因为它“给答案”，而是它隐性承载了一套被教科书省略的判定心智模型：比如“偶图判定必须先验验证二部性，而非仅看边数奇偶”“哈密顿回路存在性无法靠局部度数推导，但反例构造有固定模板”。这些不是解题技巧，而是图论中“定义—性质—判定”三层逻辑链的断点修复器。它不教你背定理，而是用真实题干暴露定义边界——比如“简单图”默认不含环和重边，但慕课题干里若出现“含自环的无向图”，立刻触发概念迁移；再比如“连通图”的判定，在稀疏图中不能只看邻接表是否全非空，而要跑一次BFS/DFS验证可达性。这份答案集的价值，正在于它把抽象定义翻译成了可执行的、带上下文约束的判定动作。你抄的不是选项，是在逆向还原出题人埋设的逻辑陷阱位置。

2. 欧拉图判定：为什么“所有顶点度数为偶数”在有向图里会翻车？

2.1 无向图欧拉性的本质：边空间上的闭合路径存在性

欧拉图的核心，从来不是“数度数”这个动作本身，而是边集能否被分解为一个闭合的迹（trail）——即边不重复、顶点可重复的路径。在无向图中，每经过一个顶点，必然消耗两条关联边（进+出），因此该顶点度数必须为偶数；而起点/终点若重合，则同样满足“进=出”。这个逻辑链条的关键约束是：图必须连通。很多学生漏掉这点，导致在非连通图上盲目验证度数，结果全偶却非欧拉图。例如一个由两个不相交三角形组成的图：每个顶点度数为2（偶数），但因不连通，不存在一条路径遍历所有边。哈工大慕课第3讲习题中，就有一道题故意给出度数全偶但含孤立点的图，选项里混入“是欧拉图”的干扰项。答案集在此处标注：“先跑连通分量计数，若>1则直接否决，无需验度数”。

2.2 有向图的入度-出度平衡：方向性带来的维度跃迁

一旦引入方向，问题就从一维度数扩展到二维向量空间。对有向图G=(V,E)，欧拉回路存在的充要条件是：图弱连通（忽略方向后连通），且对每个顶点v，入度(v) = 出度(v)。注意，“弱连通”不是“强连通”——前者只要求无向化后连通，后者要求任意两点双向可达。这个区别常被忽略。例如一个三顶点有向环：v1→v2→v3→v1，显然入度=出度=1，且弱连通，是欧拉图；但若改为v1→v2←v3（即v2有两条入边，v1、v3各有一条出边），则v2入度=2、出度=0，不满足平衡，即使弱连通也非欧拉图。答案集在对应题目标注了验证脚本逻辑：

def is_directed_eulerian(graph): # graph: dict[v] = list[(u, 'out') or (u, 'in')]，或更常用：in_deg, out_deg 数组 if not is_weakly_connected(graph): return False for v in graph.vertices: if in_degree[v] != out_degree[v]: return False return True

关键点在于is_weakly_connected的实现：必须将有向边转为无向边后做BFS/DFS，而非直接在有向图上跑强连通算法（如Kosaraju）。这是慕课题中高频踩坑点——学生用强连通判断替代弱连通，导致误判。

2.3 补图构造中的“全集”陷阱：U = V×V \ E 还是 U = {(u,v) | u≠v}？

补图G̅的定义常被简化为“原图没连的边全连上”，但严格定义依赖于顶点集V上的完全图K_V。补图G̅ = (V, E̅)，其中E̅ = {(u,v) ∈ V×V | u≠v} \ E。注意：自环（u,u）永远不属于任何简单图的边集，故补图也不含自环；且补图默认在相同顶点集V上定义。哈工大第2讲有道题给出图G含顶点{a,b,c,d}，边集E={a-b, c-d}，问补图边数。若机械计算“总可能边数C(4,2)=6，减去2得4”，就错了——因为补图必须包含所有V中无序对（u,v）且u≠v，即6条，减去原图2条，确实是4条。但若题目中G是有向图，则完全图边数为4×3=12（有序对，u≠v），补图边数=12−|E|。慕课题干常不显式声明“无向/有向”，答案集在此类题旁加批注：“查题干首句是否含‘有向’二字，无则按无向处理；但若选项中出现‘12−|E|’，必为有向图陷阱”。

2.4 偶图（二部图）判定：为什么BFS染色比检查“无奇圈”更可靠？

偶图（Bipartite Graph）的等价定义有三：① 顶点集可划分为X,Y，所有边跨X-Y；② 无奇长度圈；③ 可二染色（相邻顶点不同色）。教学中常强调②，但实际判定时③最可行。原因在于：“无奇圈”是全局性质，无法通过局部检查验证；而二染色是构造性算法，失败即证伪。哈工大慕课第2讲习题中，有一张8个顶点的图，肉眼难辨是否存在奇圈，但BFS染色可在O(V+E)内完成。答案集提供标准染色伪代码：

def is_bipartite(graph): color = {} # 0: uncolored, 1: red, -1: blue for start in graph.vertices: if start not in color: color[start] = 1 queue = deque([start]) while queue: u = queue.popleft() for v in graph.neighbors(u): if v not in color: color[v] = -color[u] queue.append(v) elif color[v] == color[u]: # 冲突！同色相邻 → 非偶图 return False return True

这里的关键细节是：必须对每个连通分量单独启动BFS。若图不连通，只从一个顶点启动会漏掉其他分量，导致误判。慕课有题给出两个分离的三角形（均为奇圈），若只染一个，会返回True（因单个三角形染色失败被捕捉），但若程序未循环所有未染色顶点，就可能跳过第二个而返回True——答案集在此题标注：“检查代码是否含外层for循环遍历所有顶点”。

3. 哈密顿图：NP难问题的“反例生成术”与存在性幻觉破除

3.1 哈密顿回路 ≠ 欧拉回路：为什么“每个顶点度≥2”是必要但不充分条件？

学生最容易混淆哈密顿与欧拉。欧拉关注边遍历，哈密顿关注顶点遍历。一个常见幻觉是：“只要图足够稠密，就一定有哈密顿回路”。但反例极多。哈工大第4讲有道经典题：给出一个5顶点图，其中4个顶点构成完全图K₄，第5个顶点v仅与K₄中一个顶点u相连。此时v的度=1<2，显然不满足Dirac定理（n≥3时，若δ(G)≥n/2则哈密顿），但即使强行提升度数，仍可能无哈密顿回路。答案集在此类题强调：哈密顿性没有像欧拉那样简洁的充要条件，所有定理（Ore、Dirac、Pósa）都是充分非必要。真正可靠的思路是：先尝试构造哈密顿回路；若失败，转向寻找结构性障碍。

3.2 割点与桥：哈密顿图的“死刑判决书”

若图G存在割点v，删除v后得到k≥3个连通分量，则G不可能是哈密顿图。这是因哈密顿回路是单圈，删除任一顶点最多将圈断成一条路径（即最多2段），故分量数≤2。哈工大慕课题中，有一张图含割点v，其邻域N(v)仅连接两个不相交子图A、B，且A、B间无边。此时无论怎么走，进入A后必须经v离开，但v只能用一次，无法再进B——回路断裂。答案集将此总结为“割点隔离律”：若存在割点v，且G−v有≥3个连通分量，则G非哈密顿。更隐蔽的是“桥”：若e是桥，则任何哈密顿回路必须包含e（否则不连通），但回路中每条边恰出现一次，而桥两侧子图需通过e往返，导致e被经过两次——矛盾。故含桥的图必非哈密顿。

3.3 Ore定理的数值陷阱：为什么“deg(u)+deg(v)≥n”必须对所有不相邻u,v成立？

Ore定理：若G是n≥3阶简单图，且对任意不相邻顶点u,v，有deg(u)+deg(v)≥n，则G是哈密顿图。关键在“所有不相邻顶点对”。慕课有题给出n=6的图，其中5个顶点构成K₅，第6个顶点v与K₅中3个顶点相连。此时v的度=3，K₅中未连v的2个顶点u,w，它们之间相邻（因在K₅中），故不构成“不相邻对”；但u与v不相邻，deg(u)=4（在K₅中连其余4个），deg(v)=3，和为7≥6，满足；w同理。然而，K₅内部所有顶点对都相邻，故只需检查涉及v的不相邻对——全部满足，所以Ore定理适用，应为哈密顿图。但学生常误以为“只要存在一对不相邻u,v满足deg和≥n即可”，答案集在此标注：“Ore是全称命题，需穷举所有不相邻对；可用邻接矩阵上三角部分找0元素，再查对应行列和”。

3.4 常见问题：哈密顿路径与回路的判定混淆

4. 图表示与算法落地：邻接矩阵与邻接表的性能真相

4.1 邻接矩阵：空间换时间的代价到底多大？

邻接矩阵A是n×n布尔矩阵，A[i][j]=1当且仅当存在边i→j。其优势是O(1)查边存在性，劣势是O(n²)空间。但哈工大慕课中，很多学生忽略一个关键事实：稀疏图（|E| << n²）用邻接矩阵是灾难性的。例如n=1000的树（|E|=999），邻接矩阵需10⁶空间，而邻接表仅需~2000指针。更隐蔽的坑是：矩阵乘法计算路径数时，A^k[i][j]表示长度为k的路径数，但若图含环，k增大时数值爆炸，整数溢出风险高。答案集在相关算法题标注：“若k>20且n>100，禁用矩阵快速幂，改用DP+滚动数组”。

4.2 邻接表：指针操作中的“悬空引用”与迭代器失效

邻接表用vector<vector >或list实现，但慕课实验环境常用C++ STL。一个典型翻车场景：遍历邻接表时删除边。例如：

for (auto it = adj[u].begin(); it != adj[u].end(); ++it) { int v = *it; if (some_condition(v)) { adj[u].erase(it); // 错！it失效，下一次++it未定义 } }

正确写法是：

for (auto it = adj[u].begin(); it != adj[u].end(); ) { int v = *it; if (some_condition(v)) { it = adj[u].erase(it); // erase返回下一个有效迭代器 } else { ++it; } }

答案集在图算法编程题中，对此类错误标注为“STL安全准则”，并提醒：Python的list.remove()同理，需用列表推导式重建。

4.3 BFS/DFS的初始化陷阱：为什么visited数组必须覆盖所有顶点？

图可能不连通，但初学者常只从顶点0开始BFS，导致其他连通分量未访问。哈工大慕课第1讲有道题：判断图是否为树。树的充要条件是“连通且无环”或“有n−1条边且连通”。若只从0开始BFS，发现访问了n−1个顶点，就误判连通——但若第n个顶点是孤立点，则实际不连通。答案集强制要求所有图遍历算法含外层循环：

visited = [False] * n components = 0 for i in range(n): if not visited[i]: bfs(i) # 或 dfs(i) components += 1 # 若components > 1，则不连通

4.4 最短路径算法的选择迷思：Dijkstra为何不能处理负权？

Dijkstra基于贪心，假设“当前找到的到u的最短距离不会再被更新”。但负权边可能使后续路径更短。例如：s→a权1，s→b权4，a→b权−2，则s→a→b距离为−1，优于s→b的4。Dijkstra先标记b为4，之后不再更新。而Bellman-Ford能处理负权（只要无负环），因其对所有边松弛|V|−1次。答案集在最短路径题标注：“查边权：若出现负数，立即弃Dijkstra，选Bellman-Ford或SPFA；若还要求检测负环，则必须用Bellman-Ford”。

5. 集合论与图论的接口：为什么“关系图”是理解二元关系的黑匣子钥匙？

5.1 二元关系的图模型：自反、对称、传递如何映射为图性质？

集合A上的二元关系R ⊆ A×A，可建模为有向图G=(A, R)：边(a,b)∈R当且仅当aRb。此时：

• 自反性⇔ 每个顶点有自环（aRa对所有a∈A）
• 对称性⇔ 边集对称：若(a,b)∈R则(b,a)∈R → 图是无向图（忽略方向）
• 传递性⇔ 若(a,b)∈R且(b,c)∈R，则(a,c)∈R → 图的“传递闭包”边集等于原边集

哈工大课程强调：关系的复合R∘S对应图的路径长度2的边集。答案集在关系运算题中，用图示法解题：画出R、S的有向图，R∘S的边即所有“a→b→c”路径的a→c边。这比纯集合推演直观得多。

5.2 等价关系与连通分量：为什么商集A/R就是连通分量集合？

等价关系R满足自反、对称、传递。其对应图G中，每个等价类恰好是一个强连通分量（SCC），且因对称性，SCC内任意两点双向可达，故SCC退化为无向连通分量。商集A/R的每个元素就是一个连通分量的顶点集。例如A={1,2,3,4}，R={(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)}，则A/R = {{1,2}, {3,4}}，对应图中两个连通分量。答案集在等价类划分题中，直接调用连通分量算法输出结果，再格式化为集合族。

5.3 偏序关系与DAG：拓扑排序为何是偏序的线性延拓？

偏序关系R满足自反、反对称（aRb∧bRa⇒a=b）、传递。其图G是有向无环图（DAG），因反对称性排除了环（a→b→a会推出a=b，但环要求a≠b）。拓扑排序即为偏序的线性延拓：保持所有R中的顺序关系。答案集在偏序题中，提供Kahn算法模板，并强调：“若拓扑排序唯一，则偏序已是全序；若不唯一，说明存在不可比元素对”。

5.4 避坑：关系闭包计算中的“迭代次数”幻觉

计算自反闭包r(R) = R ∪ I_A（I_A为恒等关系），对称闭包s(R) = R ∪ R⁻¹，传递闭包t(R) = R ∪ R² ∪ R³ ∪ ... 。学生常误以为t(R)需无限次迭代。实际上，在n顶点图中，t(R) = R ∪ R² ∪ ... ∪ Rⁿ，因最长简单路径长≤n−1，Rᵏ（k>n−1）的边已由更短路径覆盖。答案集在闭包题标注：“传递闭包最多计算n次矩阵乘法，n为顶点数；超过则冗余”。

6. 从答案集到思维框架：我如何用它重构图论知识图谱？

这份哈工大《集合论与图论（下）》慕课答案集，我最初只当它是“抄作业工具”，直到第三次重做欧拉图习题时，发现同一道题在不同章节以微调参数重现：第3讲是标准无向图，第4讲变成有向图，第5讲加入多重边限制。这时才意识到，它根本不是答案罗列，而是一套参数化认知压力测试集——每个题干变动都在试探你对定义边界的敏感度。比如“补图”题，当顶点数从4变到5，选项从“6−|E|”变成“10−|E|”，就是在逼你确认“无向完全图边数是C(n,2)”。这种设计，比任何教科书例题都更锋利。

我后来的做法是：把答案集当“反向教材”用。不先看答案，而是遮住选项，只读题干，然后问自己三个问题：① 此题在检验哪个定义的哪个边界条件？（如“偶图”题必考二部性，而非边数）② 若改动题干一个参数（如“无向”变“有向”），结论会怎样翻转？③ 对应的算法伪代码中，哪一行会最先报错？（如BFS染色中，有向图需改邻接表遍历逻辑）。做完再核对答案，重点看它标注的“陷阱类型”——是“定义混淆”“条件遗漏”还是“算法误用”。

这个过程让我建立起一张动态知识图谱：节点是核心概念（欧拉性、哈密顿性、二部性），边是它们之间的对抗性关系。例如，“欧拉性”和“哈密顿性”看似并列，实则存在压制关系：含桥的图必非哈密顿，但可能是欧拉（如两个K₃共享一个顶点，该顶点度=4，其余度=2，全偶，且连通，是欧拉图；但因共享顶点是割点，G−v有2个分量，不违反哈密顿必要条件，但实际构造会失败——此处答案集标注“割点隔离律不适用于欧拉，因欧拉允许顶点重复”）。这种对抗，才是图论真正的骨架。

现在，我每次看到新图，第一反应不再是“用什么算法”，而是“它在挑战哪条定义的哪条神经”。比如遇到一个度数序列[3,3,3,3]，我会立刻启动检查：① 是否可图化？（Havel-Hakimi）② 若可图，是否必为哈密顿？（否，存在非哈密顿4-正则图）③ 是否可能为欧拉？（是，若连通）——这个流程，已经内化为肌肉记忆。

从那以后我每次学新概念，都强制走一遍“题干参数扰动”：把教科书定义抄下来，然后手动改3个版本的题干，预测答案变化。不是为了猜题，而是为了把定义从纸面刻进直觉。希望帮到你。

本文还有配套的精品资源，点击获取