简介：本资源是哈尔滨工业大学《集合论与图论（下）》慕课MOOC课程的配套习题答案整理，面向计算机、数学及相关专业本科生及自学者，助力系统掌握图论核心理论与解题方法。内容覆盖图的基本类型（简单图、有向/无向/加权图）、树与连通性、邻接矩阵与邻接表表示、补图与偶图、欧拉图与哈密顿图判定、图着色、平面图、割点桥及最短路径算法等关键模块，紧扣课程讲授逻辑，每讲对应清晰（如第1讲图的基本概念、第3讲欧拉图、第4讲哈密顿图），并附实用提示：慕课题目重复率高，需仔细比对选项。资源为单个PDF文件，大小3.16MB，结构紧凑、排版清晰，便于离线查阅与重点标注。目前已有361人学习下载，适合考前复习、作业核对与概念巩固，是理解抽象图论知识与提升逻辑建模能力的高效辅助材料。
1. 图论下半程：一张从“定义辨析”到“判定黑匣子”的知识地图
如果你正在刷《哈工大集合论与图论（下）》慕课，却总在“欧拉图判别”和“哈密顿图存在性”之间反复横跳、在“补图构造”时漏掉自环判定、在“偶图验证”时误把二部划分当充要条件——那不是你基础差，而是这张知识地图没摊开。这门课的下半程，表面是四讲（图基本概念→连通/补/偶图→欧拉图→哈密顿图），实则暗藏三重跃迁：从静态结构描述（是什么）→动态路径存在性判定（能不能走通）→组合结构性质验证（有没有某种划分）。它不考计算，专考逻辑咬合度；不拼记忆量，拼的是对“定义边界”的敏感度——比如“简单图”默认无自环无重边，但补图定义里隐含“全图假设”，一旦忽略这点，补图顶点度数算错就是必然。适合两类人：一是备考前突击梳理判定条件链的人（比如期末前72小时），二是学完算法后回溯理论根基的人（比如刚写完Dijkstra想搞懂“为什么它不适用于负权但能跑通连通图”）。这份MOOC答案资源的价值，不在“抄答案”，而在用高频题反向锚定每个判定定理的适用前提、反例陷阱、等价变形——它是一份带错误日志的判定条件速查表。
2. 图的基本结构与表示：从定义到可操作的判定脚手架
2.1 四类图的本质差异：不是分类，是建模意图的编码
图论中“图”的类型划分，本质是数学建模对现实约束的编码。慕课第一讲反复强调的“简单图、有向图、无向图、加权图”，不能只记定义，必须对应到判定题的操作动作：
简单图（Simple Graph）：判定题中若出现“任两顶点间至多一条边”，立刻触发两个检查项：① 是否默认排除自环（loop）？② 是否禁止重边（multiple edges）？
提示：MOOC选择题常设陷阱选项如“含自环的图是简单图”，需秒判为错——简单图定义本身已排除自环，无需额外说明。
有向图（Directed Graph）：关键在“边有方向”，直接导致度数分裂为入度（in-degree）与出度（out-degree）。所有后续判定（如欧拉图、强连通）都依赖此分裂。
例如：判断有向图是否存在欧拉回路，条件是“每个顶点入度 = 出度”，而非“度数为偶数”——后者仅适用于无向图。无向图（Undirected Graph）：边无方向，度数即邻接边总数。但注意：无向图的“连通性”判定必须基于无向路径，而MOOC题常混入有向图语境干扰（如题干说“图G”，选项却用“从u到v有路径”这种有向表述）。
加权图（Weighted Graph）：权重是附加属性，不改变图的拓扑结构。但MOOC中加权图常作为最短路径、最小生成树的前置铺垫——此时权重类型（正/非负/可负）直接影响算法选择，虽本讲未展开算法，但题干若出现“边权为-3”，已在暗示后续Dijkstra不适用。
2.2 邻接矩阵 vs 邻接表：空间与判定效率的硬币两面
两种表示法在MOOC题中不考实现，但考判定场景适配性。例如：
邻接矩阵（Adjacency Matrix）：
# 假设n个顶点，matrix[i][j] = 1 表示i→j有边（有向）或i-j有边（无向） # 判定无向图：矩阵必须对称（matrix[i][j] == matrix[j][i]） # 判定简单图：主对角线全0（无自环），且每行每列无重复1（无重边，但矩阵本身无法直接体现重边，需题干说明）优势：判断两顶点是否邻接为O(1)；劣势：空间O(n²)，稀疏图浪费严重。MOOC选择题常问“某图用邻接矩阵存储，空间复杂度？”——答案必为O(n²)，与边数无关。
邻接表（Adjacency List）：
# graph[u] = [v1, v2, ...] 表示u指向v1,v2... # 判定有向图入度：统计所有邻接表中v出现的次数 # 判定无向图度数：len(graph[u]) 即u的度数（因每条边存两次）优势：空间O(n+e)，e为边数；劣势：查u-v是否邻接需遍历graph[u]。MOOC填空题常考“邻接表中顶点u的度数为____”，无向图填
len(graph[u])，有向图则需分len(graph[u])（出度）和“统计v在所有邻接表中出现次数”（入度）。
2.3 连通性判定的底层逻辑：路径存在性 ≠ 边存在性
连通图（Connected Graph）定义是“任意两顶点间存在路径”，但MOOC题常混淆“路径”与“边”：
- 错误认知：“u和v邻接（有边）→ u和v连通” ✓（正确，但只是特例）
- 错误认知：“u和v连通 → u和v邻接” ✗（典型错误！连通是传递闭包，邻接是直接边）
例：图G有边(u,w)、(w,v)，则u和v连通但不邻接。MOOC多选题常设选项“若u,v连通，则必存在边(u,v)”——此为绝对错误项。
注意：无向图连通性可用BFS/DFS验证，但MOOC不考代码，考的是反例构造能力。如问“是否存在连通但非完全图的图？”，答“存在，如3个顶点构成路径图u-w-v”——此例同时满足连通（u-v经w可达）、非完全（缺边u-v）。
3. 补图、偶图与连通性：三组易混淆的结构性质辨析
3.1 补图（Complement Graph）：全图假设下的“边取反”
补图G̅的定义依赖于原图G的顶点集V和全图K|V|（|V|阶完全图）。MOOC题中补图相关错误，90%源于忽略“全图”前提：
正确流程：
- 确认G的顶点集V（如V={a,b,c,d}）；
- 构造全图K₄（4个顶点间所有可能的6条边）；
- G̅的边集 = K₄的边集 \ G的边集。
常见翻车点：
- 若G有自环，补图定义通常不包含自环（因Kₙ默认无自环），但MOOC题干若未声明G为简单图，需警惕；
- 若G为有向图，补图需对“所有可能的有向边”取反（共n(n-1)条，不含自环），而非仅对无向边取反。
3.2 偶图（Bipartite Graph）：二部划分才是灵魂，边数奇偶是烟雾弹
“偶图”名称极具误导性——它与“边数为偶数”毫无关系！MOOC摘要中“偶图作为图中所有边的数目为偶数的图”是严重错误表述（应为笔误），正确概念是二部图（Bipartite Graph），即顶点集可划分为两个互斥子集X,Y，使得所有边的端点分别属于X和Y。
判定核心：是否存在合法二部划分。MOOC题常用以下方式检验：
- 充要条件：图中不含奇圈（odd cycle），即长度为奇数的环。
例：三角形（3圈）不是偶图；正方形（4圈）是偶图；五边形（5圈）不是偶图。 - 实操方法：尝试2-染色（bipartite coloring）——从任一点染色A，其邻点染B，邻点的邻点染A…若过程中出现某点被要求染两种颜色，则非偶图。
- 充要条件：图中不含奇圈（odd cycle），即长度为奇数的环。
易错点：题干说“图有6条边”，就认为“边数偶→是偶图”——这是玄学判定，必须回归二部划分或奇圈检验。
3.3 连通图的进阶：割点、桥与块分解的伏笔
MOOC虽未在前三讲展开割点（cut vertex）和桥（bridge），但连通性判定题已埋下线索。例如：
- “删除顶点v后，图不再连通” → v是割点；
- “删除边e后，图不再连通” → e是桥。
这些概念是理解“块（block）”——极大无割点子图——的基础。MOOC选择题可能问：“若图G有割点v，则G的连通分支数在删除v后如何变化？”答案是“增加”，但需注意：增加量 ≥1，不一定是+1（如v连接3个块，删除后分支数+2）。
提示：割点判定在MOOC中常以“某图删除某点后是否仍连通”形式出现，本质是测试对“连通性脆弱点”的识别——不是考Tarjan算法，而是考能否画出小规模反例。
4. 欧拉图与哈密顿图：存在性判定的双生难题
4.1 欧拉图：边遍历的完备条件链
欧拉路径（Euler Path）与欧拉回路（Euler Circuit）的判定，是MOOC中逻辑最严密的模块。其条件链必须严格按“图类型→路径/回路→有向/无向”展开：
| 图类型 | 欧拉回路存在条件 | 欧拉路径存在条件（非回路） |
|---|---|---|
| 无向连通图 | 所有顶点度数为偶数 | 恰好两个顶点度数为奇数（起点/终点），其余为偶数 |
| 有向连通图 | 所有顶点入度 = 出度 | 恰好一个顶点出度 = 入度 + 1（起点），一个顶点入度 = 出度 + 1（终点），其余入度 = 出度 |
关键前提：图必须连通（对无向图）或基图连通（对有向图，即忽略方向后的无向图连通）。MOOC题常省略“连通”前提，直接给图问“是否欧拉图”，此时若图不连通，即使度数满足，也不是欧拉图。
经典反例：两个分离的三角形（各3顶点）。每个三角形内所有顶点度数=2（偶数），但整个图不连通 → 无欧拉回路。
4.2 哈密顿图：NP难问题的“不可判定性”启示
哈密顿路径（Hamilton Path）与哈密顿回路（Hamilton Circuit）的判定，是图论中著名的NP难问题——不存在多项式时间的充要判定条件。MOOC不考证明，但考对“必要条件”与“充分条件”的清醒认知：
必要条件（Must have）：
- 若G是哈密顿图，则G必连通；
- 对任意非空真子集S ⊂ V，删除S后，G-S的连通分支数 ≤ |S|（Ore定理弱化版，即Dirac定理前提：若n≥3且δ(G) ≥ n/2，则G是哈密顿图）。
充分条件（Sufficient but not necessary）：
- Dirac定理：n≥3的简单图，若每个顶点度数 ≥ n/2，则G是哈密顿图；
- Ore定理：n≥3的简单图，若对任意不相邻顶点u,v，deg(u)+deg(v) ≥ n，则G是哈密顿图。
MOOC选择题陷阱：给出一个图满足Dirac条件（如5顶点图，各度数≥3），问“是否一定哈密顿？”——答“是”；但若图不满足（如某顶点度数=2），问“是否一定不哈密顿？”——答“否”，因存在不满足Dirac但仍哈密顿的图（如环图C₅）。
4.3 欧拉 vs 哈密顿：一张对比表终结所有混淆
| 维度 | 欧拉图 | 哈密顿图 |
|---|---|---|
| 遍历对象 | 每条边恰好一次 | 每个顶点恰好一次 |
| 判定难度 | 多项式时间（度数统计+连通性） | NP难（无高效充要条件） |
| 充要条件 | 存在（无向：连通+全偶度；有向：基图连通+入=出） | 不存在通用充要条件（仅有必要/充分条件） |
| MOOC题重点 | 条件链的完整性（漏“连通”即错） | 区分“必要”与“充分”（满足充分条件→是；不满足→未必不是） |
| 反例构造 | 两个分离三角形（度数偶但不连通） | Petersen图（满足Dirac？不，但它是哈密顿图？不，它其实不是——经典非哈密顿图） |
注意：Petersen图是MOOC级经典反例——10顶点，3-正则，无哈密顿回路，但满足许多“看起来像哈密顿”的条件。不必记住它，但要记住：哈密顿性不能靠直觉，必须依赖定理或穷举。
5. 易错点与易忽略点：那些让高分变及格的细节黑洞
5.1 易漏点：补图定义中的“全图”被静默吃掉
- 易漏表现：做补图题时，只关注原图G的边，直接对G的边集取反，忽略G的顶点集V和全图K|V|的边集。
- 为什么漏：定义文本中“补图G̅的边集是K|V|中不属于G的边”被快速扫过，“K|V|”这个符号未被具象化为“所有可能的边”。
- 怎么补：强制三步法——① 写出V；② 计算K|V|的边数（无向：|V|(|V|-1)/2；有向：|V|(|V|-1)）；③ 用K|V|边数减去G的边数，得G̅边数。若结果为负，必有计算错误。
5.2 易错点：偶图判定中把“边数偶”当充要条件
- 易错表现：看到图有8条边，立刻选“是偶图”；或看到有5条边，选“不是偶图”。
- 为什么错：混淆“偶图（bipartite）”与“偶数条边的图”。中文命名造成的历史遗留坑。
- 怎么补：遇到“偶图”题，脑中自动替换为“二部图”，并启动2-染色流程：选起点染红→邻点染蓝→邻点的邻点染红…若冲突则非二部。边数？忘掉它。
5.3 易忽略点：欧拉判定中“连通性”是独立前提
- 易忽略表现：题目给一个图，度数全偶，学生直接判“是欧拉图”，忽略图由两个分离组件构成。
- 为什么忽略：条件链被记成“度数偶→欧拉”，省略了“且连通”这个并列前提。
- 怎么补：所有欧拉判定题，先画草图或 mentally check 连通性——对小图（≤6顶点），用“能否从任一点走到任意其他点”快速验证；对大图，看题干是否明说“连通图”。
5.4 易错点：有向图欧拉条件中混淆“入度=出度”与“度数偶”
- 易错表现：有向图中某顶点入度=3、出度=3，学生记作“度数=6（偶）”，进而套用无向图条件。
- 为什么错：有向图的“度数”概念在欧拉判定中被解构为入度、出度两个独立变量，无向图的“度数”是它们的和，但判定逻辑完全不同。
- 怎么补：看到有向图，立即屏蔽“度数”一词，只盯“入度”和“出度”两个数字，并列比较。
5.5 易漏点：哈密顿图中“简单图”假设未被显式声明
- 易漏表现：题干只说“图G”，未提“简单图”，学生用Dirac定理（要求简单图）判定，却忽略G可能含自环或重边。
- 为什么漏：Dirac/Ore定理教材中常默认简单图，但MOOC题干未必声明。
- 怎么补：凡用Dirac/Ore定理，先确认题干有“简单图”三字；若无，则该定理不适用，只能用必要条件（如连通性）排除，不能用充分条件肯定。
6. 复习清单与查漏技巧：一份可执行的考前72小时作战计划
6.1 核心判定条件速查表（打印贴桌版）
| 定理/概念 | 充要条件（无向连通图） | 充要条件（有向基图连通） | MOOC高频陷阱 |
|---|---|---|---|
| 欧拉回路 | 所有顶点度数为偶数 | 所有顶点入度 = 出度 | 忘记检查连通性；有向图误用“度数偶” |
| 欧拉路径 | 恰好两个顶点度数为奇数 | 恰好一个出度=入度+1（起点），一个入度=出度+1（终点） | 奇度数顶点数≠2时，误判为“无路径”（实际可能有路径但非回路） |
| 偶图（二部图） | 无奇圈；或可2-染色成功 | 同无向（有向图的偶图判定同基图） | 把“边数偶”当条件；未尝试染色直接放弃 |
| 哈密顿回路（Dirac） | n≥3，且δ(G) ≥ n/2（δ为最小度） | 不适用（Dirac仅针对无向简单图） | 对非简单图误用；n<3时强行套用（n=2时，单边图是哈密顿图？否，需至少3顶点） |
| 补图边数 | |E(G̅)| = n(n-1)/2 − |E(G)| | |E(G̅)| = n(n-1) − |E(G)| | 忘记有向图全图边数为n(n-1)，误用n(n-1)/2 |
6.2 三步错题归因法：定位你的知识断点
当你做错一道MOOC题，不要只看答案，用此法归因：
- 断点定位：这道题考哪个判定条件？（例：欧拉回路→需检查连通性+度数）
- 动作回放：你当时执行了哪几步？（例：算了度数全偶，但没验证连通性）
- 漏洞类型：属于哪类易错点？（对照第5章：是“易忽略连通性”还是“混淆有向/无向”？）
- 若属“易忽略”，下次同类题强制加一步（如欧拉题必画连通性草图）；
- 若属“混淆”，制作对比卡片（如“有向图欧拉：只看入/出度，不看度数和”）。
6.3 模拟题实战：用MOOC原题反向训练
取MOOC中一道典型错题（如“判断某有向图是否存在欧拉回路”），按以下步骤拆解：
- Step 1：剥离题干——只留图结构（顶点、边方向），遮住选项；
- Step 2：手写判定链——① 基图连通？② 每个顶点入度=出度？③ 结论；
- Step 3：比对选项——找出哪个选项对应你的结论，哪个选项是常见错误（如“度数和为偶数”）；
- Step 4：错误项注释——在错选项旁写“错因：混淆有向图度数概念，此处度数和=6无意义”。
坚持5道题，你会发现自己对“定义咬合点”的敏感度飙升——因为MOOC题库重复率高，这些错因会复现。
6.4 我的血泪经验：从“抄答案”到“建判定树”的转变
最初我也把这份MOOC答案当标准答案抄，直到第三次在“补图边数”题上栽跟头：题干给4顶点图有3条边，我算补图边数=6−3=3，选了“3条”，结果错。回看才发现——题干图是有向图！全图边数应是4×3=12，补图边数=12−3=9。那一刻我意识到：答案不是终点，是映射判定条件的坐标。从此我每拿到一道题，先不看选项，而是强制在草稿纸上画一棵判定树：根是“图类型”，第一层分“有向/无向”，第二层分“连通性/度数/圈长”，叶子节点才是具体计算。现在每次打开MOOC，我第一件事是新建一个文本文件，标题写“判定树：欧拉回路”，然后逐条敲下条件，再去做题。这习惯让我在考前模拟中，欧拉/哈密顿类题正确率从65%升到92%。希望帮到你。
本文还有配套的精品资源，点击获取
