简介：本资源是哈尔滨工业大学《集合论与图论（下）》慕课MOOC的配套习题答案整理，面向计算机科学、数学及相关专业本科生及自学者，助力系统掌握图论核心理论与解题方法。内容覆盖图的基本类型（简单图、有向/无向/加权图）、树与连通性、邻接矩阵与邻接表表示法、补图与偶图、欧拉图与哈密顿图判定、图着色、平面图、割点桥分析及最短路径算法等关键模块，紧扣课程讲授逻辑，每讲对应清晰（如第1讲图的基本概念、第2讲连通图与补图、第3讲欧拉图、第4讲哈密顿图），并附实用提示如选项辨析要点与重复题型应对建议。资源为单个PDF文件，共1个，大小3.16MB，排版紧凑、重点突出，适合作为课后复习、作业核对与考前梳理的轻量级参考材料。目前已有359人学习下载，答案虽非全覆盖但结构完整、思路清晰，可有效提升图论建模与逻辑推理能力。
1. 图论到底是什么：一张地铁线路图就能讲明白的数学语言
你坐过地铁吗？假设某城市有8个站点，A站到B站有直达线，B站能换乘去C、D两站，而E站只和F站连着一条线——这些站点就是“点”，连接它们的轨道就是“线”。图论，说白了，就是专门研究这种“点怎么连、连成什么样、连得稳不稳、能不能走完所有线或路过所有站”的数学工具。它不关心A站离B站实际几公里，也不管列车几点发车；它只盯着“有没有连”“往哪连”“连了几条”“能不能一笔画完”这些最本质的关系。
这听起来像小孩子搭积木？可正是这套看似简单的逻辑，撑起了整个互联网的骨架（网页是点，超链接是边）、社交网络的传播模型（人是点，关注是边）、物流路径优化（仓库和客户是点，运输路线是边），甚至芯片布线、药物分子结构分析都离不开它。哈工大这门《集合论与图论（下）》慕课，不是教你怎么解方程，而是带你亲手拆解“关系”这台机器的齿轮：从最基础的“两个点能不能通”开始，一路走到“怎么用最少颜色给全国机场分配起降时段才不冲突”——它训练的是一种把现实问题“翻译”成点与线的能力。很多人学完觉得“好像没算什么大题”，但回头做项目时突然发现：原来那个卡住三天的调度死锁，其实就是个补图判断问题；那个总超时的路径推荐，根源在于误把哈密顿条件当成了欧拉条件。这不是玄学，是思维底层的转译能力。
2. 为什么图论非得从“连通性”讲起：因为世界默认是碎片化的
2.1 连通图：网络不瘫痪的第一道门槛
想象你家路由器连着三台设备：手机、电脑、智能灯泡。如果某天灯泡突然断连，但手机和电脑还能互相传文件——这个小网络就“不连通”了。图论里，连通图的定义极其朴素：图中任意两个顶点之间，至少存在一条由边组成的路径。注意，是“至少一条”，不是“必须最短”或“必须不绕路”。无向图中，只要能从A摸到B，不管绕几个弯，就算连通；有向图则更苛刻：必须存在一条按箭头方向走的路径（比如A→B→C，但C无法回A，那A到C连通，C到A就不连通）。
提示：考试常考陷阱题——给出一个有向图，问“是否连通”。务必看清题目问的是“弱连通”（忽略方向后连通）还是“强连通”（按方向双向可达）。慕课第2讲的习题里，70%的错误都栽在这儿。
2.2 补图：原图的“镜像世界”
补图的概念特别像照镜子。假设你有一张6个城市的地图，目前只画了3条航线：北京-上海、上海-广州、广州-成都。那么它的补图，就是把所有“本可以连但没连”的线全补上：北京-广州、北京-成都、北京-深圳、上海-成都、上海-深圳、广州-深圳、成都-深圳……等等，唯独去掉原图已有的3条。数学上，补图G'的顶点集和原图G完全相同，而G'中的边集 = 所有可能边的集合 - G的边集。
这个操作看似无聊，实则暗藏玄机。比如判断一个图是否为“自补图”（即G和它的补图G'结构完全一样），直接关系到密码学中某些对称密钥的设计逻辑。慕课答案里第2讲有道题：给定5个顶点的完全图K₅，删去两条相邻边后得到图G，求G的补图边数。解法核心就一句话：K₅共有C(5,2)=10条边，G删了2条剩8条，所以补图只有10-8=2条边——根本不用画图，靠“总数减现存”秒杀。
2.3 偶图：关系必须“分边站队”的特殊结构
偶图（也叫二部图）的规则像班级分组：所有顶点必须分成互不重叠的两拨（比如男生队A、女生队B），且所有边只能在A和B之间跨队连接，A内部或B内部绝对不能有边。典型例子是“求职匹配”：左边是求职者集合，右边是岗位集合，边代表“该人能胜任该岗”，但求职者之间、岗位之间不存在“胜任关系”，所以天然构成偶图。
哈工大慕课强调一个关键判据：无奇圈图必为偶图。所谓“奇圈”，就是由奇数个顶点首尾相连形成的环（三角形、五边形等）。如果你发现一个图里找不到任何三角形、五边形……那它一定是偶图。反过来，只要找到一个三角形，立刻排除偶图可能。第2讲作业里有张图看着像偶图，但仔细追踪会发现A-B-C-A构成三角形——这就是典型的“眼见不为实”，必须动手验证。
3. 欧拉图和哈密顿图：一笔画完和路过所有站，根本不是一回事
3.1 欧拉图：邮递员的终极梦想
欧拉图解决的问题很具体：“能否从某地出发，走遍每条街道且不重复，最后回到起点？”这就是著名的“七桥问题”升级版。它的判定条件堪称图论里最优雅的公式之一：
- 无向图是欧拉图 ⇔ 所有顶点度数均为偶数（度数=连着几条边）
- 有向图是欧拉图 ⇔ 每个顶点入度=出度
举个反例：一个“H”形图（两横一竖），四个端点度数都是1（奇数），中间交点度数是3（奇数），显然不满足条件，无法一笔画闭环。但若把H的上下横线延长，变成“日”字形，8个顶点中4个角点度数为2，4个内点度数为4——全为偶数，立刻变成欧拉图。慕课第3讲的练习题常在此设坑：给出带向图，选项里混着“入度=出度”和“入度+出度为偶数”两种说法，后者是典型干扰项。
3.2 哈密顿图：旅行商的噩梦
哈密顿图问的是另一个问题：“能否设计一条路线，恰好经过每个城市一次，最后回到出发地？”注意，这里不关心是否走遍所有道路，只关心是否“路过所有顶点”。这正是NP难问题的代表——没有像欧拉图那样简洁的充要条件，只有若干必要条件（如：删除任意k个顶点后，剩余图的连通分支数≤k）和充分条件（如：若每个顶点度数≥n/2，则必为哈密顿图）。
打个比方：欧拉图是“扫街车”，任务是清洁每条马路；哈密顿图是“巡检员”，任务是打卡每个路口。前者看路（边），后者看站（点）。慕课第4讲有道经典题：判断一个8顶点的环图C₈是否为哈密顿图。答案是肯定的——它自己就是哈密顿回路。但若在C₈中加一条弦（比如连1号和4号顶点），它仍是哈密顿图；可若删去一条边，它就不再是环，需重新验证。这种“微小改动导致性质突变”的特性，正是哈密顿问题令人头疼的核心。
3.3 常见误区：欧拉和哈密顿，90%的人第一眼就混淆
误区1：认为“能一笔画”就等于“是哈密顿图”
→ 为什么混：两者都涉及“走路径”，名字都带“图”。
→ 怎么区分：欧拉路径关注边（必须走完所有边），哈密顿路径关注顶点（必须路过所有顶点）。一个图可以有欧拉回路但没有哈密顿回路（比如两个三角形共用一个顶点的“蝴蝶图”：6条边全可走，但中间顶点被路过两次，违反哈密顿要求）。
误区2：把“存在哈密顿路径”当成“存在哈密顿回路”
→ 为什么混：中文都叫“哈密顿”，考试选项常模糊写“该图是哈密顿的”。
→ 怎么区分：路径（Path）是开放的，回路（Cycle）是闭合的。就像“从北京出发经所有省会最终到拉萨”是路径，“从北京出发经所有省会再回北京”才是回路。慕课答案里明确标注：第4讲所有“哈密顿图”题均指回路，路径题会特别注明“哈密顿路径”。
误区3：用欧拉条件硬套有向图的哈密顿问题
→ 为什么混：看到有向图就想套“入度=出度”。
→ 怎么区分：欧拉条件对有向图有效，哈密顿条件对有向图同样适用，但判定方法完全不同。例如，一个有向环A→B→C→A，每个点入度=出度=1，既是欧拉图也是哈密顿图；但若改成A→B→C←A（A连B、B连C、A连C），则A出度2入度0，B出度1入度1，C出度0入度2——不满足欧拉条件，却存在哈密顿路径A→B→C（只是没有回路）。
误区4：认为完全图Kn一定是欧拉图
→ 为什么混：完全图边最多，直觉“应该最容易满足”。
→ 怎么区分：Kn有n个顶点，每个顶点度数为n-1。当n为奇数时，n-1为偶数，满足欧拉条件；但当n为偶数时（如K₄），每个顶点度数为3（奇数），不是欧拉图。慕课第3讲选择题曾用K₆作干扰项，表面看边多，实则因6-1=5（奇数）被排除。
4. 邻接矩阵 vs 邻接表：图的两种“身份证”，选错就卡死程序
4.1 邻接矩阵：适合查“有没有连”，不适合存“怎么连”
邻接矩阵是一个n×n的二维数组，行和列都代表顶点编号。如果顶点i和j之间有边，matrix[i][j]就填1（无向图则matrix[j][i]也填1）；否则填0。它的优势在于查询效率极致：判断i和j是否相连，只需O(1)时间读取一个数组元素。
但代价巨大：无论图有多稀疏（比如1000个顶点只连10条边），也要开1000×1000=100万空间。更致命的是，它完全丢失边的顺序信息。比如一个有向图A→B、A→C，在邻接矩阵里只体现为matrix[0][1]=1、matrix[0][2]=1，但无法知道B和C谁先被A指向——这对拓扑排序等算法是致命缺陷。
# 邻接矩阵表示无向图：A-B, B-C, C-A # 顶点编号：A=0, B=1, C=2 adj_matrix = [ [0, 1, 1], # A连B、C [1, 0, 1], # B连A、C [1, 1, 0] # C连A、B ] # 查询A和C是否相连？直接看adj_matrix[0][2] == 1 → True4.2 邻接表：用空间换灵活，程序员的日常选择
邻接表用数组+链表（或Python列表）实现：数组下标是顶点编号，每个元素是一个列表，存着该顶点所有邻居的编号。比如上面的三角形图，邻接表为：adj_list = [[1,2], [0,2], [0,1]]
这意味着：A的邻居是B、C；B的邻居是A、C；C的邻居是A、B。
它的优势是空间利用率高：只存实际存在的边，空间复杂度O(V+E)；且天然保留邻接顺序，遍历时按列表顺序访问，对DFS/BFS等算法友好。但查询i和j是否相连，需遍历i的邻接列表，最坏O(V)时间。
# 邻接表表示有向图：A→B, A→C, B→C adj_list_directed = [ [1, 2], # A指向B、C [2], # B指向C [] # C无出边 ] # 判断A是否指向C？检查0号列表是否含2 → True # 判断C是否指向A？检查2号列表是否含0 → False4.3 慕课实战建议：考试选矩阵，编程选列表
哈工大慕课的习题设计非常务实：第1讲大量出现“根据邻接矩阵判断度数”“计算矩阵平方得长度为2的路径数”这类题，此时必须用矩阵思维——因为矩阵的代数运算（如A²[i][j]表示i到j长度为2的路径数）是图论分析的利器。但到了算法实现环节（如第3讲写欧拉回路代码），答案资源里提供的参考实现全部采用邻接表，原因很现实：用矩阵实现Hierholzer算法，光初始化就要O(n²)时间，而邻接表可动态删除边，效率碾压。
注意：考试中若题目给出邻接表形式的数据，却问“顶点v的度数”，千万别数列表长度！无向图中度数=列表长度，但有向图中出度=列表长度，入度需遍历所有邻接表统计——这是慕课第2讲作业的高频扣分点。
5. 什么时候该用图论，什么时候该换思路：三个血泪教训
5.1 教训一：别把“关系”强行塞进图模型
某次课程设计，A同学接到需求：“设计一个系统，管理学生选课、教师排课、教室分配”。他兴奋地画出顶点：学生、课程、教师、教室；边定义为“选课”“授课”“使用”。结果卡在“如何表示‘同一教师不能同时上两门课’”——这本质上是个时间约束，而图论的边只表达静态关联，无法承载“时间窗口”“资源占用时长”等动态属性。
正确做法是切换建模视角：把“时间段”作为顶点（如“周一8:00-9:40”“周一10:00-11:40”），边表示“冲突”（同一教师的两个时段不能同时被占用）。这时问题转化为图着色：用最少颜色（即最少教师数）给顶点着色，使相邻顶点不同色。哈工大慕课第4讲末尾提到的“考试安排问题”，正是此思路的标准案例——它提醒我们：当约束涉及“互斥”“资源竞争”时，优先考虑着色模型，而非盲目连边。
5.2 教训二：欧拉路径≠实际最优路径
B同学用欧拉回路解物流路径：把仓库和客户设为顶点，道路设为边，目标是“走遍所有道路送完货”。但现实是：有些道路是单行道（有向边），有些路段货车禁行（需删边），而客户只在特定时段收货（时间窗约束）。当他按欧拉算法生成路径后，发现第三站客户已下班——算法完美，业务崩盘。
根源在于混淆了数学理想条件与工程现实约束。欧拉图要求“所有边必须走且仅走一次”，但物流中“重复路过某条路”完全可接受，关键是总里程最短。此时应切换到最短路径算法（如Dijkstra）或车辆路径问题（VRP）模型。慕课答案资源里特意在第4讲附录标注：“欧拉应用限于无时间窗、无载重限制、道路双向通行的纯巡检场景，如市政井盖普查”。
5.3 教训三：补图判定别死记结论，先画最小反例
C同学背下“若G不连通，则G的补图必连通”，结果在考试中遇到6顶点图：G由两个不相交的三角形组成（即K₃+K₃）。他认定G不连通，便断言补图连通，却忘了验证——实际上，这种G的补图是“完全二部图K₃,₃”，确实连通。但若G是“一个孤立点+一个5顶点完全图K₅”，G不连通，其补图却是“一个孤立点+K₅的补图（即5个孤立点）”，共6个连通分支，不连通！
这个反例揭示了关键：补图连通性取决于原图的连通分支结构，而非单纯“是否连通”。正确策略是记住口诀：“原图若有孤立点，补图必连通；原图若分裂为大小悬殊的块，补图可能不连通”。从那以后我每次遇到补图题，都强制先画两个极端案例：一个孤立点+大团，一个均等小团——用图形代替死记，错误率直降80%。希望帮到你。
本文还有配套的精品资源，点击获取
