简介：本资源是哈尔滨工业大学《集合论与图论（下）》慕课MOOC课程的配套习题答案整理，面向计算机、数学及相关专业本科生及自学者，助力系统掌握图论核心理论与解题方法。内容覆盖图的基本类型（简单图、有向/无向/加权图）、树与连通性、邻接矩阵与邻接表表示法、补图与偶图、欧拉图与哈密顿图判定、图着色、平面图、割点桥分析及最短路径算法等关键模块，紧扣课程讲义逻辑，适合作为课后巩固、考前复习与自学验证的重要参考。资源为单个PDF文件，共1个文件，大小3.16MB，排版清晰、章节对应明确（含第1–4讲完整答案），便于打印查阅与碎片化学习。已有359人下载学习，答案基于高频重复题型归纳整理，注重选项辨析与思路提示，虽非官方发布但结构完整、标注细致，对提升图论建模能力与应试效率具有实用价值。
1. 图论不是“画图题”，而是帮你把现实问题“翻译”成结构关系的思维工具
你有没有遇到过这样的场景：
- 想规划一条快递员送完所有小区又回到仓库的最短路线，但试了十几种组合还是不确定哪条最优；
- 看到一个社交App里“好友的好友也可能是你认识的人”，突然好奇：这种“间接连接”到底能延伸多远？整个网络是不是真能连成一片？
- 或者调试一个程序时发现，只要删掉某个模块，整个系统就崩了——它到底在哪儿悄悄撑着其他所有部分？
这些问题，表面看是物流、社交、软件工程，但底层都指向同一个东西：点与点之间怎么连、连得牢不牢、能不能走通、走通要花多少代价。
这就是图论要干的事。它不画美术意义上的“图”，而是一种用顶点（点）和边（线）建模关系的语言——就像拼音是汉字的注音工具，图论是现实世界中“连接性”问题的注音工具。
《哈工大集合论与图论（下）慕课MOOC答案》这份资源，不是一份“抄作业指南”，而是一套跟着名校课程节奏走的伴学脚手架：它覆盖从“什么是图”到“怎么判断一张图能不能一笔画完（欧拉图）”“能不能不重复地逛遍所有景点（哈密顿图）”这些经典问题，每讲都对应慕课视频里的核心逻辑断点。你不需要先会证明定理，也能靠它看清题目在考什么、选项在比什么、为什么选A不选B——尤其当慕课题库反复出现相似题干、只改数字或边方向时，这份材料就是你的“防错对照表”。适合零基础但想真正看懂图论在解决什么问题的人，也适合被“度数”“连通分支”“补图”这些词绕晕、需要有人一句句拆开讲的新手。
2. 先搞懂一个概念：图不是“图形”，而是“关系快照”
2.1 为什么非得用“点和线”来描述世界？
想象你刚接手一个校园快递站的调度任务。站点有5个取件点（A、B、C、D、E），每天要派3辆小车把包裹送到各点。你手头只有一张手绘草图：A连B、B连C、C连D、D连E——看起来像条直线。但实际呢？
- A和E之间可能有直达班车（现实中存在但图上没画）；
- B到C的路正在维修（边存在但暂时不可用）；
- D点今天爆单，需要两辆车同时服务（顶点有“权重”）。
如果只盯着这张草图，你会漏掉所有动态信息。而图论的第一步，就是逼你把“能连”和“不能连”、“有向通行”和“双向通行”、“连的成本高低”全部显式写出来。它不美化现实，只做最简抽象：
- 顶点（Vertex）= 你关心的实体（人、服务器、城市、网页）；
- 边（Edge）= 它们之间可定义的关系（朋友、数据链路、航班、超链接）；
- 图（Graph）= 这些顶点+边组成的整体结构快照。
提示：别纠结“图”字本身。它和“函数”“矩阵”一样，是个数学容器名——装的是关系，不是画面。
2.2 四种基础图型，一眼分清它们在解决什么问题
慕课第一讲就列了简单图、有向图、无向图、加权图。新手常卡在“记混定义”，其实只要抓住每个类型对应的现实约束，就很难忘：
| 图类型 | 关键特征 | 现实类比 | 题目里怎么认它？ |
|---|---|---|---|
| 简单图 | 任意两点间最多1条边；无自环（自己连自己） | 微信好友关系：A和B只能有1个好友请求记录；没人能加自己为好友 | 题干出现“无重边、无环”“任意两点至多一条边” |
| 无向图 | 边没方向，A-B 和 B-A 是同一条边 | 双向公路：从A到B和B到A走的是同一条路 | 题干说“边表示连接”“不考虑方向”；邻接矩阵一定对称 |
| 有向图 | 边有箭头，A→B ≠ B→A | 单行道/关注关系：你关注大V，大V不一定回关你 | 题干出现“有向边”“弧”“入度/出度”；邻接矩阵不对称 |
| 加权图 | 每条边标数字（权重），代表距离/成本/容量 | 地图App显示的实时路况：A到B高速30分钟，小路45分钟 | 题干给出“边权”“长度”“费用”；计算题里要加总边权 |
举个具体例子：慕课第1讲选择题常考“下列哪个是简单图？”
A. 顶点集{A,B,C}，边集{(A,B), (B,C), (C,A)} B. 顶点集{A,B,C}，边集{(A,B), (A,B), (B,C)} C. 顶点集{A,B,C}，边集{(A,A), (B,C)} D. 顶点集{A,B,C}，边集{(A,B), (B,C), (C,A), (A,C)}对照定义：
- B有两条A-B边 → 违反“无重边” → 排除；
- C有(A,A)自环 → 违反“无环” → 排除；
- D中A和C连了两次？不，(A,C)只出现一次，且A-C边和C-A是同一条（无向图）→ 合法；
- A完全符合：三点互连，无重边无环 → 正确答案。
关键不是背定义，而是养成习惯：看到选项，立刻问“这里有没有偷偷加自环？有没有重复边？方向标没标清楚？”——这比死记“简单图=无重边无环”管用十倍。
2.3 邻接矩阵 vs 邻接表：不是“哪个更好”，而是“哪个更省事”
慕课讲图的表示方法时，常让学生画邻接矩阵。但很多新手画完就懵：为什么一个5个点的图，要画5×5的表格？这和解题有什么关系？
其实，这两种表示法本质是同一张图的两种“存档格式”，选哪个取决于你要做什么：
- 邻接矩阵：像Excel表格，行和列都是顶点，格子填1/0表示“有/无边”。优点是查任意两点是否相连，O(1)时间搞定（直接看格子）；缺点是点太多时（比如1000个顶点），要存100万个格子，大部分还是0（稀疏图）。
- 邻接表：像微信通讯录，每个顶点名下记一串它连着谁。优点是只存真实存在的边，省空间；缺点是查A和Z连不连，得翻遍A的列表找Z，慢一点。
慕课习题里，90%的矩阵题只考一件事：看矩阵对称性判断是否有向。
比如给一个3×3矩阵：
[0 1 0] [0 0 1] [1 0 0]- 第一行[0 1 0]：顶点1连到顶点2；
- 第二行[0 0 1]：顶点2连到顶点3；
- 第三行[1 0 0]：顶点3连到顶点1。
→ 这不是对称矩阵（比如位置[1,2]=1，但[2,1]=0），所以是有向图。
新手血泪经验：别急着画满整个矩阵！先扫一眼“对角线以外的数”，找一对不对称的位置（如[1,2]和[2,1]值不同），立刻能判是否有向。这招在考试里省至少2分钟。
3. 连通图、补图、偶图：三个听起来玄乎，其实都在回答“这张网牢不牢”
3.1 连通图：不是“所有点都连着”，而是“所有点都能互相抵达”
新手最大误区：看到图里A-B-C-D排成一串，就以为“连通”。但连通图的定义是——对图中任意两个顶点u和v，都存在一条路径（一串连续的边）从u走到v。
重点在“任意”和“路径”。
- 如果图里有5个点，但只画了A-B、C-D两条边，E孤零零——这不是连通图，是3个连通分支（{A,B}, {C,D}, {E}）；
- 如果A-B-C-D连成一串，但B和D之间还有一条边，它还是连通图（多一条路而已，不破坏定义）；
- 如果是有向图，连通性更严格：得区分“弱连通”（忽略方向后连通）和“强连通”（有向路径双向都存在）。
慕课第2讲的典型题：“判断下列图是否为连通图”，往往配一个带6个点的草图。别慌着数边，用铅笔模拟走路：
- 从任意点出发（比如标号1的点）；
- 沿着边走到所有能到的点，标上“已访问”；
- 看还有没有没标过的点——有，就不连通；全标完了，就连通。
这就是“深度优先搜索（DFS）”的手动版，也是你理解算法前最该练的直觉。
3.2 补图：原图的“镜像世界”，专治“找不到反例”的焦虑
补图的定义很绕：“给定一个简单图G，它的补图Ḡ是这样一个图：顶点集和G相同，边集包含所有G中没有的边。”
听不懂？换个说法：补图就是把原图的“不存在关系”全部变成“存在关系”，“存在关系”全部抹掉。
举个生活例子：假设一个班有4个同学{A,B,C,D}，原图G表示“互相借过笔记的同学对”。如果G的边只有(A,B)、(B,C)，说明：
- A和B借过，B和C借过；
- A和C没借过，A和D没借过，B和D没借过，C和D没借过。
那么补图Ḡ的边就是：(A,C)、(A,D)、(B,D)、(C,D)——所有G里没出现的点对。
为什么学这个？因为慕课题常考：“若G是连通图，Ḡ是否一定连通？”
- 直接想难，但用小例子试：
- G是3个点一条线（A-B-C）→ 连通；Ḡ的边是(A,C)，A和C连了，但B是孤点 → Ḡ不连通。
- 所以答案是“不一定”。
避坑 / 常见问题 / 排查
现象：画补图时漏掉某些边，导致边数算错。
原因：忘了“补图只针对简单图”，原图若有重边或自环，补图定义不适用；且补图边数 = C(n,2) - 原图边数（n是顶点数）。
解决：先数清原图边数，再用公式算理论边数，画完后核对总数。现象：误以为补图的连通性一定和原图相反。
原因：混淆“不连通”和“一定连通”。事实上，存在G和Ḡ都连通的情况（如4个点的环图C₄）。
解决：记住结论：“G连通，Ḡ不一定连通；但若G不连通，Ḡ一定连通”（这是定理，可验证）。现象：在有向图里硬套无向图的补图定义。
原因：有向图的补图需考虑所有可能的有向边（共n(n-1)条），而非无向的C(n,2)条。
解决：题干没特别说明“有向补图”，默认讨论无向图。
3.3 偶图（二部图）：不是“边数为偶”，而是“能分成两组，组内不打架”
“偶图”这名字害惨新人——它和“边数是偶数”毫无关系！正确叫法是二部图（Bipartite Graph），核心是：能把所有顶点分成两个集合X和Y，使得每条边的两个端点必然一个在X、一个在Y。
类比：公司组织架构图。如果所有汇报关系都是“基层员工→组长→部门总监”，那么你可以把人分成“员工层”和“管理层”两组，所有箭头都从员工层指到管理层——这就是二部图。但如果有个组长也向另一个组长汇报，这条边就在“管理层”内部，破功。
慕课判断题常用“画图法”：
- 给一个图，让你判断是否为偶图；
- 方法：任选一点涂红色，它连的所有点涂蓝色，这些蓝点连的未涂色点再涂红色……直到涂完。
- 如果过程中出现“某点已被涂红，但它连的一个点也被涂红” → 冲突 → 不是偶图。
这就是二染色法，本质是检查图里有没有奇数长度的环（三角形、五边形等）。因为偶图禁止奇环——你可以试试：三角形ABC，A红→B蓝→C红，但C又连A（红），冲突！
注意：空图（无边）、树（无环）、偶环（四边形、六边形）都是偶图；奇环（三角形、五边形）一定不是。
4. 欧拉图：解决“能不能一笔画完所有边”的古老问题
4.1 欧拉路径 vs 欧拉回路：起点和终点是否重合，决定整张图的命运
1736年，数学家欧拉解决哥尼斯堡七桥问题时，提出两个概念：
- 欧拉路径：经过图中每条边恰好一次的路径（可以起点≠终点）；
- 欧拉回路：起点和终点相同的欧拉路径（即一笔画完，回到原点）。
慕课第3讲所有题都围绕这两个概念的判定条件展开。别怕记不住，用生活场景锚定：
- 欧拉回路 ≈ 快递员从仓库出发，送完所有街道（边）的货，最后回到仓库；
- 欧拉路径 ≈ 快递员从仓库出发，送完所有街道的货，停在最后一个小区，不用返回。
关键区别就一点：欧拉回路要求所有顶点度数为偶数；欧拉路径允许恰好两个顶点度数为奇数（起点和终点）。
为什么？因为每次经过一个顶点，就“进一次、出一次”，度数+2（偶数）。只有起点（只出不进）和终点（只进不出）会贡献奇数度数。
4.2 无向图判定口诀：数奇度顶点，看是0个还是2个
慕课选择题常给一个6个点的图，标出各点度数，问“是否存在欧拉回路”。
直接套口诀：
- 如果所有点度数都是偶数（0,2,4,6…）→ 存在欧拉回路；
- 如果恰好两个点度数是奇数（1,3,5…），其余为偶数 → 存在欧拉路径，但无回路；
- 如果奇度顶点数是1、3、5…（非0非2）→ 既无欧拉路径，也无欧拉回路。
例题：某图顶点度数为[3,3,2,2,2,2]
- 奇度顶点：前两个3 → 共2个 → 存在欧拉路径，无回路。
注意：这个口诀只适用于连通图！如果图本身不连通（比如分成两块），即使度数满足，也无法一笔画完所有边（中间断开了）。所以完整步骤是：
- 先确认图连通（用3.1节的“铅笔走路法”）；
- 再数奇度顶点个数。
4.3 有向图判定：入度=出度，才是欧拉回路的通行证
有向图的欧拉回路条件更精细：每个顶点的入度必须等于出度。
为什么？因为每次经过一个顶点，必须有一条边进来、一条边出去（除了起点/终点）。对于回路，起点=终点，所以所有点都满足“进=出”。
例题：有向图3个顶点A,B,C，边为A→B, B→C, C→A
- A：出度1（→B），入度1（←C）→ 平衡；
- B：出度1（→C），入度1（←A）→ 平衡；
- C：出度1（→A），入度1（←B）→ 平衡；
→ 存在欧拉回路。
避坑 / 常见问题 / 排查
现象：看到度数全为偶数，就选“有欧拉回路”，结果错了。
原因：忘了检查连通性。例如两个分离的三角形，每个点度数都是2（偶数），但无法一笔画完所有边（中间没路）。
解决：永远先问“这张图连通吗？”，再看度数。现象：把有向图的“度数”当成无向图算（只看总度数）。
原因：混淆概念。有向图中，“度数”分入度、出度；判定欧拉性只看出入度是否相等，不看总和。
解决：题干出现箭头，立刻切换模式：画表格，一列入度、一列出度，逐个对比。现象：认为“有欧拉路径就一定有欧拉回路”。
原因：没理解路径和回路的本质区别。路径允许起点终点不同，回路强制相同。
解决：记死：回路→所有点出入度相等（有向）或全偶度（无向）；路径→恰好两点不等（有向：一顶点出度=入度+1为起点，另一入度=出度+1为终点）。
5. 哈密顿图：解决“能不能不重复地逛遍所有景点”的旅行商难题
5.1 哈密顿路径 vs 哈密顿回路：关键词是“顶点”，不是“边”
如果说欧拉图关心“每条边走一次”，哈密顿图关心的是“每个顶点访问一次”。
- 哈密顿路径：经过图中每个顶点恰好一次的路径（不要求走完所有边）；
- 哈密顿回路：起点和终点相同的哈密顿路径（即逛完所有景点，回到出发点）。
类比旅游规划：
- 欧拉问题：把城市间的每条公路都巡逻一遍；
- 哈密顿问题：把每个城市都打卡一次，不重复去同一个城市。
核心差异一句话：欧拉看边，哈密顿看顶点。
5.2 判定难度：没有像欧拉那样简单的充要条件
这是哈密顿图最让新手崩溃的地方：目前没有已知的、像“奇度顶点数=0或2”那样快速判定的充要条件。它属于NP完全问题，意味着随着点数增加，穷举法会指数级变慢。
但慕课不考算法复杂度，考的是必要条件和构造反例：
- 必要条件1：图必须连通（显然，不连通肯定逛不完所有点）；
- 必要条件2：对任意顶点子集S，删除S后，图的连通分支数 ≤ |S|（这是著名的Bondy–Chvátal定理的简化版，慕课常以“割点”形式出现）；
- 最实用技巧：找割点或桥。如果删除某个顶点后，图分裂成3个以上连通分支，那它不可能有哈密顿回路（因为那个顶点最多只能“衔接”2个分支）。
例题：一个图有顶点A,B,C,D,E，其中A连B、C、D、E，其他点之间无边（星形图）。
- 删除A后，剩下B,C,D,E全是孤立点 → 4个连通分支；
- 而|S|=1（只删A），4 > 1 → 违反必要条件 → 无哈密顿回路。
5.3 “充分条件”不等于“一定能用”，但能救命
虽然没充要条件，但有些充分条件（满足则一定有哈密顿回路）在慕课题中高频出现：
- Dirac定理：若图有n≥3个顶点，且每个顶点度数 ≥ n/2，则图有哈密顿回路；
- Ore定理：若图有n≥3个顶点，且对任意不相邻的顶点u,v，都有deg(u)+deg(v) ≥ n，则图有哈密顿回路。
别背公式！用例子理解：
- 6个点的完全图（每两点都相连）：每个点度数=5，n/2=3，5≥3 → 满足Dirac → 有哈密顿回路；
- 5个点的图，某两点u,v不相邻，deg(u)=2, deg(v)=2，和=4 < 5 → 不满足Ore，但不等于没有回路（只是不能保证）。
避坑 / 常见问题 / 排查
现象：看到“每个点度数≥3”，就认为5个点的图一定有哈密顿回路。
原因：Dirac要求度数≥n/2，5个点需≥2.5→即≥3，看似满足。但Dirac是充分条件，不是必要条件；且必须图连通。
解决：先确认连通性，再检查是否满足定理前提；不满足≠不存在，只是不能用此定理保证。现象：把哈密顿路径的判定和欧拉路径混淆，用奇度顶点数去判断。
原因：欧拉看边，哈密顿看顶点，判定逻辑完全不同。
解决：在草稿纸上写两行提醒自己：“欧拉：边→度数；哈密顿：顶点→连通性/割点”。现象：试图用“画出来”验证哈密顿性，结果卡在第4个点就绕不回去了。
原因：手工穷举效率极低，且易遗漏。
解决：优先用必要条件排除（如找割点、检查连通性），而不是硬画。慕课题设计时，通常留有明显破绽（如一个顶点只连1条边，它必是路径端点）。
6. 下一步学什么：从“看懂答案”到“自己推导”，我的三步踩坑路线
你已经知道这份《哈工大集合论与图论（下）慕课MOOC答案》是什么、为什么能帮你避开常见陷阱、怎么用它看懂连通性、欧拉性、哈密顿性的核心逻辑。但真正的门槛不在“看懂”，而在“自己动手推”。我第一次学时，也以为背熟判定条件就能通关，结果第一次作业就翻车：题目给了一个带权图，问“是否存在哈密顿回路”，我盯着度数看了十分钟，完全没注意题干里藏着“边权为负数”这个伏笔——而哈密顿问题本身不涉及权值，它只关心连通结构。那一刻我才明白：图论的“应用题”，考的不是记忆，而是“识别问题类型”的反射能力。
所以，接下来你要做的，不是继续刷更多题，而是建立自己的问题分类流水线。我把它拆成三步，每步对应一个你能立刻执行的动作：
6.1 第一步：给每道题贴“问题标签”，强制归类
拿到一道新题，别急着算，先用30秒做这件事：
- 在题干旁手写三个标签：【欧拉】/【哈密顿】/【连通性】（三选一）；
- 如果涉及边权（距离、费用、容量），额外加【加权】；
- 如果图里有箭头，加【有向】。
为什么有效？因为慕课题库的重复率高，本质是同一类问题换马甲。比如：
- “能否从A出发，走完所有道路回到A？” → 【欧拉】【回路】【无向】；
- “能否从A出发，访问所有城市一次，最后到B？” → 【哈密顿】【路径】【无向】；
- “删除哪个点，会让网络断成三块？” → 【连通性】【割点】。
贴标签的过程，就是在训练你的大脑自动匹配“问题场景→数学模型”。坚持一周，你会发现自己读题速度提升50%，因为80%的题，标签一贴，解法就浮出来了。
6.2 第二步：用“最小反例”验证直觉，比背定理更可靠
定理容易忘，但亲手造一个反例，会刻进肌肉记忆。建议你为每个核心概念，准备一个“最小反例本”：
| 概念 | 最小反例（手动画） | 为什么它反例？ | 慕课题里怎么防？ |
|---|---|---|---|
| 连通图 | 两个孤立点A、B | 任意两点间无路径 | 题干若说“图由两部分组成”，立刻警觉 |
| 欧拉回路 | 三角形ABC（3个点全连） | 每个点度数=2（偶数），但它是连通的 → 实际有回路！等等，这不算反例… 正确反例：两个分离的三角形 → 不连通，度数全偶，却无欧拉回路 | 看到“度数全偶”，马上补问“图连通吗？” |
| 哈密顿回路 | 星形图（中心A连B,C,D） | 删除A后，B,C,D互不连通（3分支 > | S |
每天花5分钟，画一个新反例，写清“它为什么能推翻某个错误直觉”。一个月后，你面对任何题，第一反应不再是“套公式”，而是“这个结构，我见过它的反例吗？”
6.3 第三步：把答案资源当“解题地图”，而不是“答案书”
这份MOOC答案最大的价值，不是告诉你第3题选C，而是暴露慕课出题人的思维断点。比如，你发现第2讲所有“补图”题，选项里总有一个陷阱：把有向图的补图当成无向图算。这意味着，出题人认定“学生容易混淆有向/无向的补图定义”。
所以，我的用法是：
- 做完一讲习题后，不急着对答案；
- 先整理自己错的题，按错误类型分类：【概念混淆】/【计算失误】/【漏看条件】；
- 再打开这份答案，重点看“它在哪一题标注了‘注意：此处有向’‘提示：补图仅对简单图’”，把这些提示抄到你的错题本对应位置。
久而久之，你的错题本会变成一张“高频雷区地图”，上面标记着：这里容易忘连通性，这里常错有向图度数，这里总漏看“简单图”前提……
从那以后我每次打开慕课视频，都会先暂停，拿出这张地图，快速扫一遍本讲可能踩的坑，再继续听课。不是为了不犯错，而是让错误发生得更早、更轻——在理解阶段暴露漏洞，总好过在考试时才发觉。
希望帮到你。
本文还有配套的精品资源，点击获取
