图论概念映射训练：从简单图、二部图到补图的精准理解-平芜编程栈

简介：本资源是哈尔滨工业大学《集合论与图论（下）》慕课MOOC的配套习题答案整理，面向计算机、数学及相关专业本科生及自学者，助力系统掌握图论核心理论与解题思路。内容覆盖图的基本类型（简单图、有向/无向/加权图）、树与连通性、邻接矩阵与邻接表表示法、补图与偶图、欧拉图与哈密顿图判定、图着色、平面图、割点桥及最短路径算法等关键模块，紧扣课程讲授逻辑与高频考点。资源为1个PDF文件，大小3.16MB，排版清晰、章节对应明确（含第1讲图的基本概念至第4讲哈密顿图），便于逐讲对照复习与自查。目前已有361人学习下载，答案经人工梳理整合，注重选项辨析与典型题型归纳，虽非官方发布但结构完整、要点突出，适合作为课后巩固、考前冲刺与自学验证的实用参考材料。

1. 图论不是“画图题”：为什么哈工大这门课的答案集，能帮你绕过90%的抽象陷阱？

你有没有试过对着一道图论题发呆十分钟——题目里全是“顶点”“边”“连通分支”“度序列”，但就是找不到下手点？不是计算错，而是根本没读懂它在问什么。这不是你数学差，是图论这门课有个隐藏门槛：它不考算术，考的是概念映射能力——把文字描述精准地翻译成图结构，再把图结构的性质反向还原成逻辑断言。而哈工大《集合论与图论（下）》慕课的题库，恰恰踩在了这个映射最易断裂的几个节点上：比如“补图的连通性是否一定与原图相反？”“偶图的定义里‘偶’到底修饰的是边数、顶点数，还是二部划分的大小？”——这些题表面在考定义，实则在测试你有没有把“偶图 = 二部图”这个等价关系真正内化为直觉。这份答案集的价值，不在于抄答案，而在于它用高频重复题+选项对比的方式，把那些教科书里一笔带过的“显然成立”“易证”“同理可得”，全部拆解成可验证的中间步骤。它逼你停下来想：为什么“欧拉图要求所有顶点度数为偶数”这条定理，在有向图里要改成“入度=出度”？因为无向图的一条边贡献2度，而有向图的一条边只贡献1入度+1出度——这个底层计数逻辑，才是你真正该焊进脑子的“图论肌肉记忆”。搞懂这个，你才不是在背答案，是在训练一种新的思维操作系统。

2. 概念锚点：为什么“简单图”“偶图”“补图”这三个词，必须从定义源头重新拧紧？

图论的很多翻车，都源于对基础概念的“模糊共识”。比如看到“偶图”，第一反应是“边数为偶数的图”？错。看到“补图”，下意识觉得“把原图的边全删掉，再把没连的边全加上”？也不完全对。哈工大这门课的答案集之所以有效，是因为它用高频题反复锤打这些概念的精确定义边界——不是让你死记，而是让你在选项对比中被迫厘清每一个量词、每一个限定条件。我们来拆解三个最容易被惯性思维带偏的核心概念。

2.1 简单图：为什么“无环无重边”是铁律，而不是可商量的风格？

简单图（Simple Graph）的定义是：不含自环（loop）且不含平行边（multiple edges）的无向图。注意，这里有两个“无”，缺一不可。很多初学者会忽略“无环”这一条，导致在判断补图或构造反例时出错。例如，一道典型题问：“一个有4个顶点的简单图，其补图是否可能含有自环？”答案必然是“否”，因为补图的定义前提是“在同一个顶点集上，对所有未出现的边进行补充”，而简单图的顶点集本身就不允许自环存在，所以补图的边集自然也不可能包含自环。这个逻辑链的关键在于：补图操作不改变顶点集，只改变边集；而简单图的顶点集定义隐含了“自环不被允许”这一元规则。

# 模拟简单图的邻接矩阵表示（以4顶点为例） # 注意：对角线元素必须全为0，代表无自环 adj_matrix_simple = [ [0, 1, 0, 1], # 顶点0连接1和3 [1, 0, 1, 0], # 顶点1连接0和2 [0, 1, 0, 1], # 顶点2连接1和3 [1, 0, 1, 0] # 顶点3连接0和2 ] # 如果某行某列的对角线元素为1，它就不再是简单图

这段代码展示的不是一个算法，而是一个定义检查器：简单图的邻接矩阵，对角线必须全零。这是硬性约束，不是编码习惯。当你在慕课题里看到“给定一个图G，判断其补图G'是否为简单图”时，第一步永远是确认G本身是否满足简单图定义——如果G里有自环，那整个问题的前提就崩了，后续所有推理都无效。这就是为什么答案集里反复强调“选答案时要格外注意对比选项”：因为干扰项往往就藏在对“简单图”定义的松动理解里。

2.2 偶图：为什么“偶”字在这里与奇偶性毫无关系？

这是图论里最经典的术语陷阱。“偶图”（Even Graph）在中文教材里常被误用，但哈工大课程严格遵循国际惯例：这里的“偶图”实为“二部图”（Bipartite Graph）的旧译或误译，正确概念应为“二部图”。它的核心定义是：顶点集V可以划分为两个互不相交的子集X和Y（即V = X ∪ Y, X ∩ Y = ∅），使得图中每一条边的两个端点分别属于X和Y。换句话说，所有边都“跨部”，没有“内部边”。

提示：不要被“偶”字误导。二部图的顶点数、边数、部集大小都可以是奇数。例如，一个星形图K_{1,3}（中心1个顶点，外围3个顶点）是典型的二部图，但|X|=1（奇数），|Y|=3（奇数），总顶点数4（偶数），边数3（奇数）。它的“二部性”只取决于能否完成两分，与任何数值的奇偶无关。

判断一个图是否为二部图，标准算法是二染色法：尝试用两种颜色给顶点染色，要求相邻顶点颜色不同。若成功，则为二部图；若在染色过程中发现某条边两端颜色相同，则存在奇圈（odd cycle），必然不是二部图。慕课中大量题目考察的就是这个判定过程的逆向应用——给你一个结论（如“该图是二部图”），让你反推其结构限制（如“图中不能含长度为3的圈”）。

2.3 补图：为什么“补”不是简单的“取反”，而是一场顶点集的静默契约？

补图（Complement Graph）G' 的定义是：与原图G拥有完全相同的顶点集V，且对于V中任意两个不同顶点u和v，边(u,v)属于G'当且仅当(u,v)不属于G。关键点有三：

顶点集绝对一致：G和G'的顶点一个都不能少，一个都不能多；
只针对无序顶点对：补图操作默认在无向简单图语境下，因此只考虑u≠v的无序对{u,v}；
“补”的对象是“可能存在的边”的全集：这个全集是顶点集V上所有可能的无序对，共C(|V|,2)个，而非G中实际出现的边数。

这意味着，一个有n个顶点的图G，其补图G'的边数 = C(n,2) − |E(G)|。这个公式背后是组合数学的硬逻辑，不是图论的特例。慕课里有一道高频题：“若G是连通图，其补图G'是否一定不连通？”答案是“不一定”。反例是路径图P₄（4个顶点排成一排），它自身连通，其补图也连通。这个反直觉结论的根源，就在于补图的边数由顶点总数决定，而非G的连通性。当你在选项里看到“补图一定不连通”这种绝对化表述时，立刻该想到：它忽略了补图定义中那个静默的、强大的顶点集契约。

3. 结构判据：欧拉图与哈密顿图的判定，为什么一个可机械执行，一个却像黑匣子？

欧拉图（Eulerian Graph）和哈密顿图（Hamiltonian Graph）是图论中一对著名的“镜像难题”：它们描述的都是遍历性路径，但判定难度天壤之别。欧拉图的判定是多项式时间可解的，有明确、可验证的充要条件；而哈密顿图的判定是NP-完全问题，至今没有已知的高效通用算法。哈工大慕课的答案集之所以把这两讲并列，正是为了让你在做题的肌肉记忆里，刻下这种根本性的复杂度差异。

3.1 欧拉图：度数条件就是你的“编译器”，它会当场报错

欧拉图的核心是欧拉回路（Eulerian Circuit）：一条经过图中每条边恰好一次并回到起点的闭合路径。其判定条件简洁到残酷：

无向图G是欧拉图 ⇔ G连通且所有顶点的度数均为偶数
有向图D是欧拉图 ⇔ D弱连通（忽略方向后连通）且每个顶点的入度 = 出度

这个条件为什么成立？根源在于边的消耗守恒。想象你沿着一条路径行走：每次进入一个顶点，就消耗一条入边；每次离开，就消耗一条出边。对于起点/终点重合的回路，每个顶点的“进入次数”必须等于“离开次数”。在无向图中，“进入”和“离开”都体现为度数，所以度数必须是偶数（2的倍数）；在有向图中，这直接对应入度=出度。这是一个计数层面的必然，不是概率或经验。

def is_eulerian_undirected(adj_matrix): n = len(adj_matrix) # 检查连通性（BFS/DFS） visited = [False] * n from collections import deque q = deque([0]) visited[0] = True while q: u = q.popleft() for v in range(n): if adj_matrix[u][v] == 1 and not visited[v]: visited[v] = True q.append(v) if not all(visited): return False # 不连通 # 检查所有顶点度数是否为偶数 for u in range(n): degree = sum(adj_matrix[u]) if degree % 2 != 0: return False return True # 示例：一个4顶点的环图 C4，邻接矩阵如下 c4_matrix = [ [0,1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1,0] ] print(is_eulerian_undirected(c4_matrix)) # True

这段Python代码不是为了生产环境，而是为了可视化判定逻辑的刚性。它强制你走完两步：先确保图连通（这是存在路径的前提），再逐个检查度数（这是路径能闭合的充要条件）。慕课题里常见的陷阱是：给出一个度数全为偶数但不连通的图（比如两个分离的三角形），然后问“是否为欧拉图？”——答案是否定的，因为连通性是前置条件，不是可选附加项。这个代码块提醒你：在欧拉图的世界里，没有“差不多”，只有“全满足”或“立刻失败”。

3.2 哈密顿图：为什么“每个顶点恰好一次”会引爆计算复杂度？

哈密顿图关注的是哈密顿回路（Hamiltonian Circuit）：一条经过图中每个顶点恰好一次并回到起点的闭合路径。注意，这里是“顶点”，不是“边”。这个微小的主语变化，让问题难度跃升几个数量级。

原因在于：哈密顿回路的约束是全局性的、组合爆炸式的。欧拉回路的每一步只关心“这条边我还没走过”，选择是局部的；而哈密顿回路的每一步都在做“这个顶点我还能不能去”的全局决策，因为它必须保证最后能回到起点，且不遗漏任何一个。这本质上是旅行商问题（TSP）的图论版本，其状态空间是顶点数n的阶乘级（O(n!)）。

目前没有已知的多项式时间充要条件。我们只有若干充分条件（满足则一定是哈密顿图）和必要条件（不满足则一定不是），但它们都不完备。例如：

Dirac定理（充分条件）：若G是n≥3的简单图，且每个顶点的度数 ≥ n/2，则G是哈密顿图。
Ore定理（充分条件）：若G是n≥3的简单图，且对任意两个不相邻顶点u,v，有deg(u)+deg(v) ≥ n，则G是哈密顿图。
必要条件：若G是哈密顿图，则对G的任意非空真子集S，G−S的连通分支数 ≤ |S|（即“割点集大小必须足够大”）。

慕课答案集的价值，在于它用具体题目逼你区分这些定理的适用边界。比如一道题给出一个5顶点图，各顶点度数为[2,2,2,2,2]，问是否为哈密顿图。根据Dirac定理，n/2 = 2.5，而所有度数=2 < 2.5，所以Dirac定理不适用；但这并不意味着它不是哈密顿图（事实上，5个顶点的环C₅就是哈密顿图）。你必须回归定义，手动尝试构造——而这正是哈密顿问题的“玄学”所在：它拒绝被机械化，只接受构造性证明或反例。

3.3 避坑：欧拉与哈密顿判定中，5个血泪换来的常见错误

做图论题最痛苦的，不是不会，而是“以为会了，结果全错”。以下是基于哈工大慕课高频题和学生反馈总结的5个典型坑，每个都附带真实题干片段、错误原因和修正方法：

现象：题干说“图G有6个顶点，每个顶点度数为3”，选项A称“G必为欧拉图”。
原因：忽略了连通性前提。6个顶点、度数全为3的图，边数 = (6×3)/2 = 9，但这样的图可以是两个分离的K₃,₃（完全二部图），每个K₃,₃有6顶点、9边、度数全为3，但它不连通，故不是欧拉图。
解决：看到“度数全偶”时，第一反应必须是“它连通吗？”——没有连通性，度数条件就是废纸。
现象：题干给出一个有向图，顶点A入度=2、出度=2，顶点B入度=1、出度=3，其他顶点入度=出度，问是否为欧拉图。
原因：只检查了“所有顶点入度=出度”，却忘了“弱连通”这个隐藏条件。如果该图由两个分离的强连通分量组成，即使每个分量内部满足入度=出度，整体也不是欧拉图。
解决：有向图欧拉判定必须显式验证弱连通性，不能只看度数。
现象：题干说“G是哈密顿图”，问“G的补图G'是否一定也是哈密顿图？”选项为“是”。
原因：将哈密顿性错误地当作补图下的不变性质。反例：完全图K₅是哈密顿图，但其补图是空图（无边），显然不是哈密顿图。
解决：牢记“哈密顿性在补图下不保持”，这是高频考点。
现象：题干给出一个偶数个顶点的完全图K_{2n}，问是否存在哈密顿回路。
原因：认为“完全图太满，反而不好找路径”。实际上，K_n（n≥3）总是哈密顿图，因为你可以按任意顺序遍历所有顶点再返回。
解决：完全图是哈密顿图的“银弹”——只要n≥3，它就自动满足所有充分条件。
现象：题干说“图G有割点v，删除v后得到3个连通分支”，问“G是否可能为哈密顿图？”选项为“不可能”。
原因：混淆了必要条件与充要条件。割点存在只是“可能不是”的警示，不是死刑判决。例如，一个“星形+环”的复合图可能有割点但仍含哈密顿回路。
解决：看到割点，先用Ore或Dirac定理尝试证明；若失败，再尝试手动构造回路，不要直接否定。

4. 表示与转换：邻接矩阵与邻接表，为什么选择它，决定了你解题的速度与精度？

图的表示方法，远不止是数据结构选型问题。它是你与图“对话”的接口，直接影响你能否快速提取关键信息、避免逻辑漏洞。哈工大慕课的答案集之所以强调“整理不易”，正是因为很多题目的突破口，就藏在表示方法的转换细节里——比如，从邻接矩阵一眼看出度数，但从邻接表一眼看出连通分支。

4.1 邻接矩阵：为什么它是“全局视野”的代名词，也是稀疏图的内存黑洞？

邻接矩阵A是一个n×n的方阵（n为顶点数），其中A[i][j] = 1 表示存在从顶点i到顶点j的边（无向图中A是对称矩阵）。它的核心优势在于O(1)时间查询任意两点间是否有边，以及O(n)时间计算任意顶点的度数（对第i行求和）。

# 无向图邻接矩阵：对称性是它的DNA undirected_adj = [ [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1], [0, 1, 1, 0] ] # 计算顶点0的度数：sum(undirected_adj[0]) = 1+1+0 = 2 # 检查顶点1和3是否相连：undirected_adj[1][3] == 1 → True

但它的致命缺陷是空间浪费。一个有1000个顶点的稀疏图（平均每个顶点只连5个邻居），邻接矩阵需要1000² = 1,000,000个存储单元，其中99.5%是0。慕课里有一道题：“一个有100个顶点的图，边数少于200，用邻接矩阵表示是否合理？”答案是否定的，因为此时空间利用率低于0.02%。更隐蔽的陷阱是：邻接矩阵天然隐含了‘所有顶点编号连续且从0开始’的假设。如果你在纸上画图时顶点标号是{A,B,C,D}，强行套用矩阵索引[0][1]，就可能因映射错误导致整个分析崩盘。

4.2 邻接表：为什么它是“局部聚焦”的利器，也是连通性分析的加速器？

邻接表用一个数组（或字典）存储，每个元素是一个链表（或列表），记录该顶点的所有邻居。它的空间复杂度是O(n + m)（n顶点数，m边数），对稀疏图极其友好。

# 同样的无向图，用邻接表表示（字典形式） adj_list = { 0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2] } # 获取顶点1的所有邻居：adj_list[1] → [0, 3] # 判断顶点1和3是否相连：3 in adj_list[1] → True（但这是O(d)操作，d为顶点1的度数）

邻接表的优势在于天然支持深度优先搜索（DFS）和广度优先搜索（BFS）。要找连通分支，你只需从一个未访问顶点开始DFS，它会自动顺着指针“流淌”到所有可达顶点。慕课中关于“补图的连通性”或“偶图的二分性”的题目，最优解法几乎都是基于邻接表的遍历。但它的代价是：查询两点间是否有边，最坏需要O(n)时间（遍历整个邻居列表）。所以，当你看到一道题需要频繁查询“u和v是否相邻”，而图又很稠密，邻接表就不是最佳选择。

4.3 表示转换：为什么“矩阵转表”不是格式转换，而是思维模式切换？

在慕课答案集中，很多题目的解法提示会写：“建议先将给定邻接矩阵转换为邻接表，再进行BFS”。这绝不是为了炫技，而是因为不同的表示方法激活了大脑中不同的模式识别回路。邻接矩阵让你盯着整个图的“静态快照”，适合做全局统计（如度数分布、特征值）；邻接表则让你进入图的“动态流”，适合做路径探索（如找最短路、判断连通性）。

一个经典例子是判断“图是否为树”。树的定义是“无环连通图”，等价于“连通且边数 = 顶点数 - 1”。用邻接矩阵，你需要：

先用DFS/BFS检查连通性（需额外实现）；
再遍历矩阵求和得到边数（注意无向图要除以2）。

用邻接表，你只需：

在构建邻接表时，边数m就是所有邻居列表长度之和除以2；
连通性检查直接嵌入BFS过程中。

这个看似微小的差别，在限时慕课考试中，就是3分钟和8分钟的差距。答案集的价值，正在于它用真实题目告诉你：什么时候该切到矩阵模式，什么时候该切到表模式——这是一种工程师的直觉，只能通过大量“表示-问题”配对训练出来。

5. 设计取舍：为什么哈工大这门课的答案集，不提供“万能解题模板”，而坚持用高频题暴露你的思维盲区？

我第一次系统刷完这份答案集时，最大的震撼不是答案本身，而是它背后的教学设计哲学：它不试图教你“怎么解题”，而是 relentlessly（无情地）暴露你“为什么解不了题”。它没有给你一个“欧拉图判定四步法”或“哈密顿图构造七招”，而是用高度重复的题干变体，把你一次次推到同一个认知悬崖边——比如，连续三道题都问“补图的连通性”，但每次的原图结构都微妙不同：一个是连通但有割点，一个是不连通但每个分支都是完全图，一个是正则图。你无法靠记忆选项蒙混过关，必须在现场重构对“补图”定义的理解。

这种设计，直指图论学习的核心矛盾：图论的难点不在计算，而在建模。现实世界的问题（网络路由、社交关系、电路设计）不会以“请判断此图是否为二部图”的形式出现。它会说：“我们需要把用户分成两组，确保每组内部不发生冲突。”——这时，你脑子里必须瞬间完成两次映射：用户→顶点，冲突关系→边，分组需求→二部图判定。这个映射过程，没有任何模板可套，它依赖你对概念边界的绝对清晰。

我后来带某高校图论实验课时，把这份答案集作为预习材料。观察到一个有趣现象：那些总想“速成”的学生，会跳过题干直接背答案，结果在期中考试遇到新题型时全面溃败；而那些愿意花10分钟，把一道题的四个选项逐一用邻接矩阵画出来、再手动验证补图的学生，哪怕当时错了，两周后遇到同类题，正确率接近100%。区别在于，前者在积累“答案碎片”，后者在锻造“概念神经突触”。

所以，这份资源真正的“高级用法”，不是把它当答案手册，而是当概念压力测试仪。我的习惯是：拿到一道题，先遮住答案，强迫自己用三种方式验证：