★ FEATURED ARTICLE 简介本资源是哈尔滨工业大学《集合论与图论下》慕课MOOC课程的配套习题答案整理面向计算机、数学及相关专业本科生及自学者助力系统掌握图论核心理论与解题方法。内容覆盖图的基本类型简单图、有向/无向/加权图、树与连通性、邻接矩阵与邻接表表示法、补图与偶图、欧拉图与哈密顿图判定、图着色、平面图、割点桥分析及最短路径算法等关键模块紧扣课程讲授逻辑适合作为课后巩固、考前复习与自学核验的重要参考。资源为单个PDF文件大小3.16MB排版清晰、章节对应明确含第1–4讲完整答案便于离线查阅与重点标注。目前已有359人学习下载答案基于高频重复题型归纳整理并附有选项辨析提示虽非官方发布但结构完整、思路清晰可有效提升解题准确率与概念理解深度。1. 图论到底是什么——别被“点和线”骗了它其实是你手机里导航、社交推荐、甚至快递路径背后的隐形大脑你用地图App查路线时系统怎么知道哪条路最快你刷短视频平台为什么总能推给你想看的内容你点外卖骑手怎么在几十个订单里规划出最省时间的送单顺序这些看似毫不相干的事背后都藏着同一个数学工具图论。它不讲函数也不解方程只研究“谁连着谁”——把城市变成点顶点把道路变成线边把用户变成点把“关注”“点赞”变成线把商品变成点把“经常一起买”变成线。就这么简单两样东西搭出来的结构却能描述真实世界里最复杂的关联。《哈工大集合论与图论下慕课MOOC答案》这份资源不是一本习题集而是一份“带注释的通关地图”它对应的是国内高校公认扎实的图论入门课下半程从“图长什么样”一路走到“怎么用图解决真问题”。如果你刚学完集合论基础、正卡在“欧拉图和哈密顿图分不清”“邻接矩阵和邻接表到底该用哪个”“补图到底是把边全删了还是全加上了”这些具体困惑里——这份资料就是为你写的。它不替代听课但能帮你把老师讲的抽象定义立刻对上一个可验证、可对比、有上下文的答案参考。零基础没关系。只要你能看懂“A连B”“C没连D”就能跟着这份材料从第一讲的“什么是简单图”开始一讲一讲地把图论的骨架摸清楚。2. 先搞懂一个前提这份“答案”不是抄作业本而是帮你建立判断力的脚手架很多人第一次看到“慕课答案”四个字本能反应是“哦抄的吧”——这恰恰是新手最容易掉进的第一个认知坑。我们得先说透这份《哈工大集合论与图论下慕课MOOC答案》的价值根本不在“让你交差”而在于帮你建立一种关键能力在高度相似的选项中识别出那个唯一符合定义的正确答案。慕课题库有个特点题目重复率高但选项会微调。比如一道考“欧拉图判定”的题A选项说“所有顶点度数为偶数”B选项说“至少有两个顶点度数为偶数”C选项说“所有顶点度数为奇数”D选项说“存在一条经过每条边一次的路径”。表面看都沾点边但只有A完全满足无向图欧拉图的充要条件。如果你没真正理解定义光靠记忆“欧拉图能一笔画”就很容易选错C或D。这份答案的珍贵之处正在于它把每道题的判定依据直接锚定在教材定义上。它不是告诉你“选A”而是用简短注释点明“此处考察无向图欧拉图判定定理当且仅当所有顶点度数均为偶数”。你看一遍再做一遍同类题下次再遇到选项微调就能自己推理出来。这种能力在后续学算法比如判断一个网络能不能遍历所有链路而不重复、学数据库比如分析用户关系图有没有环、甚至学机器学习比如理解图神经网络GNN的输入结构时都是底层思维习惯。所以使用它的第一步不是打开文档找答案而是打开课程视频暂停在题目出现的那一刻先自己读题、划关键词、回忆定义再对照这份资料里的解析逻辑。你会发现很多“不会”其实只是定义没吃透而很多“会了”是因为你终于看清了题目在考哪个精确的数学条件。2.1 为什么必须从“图的基本概念”讲起——因为90%的翻车都发生在起点没站稳图论看起来简单但新手常犯一个隐蔽错误把生活语言直接套进数学定义。比如看到“连通图”第一反应是“我能从北京开车到上海”这没错但数学上“连通”特指图中任意两个顶点之间都存在一条由边组成的路径。注意是“任意两个”不是“大部分”是“存在路径”不是“有直达航班”。再比如“简单图”生活中说“这个图很简单”数学上它有明确定义没有环顶点到自身的边且没有重边同一对顶点间多于一条边的无向图。如果题目给了一张带自环的图问“这是简单图吗”答案就是“否”哪怕它只有3个点、2条边。这份资料的第一讲“图的基本概念”就是在帮你校准这种语言差异。它覆盖的类型非常典型无向图 vs 有向图无向图的边像一根绳子两端没区别有向图的边像单行道箭头方向决定谁能到谁。考试常考有向图的“入度”指向它的边数和“出度”它指向的边数必须分开算。加权图每条边标着数字比如距离、费用、延迟。这不是装饰是后续学最短路径Dijkstra、最小生成树Kruskal的前提。子图、生成子图、导出子图这三个词长得像但逻辑不同。子图是随便删点删边生成子图必须保留所有顶点只删边导出子图则是选定一部分顶点把它们之间原来所有的边都保留下来。考试题常让判断某个图是不是另一个图的导出子图关键就看“选中的点之间原图有的边这里是不是全都有”。提示不要试图背下所有定义。拿起一张白纸画4个点标为v1,v2,v3,v4然后按定义自己动手构造画一个简单图检查有没有环、重边画一个有向图标几个箭头算算v2的入度和出度再画一个加权图给几条边标上1,5,10。动手画三遍比看十遍定义记得牢。2.2 “连通图、补图、偶图”这组概念为什么总让人晕——用三个生活场景秒懂第二讲的这三个概念名字抽象但本质极清晰。我们不用术语轰炸直接用你能马上验证的例子连通图想象一个微信群。群里所有人顶点只要能通过“好友关系链”传话就算连通。比如A认识BB认识C那A和C就算连通哪怕他俩没加微信。但如果群里有个人D谁都不认识也没人认识他那整个群就不连通了——D是孤立点。图论里连通图要求任意两点间都有路径不连通的图会被分成若干个“连通分支”就像微信群里分成了几个小圈子圈子内能传话圈子间不能。补图这是个容易误解的点。补图不是“把图删干净”而是“把原图没连的边全连上已经连的边全断开”。举个例子原图只有3个点A,B,C只连了A-B这一条边。那么它的补图就是把A-C、B-C这两条边连上同时把A-B这条边去掉。结果补图里A和B不连但A连C、B连C。补图的顶点集和原图完全一样边集是“全可能边集”减去原图的边集。考试常考原图连通补图一定连通吗答案是否定的。上面3点例子中原图只有A-B不连通C是孤立点但它的补图A-C,B-C是连通的反过来也能构造出原图连通但补图不连通的例子。关键在理解“补”是相对“完全图”而言的。偶图二部图这个名字更直白——图里的所有点能分成两组比如男生组、女生组并且所有的边都只出现在组与组之间组内绝对没有边。比如“学生选课”学生是一组课程是一组边表示“某学生选了某课”学生之间、课程之间没有边。这就是典型的偶图。判断一个图是不是偶图有个血泪经验试着给所有顶点染两种颜色比如红和蓝要求每条边的两个端点颜色不同。如果能成功染色它就是偶图如果染着染着发现矛盾比如一个点既要是红又要是蓝那就不是。这个“二染色法”是考试和实际编程中最常用的判定手段。2.3 避坑新手在“图的基本概念”阶段最容易踩的5个坑现象做题时看到“有向图的度数”直接用无向图的“度数邻接点个数”去算。原因混淆了有向图的“入度”有多少边指向它和“出度”它指向多少边而“度数”在有向图里通常指两者之和但题目考的往往是单独的入度或出度。解决看到有向图第一反应写两列一列“入度”一列“出度”。计算前先确认题目问的是哪个。现象判断“补图”时以为要把原图的边全部删除再随便连几条新边。原因没抓住“补图是相对于完全图而言的”这个核心。完全图是n个点之间所有可能的边无向图是n(n-1)/2条有向图是n(n-1)条都连满的状态。解决先算出n个点的完全图有多少条边再减去原图的边数得到补图的边数。这是验算补图是否画对的最快方法。现象看到“偶图”以为只要点能分成两组就行忽略了“组内不能有边”这个硬性条件。原因生活化理解过度把“分组”等同于“偶图”。比如把朋友圈所有人按年龄分“青年”“中年”但青年之间依然互相关注有边这就不是偶图。解决画出分组后立刻检查每一组内部有没有任意两个点之间连了边有就立刻排除。现象做“子图”相关题把“生成子图”和“导出子图”弄反。原因记混了“生成保点删边”和“导出选点保边”的口诀。解决用缩写强化记忆“生顶点全留生下来的孩子一个都不能少”“导导出的点原边全要导出即提取原汁原味”。现象看到“简单图”的定义觉得“没有环和重边”很容易结果题目给了一个带平行边的图比如v1-v2之间有两条边还问是不是简单图。原因对“重边”理解不敏感以为只有画成两条完全重叠的线才算其实只要两个顶点间边数1就是重边。解决数边时对每一对顶点vi,vj单独统计它们之间有多少条边。大于1立刻判否。3. 从“能画出来”到“能算出来”欧拉图与哈密顿图是图论里最经典的两道分水岭第三讲和第四讲是整门课的转折点。前两讲在学“图长什么样”这两讲开始学“图能干什么”。欧拉图和哈密顿图听名字像孪生兄弟其实内核完全不同欧拉图关心的是“边”——能不能不重复、不遗漏地走完所有边哈密顿图关心的是“点”——能不能不重复、不遗漏地路过所有顶点。这个根本差异决定了它们的判定方法、应用场景和难度层级。欧拉图有明确、易验证的充要条件无向图所有顶点度数为偶数有向图每个顶点入度出度所以它是“能算出来”的哈密顿图至今没有多项式时间的通用判定算法属于NP难问题所以它是“能猜出来、但很难证出来”的。这份资料把这两讲放在一起正是为了让你在对比中建立清晰认知别被相似的名字迷惑先盯住问题对象边 or 点再选工具欧拉定理 or 哈密顿必要条件。3.1 欧拉图一笔画问题的数学化身3步判定法比心算还快欧拉图的现实感最强。小时候玩的“一笔画”游戏就是欧拉回路的雏形。它的数学价值在于提供了一种检验图结构是否“均衡”的方法。一个网络比如电路板布线、物流配送路线如果能形成欧拉回路意味着你可以设计一条路径让设备/车辆/信号遍历所有连接最终回到起点效率极高。判定它只需三步确认图的类型是无向图还是有向图题目一定会说明别跳过检查连通性必须是连通图或强连通图对有向图而言。如果图本身是散的肯定没法一笔画完。验证度数条件无向图所有顶点的度数必须是偶数。这是充要条件缺一不可。有向图每个顶点的入度必须等于出度。同样是充要条件。来看一个典型例题模拟题给定无向图G顶点集{v1,v2,v3,v4}边集{(v1,v2), (v2,v3), (v3,v4), (v4,v1), (v1,v3)}。问G是否为欧拉图解第一步是无向图。第二步画一下四个点围成一个四边形再加一条对角线v1-v3。显然任意两点都连通是连通图。第三步算度数。v1连v2,v4,v3 → 度数3v2连v1,v3 → 度数2v3连v2,v4,v1 → 度数3v4连v3,v1 → 度数2。v1和v3度数是奇数不满足“全为偶数”所以不是欧拉图。但注意它满足欧拉路径的条件恰好两个奇度数顶点所以可以一笔画但起点和终点必须是v1和v3。这份资料里对这类细微差别都有明确标注避免你把“欧拉路径”和“欧拉回路”混为一谈。3.2 哈密顿图旅行商问题的简化版为什么它让计算机科学家头疼如果说欧拉图是“走完所有路”哈密顿图就是“拜访所有城”。它要求找到一条路径哈密顿路径或回路哈密顿回路使得图中每个顶点恰好经过一次。这听起来很美但数学上极其困难。目前没有任何像欧拉定理那样简洁的充要条件。我们能用的主要是必要条件不满足则一定不是和充分条件满足则一定是以及一些实用的排除技巧。必要条件Dirac定理对于n个顶点的简单图如果每个顶点的度数都≥n/2那么它一定是哈密顿图。这是一个“够用就好”的强条件但不满足它不代表不是哈密顿图。常用排除法最有效割点法如果图中存在一个顶点v删除v后图的连通分支数≥3那么原图一定不是哈密顿图。因为哈密顿回路是一个圈删掉圈上一个点最多把圈切成一条链连通分支数1绝不可能变成3个以上碎片。度数和法对任意两个不相邻的顶点u和v如果deg(u)deg(v) n那么图不是哈密顿图。Ore定理举个避坑例子题目给一个5个顶点的图其中v1只连v2v2连v1和v3v3连v2和v4v4连v3和v5v5只连v4。这是一条链v1-v2-v3-v4-v5。问是否为哈密顿图答不是。因为哈密顿回路要求首尾相连形成圈而这条链的两端v1和v5度数都是1无法闭合。更严谨地用割点法删掉v2剩下v1孤立、v3-v4-v5连通共2个分支删掉v3剩下v1-v2、v4-v5也是2个分支。虽然没到3个但已暴露结构脆弱。而哈密顿图要求图是“1-连通”的删一个点仍连通这个链删掉中间点就断成两截显然不满足。3.3 避坑欧拉图与哈密顿图混淆的4个致命瞬间现象看到题目说“能否不重复地走完所有边”下意识去检查每个顶点的度数是不是都≥2。原因把哈密顿图的必要条件每个顶点度数≥2是哈密顿图的必要条件但非充分错误迁移到欧拉图上。欧拉图只认“奇偶性”不认“大小”。解决欧拉图只问“偶数”哈密顿图才问“够不够2”。建立条件反射见“边”→想“奇偶”见“点”→想“度数大小”。现象判断有向图欧拉性时只算了出度忘了入度或者把入度出度加起来当度数用。原因没区分有向图的度数定义。有向图的“度数”是入度出度但欧拉定理要求的是“入度出度”不是“入度出度偶数”。解决强制自己画表格左边列顶点中间列出度右边列入度最后加一列“入度出度”。三列并排一目了然。现象看到一个图有哈密顿路径就认为它也有哈密顿回路。原因路径和回路是不同概念。路径有起点终点回路首尾相接。一个链状图有哈密顿路径v1-v2-v3-v4但没有哈密顿回路因为v1和v4不连。解决题目问“哈密顿图”默认指存在哈密顿回路。如果只找到路径必须额外验证起点和终点是否相邻。现象用Dirac定理度数≥n/2去证明一个图是哈密顿图结果算出来v1度数2n522.5于是断定“不是哈密顿图”。原因Dirac定理是充分条件不是必要条件。它说“满足就一定是”但没说“不满足就一定不是”。这个图完全可能通过其他方式是哈密顿图。解决Dirac定理只用来“快速确认是”绝不用来“快速确认不是”。排除哈密顿图优先用割点法或Ore定理。4. 把抽象概念落地用邻接矩阵和邻接表亲手“看见”一个图的结构前面讲的都是“纸上谈兵”现在到了动手环节。图论要真正用起来必须把它变成计算机能处理的数据。而“邻接矩阵”和“邻接表”就是图论通往编程世界的两座桥。它们不是选择题而是必修课邻接矩阵适合小而稠密的图比如5个点边很多操作直观邻接表适合大而稀疏的图比如1000个用户每人只关注10个节省空间。这份资料虽是文字答案但它在解析题目时会明确指出“此题用邻接矩阵更易观察”或“此题用邻接表可快速找出所有邻居”教你根据问题选工具。下面我们就用一个统一的例子带你亲手构建这两种表示。4.1 邻接矩阵一张“谁和谁有关系”的二维表格我们还是用之前的5点链图顶点{v1,v2,v3,v4,v5}边{(v1,v2), (v2,v3), (v3,v4), (v4,v5)}。邻接矩阵是一个5×5的方阵行和列都按顶点顺序排列v1,v2,v3,v4,v5。规则超简单如果vi到vj有一条边无向图中vi-vj和vj-vi等价矩阵[i][j]位置填1否则填0。因为是无向图矩阵一定是对称的主对角线以外。构建过程第一行v1v1只连v2所以[0][1]1索引从0开始其余为0 →[0,1,0,0,0]第二行v2v2连v1和v3 →[1,0,1,0,0]第三行v3v3连v2和v4 →[0,1,0,1,0]第四行v4v4连v3和v5 →[0,0,1,0,1]第五行v5v5只连v4 →[0,0,0,1,0]最终邻接矩阵[[0,1,0,0,0], [1,0,1,0,0], [0,1,0,1,0], [0,0,1,0,1], [0,0,0,1,0]]注意主对角线全是0因为我们假设没有自环简单图。如果题目允许自环对角线对应位置填1。这个矩阵能直接回答很多问题v1的邻居是谁看第一行只有第1列v2是1 → 邻居是v2。v2和v4连吗看第二行第四列索引[1][3]是0 → 不连。图是连通的吗计算矩阵的幂A², A³...如果某次幂后所有非对角线元素都0说明任意两点间有路径。但手动算幂太麻烦所以邻接矩阵更适合小图的直观观察。4.2 邻接表一份“每个点的朋友圈”清单邻接表更贴近人的思维。它是一个列表列表的每个元素对应一个顶点里面存着这个顶点的所有邻居。对同一个5点链图v1: [v2]v2: [v1, v3]v3: [v2, v4]v4: [v3, v5]v5: [v4]在Python里它通常用字典实现graph { v1: [v2], v2: [v1, v3], v3: [v2, v4], v4: [v3, v5], v5: [v4] }优势立现查邻居快graph[v3]直接返回[v2, v4]O(1)时间。省空间只存储存在的边。5个点最多有10条边完全图但这个图只有4条边邻接表只存4个字符串而邻接矩阵要存25个数字。增删边方便给v1加个朋友v3graph[v1].append(v3)graph[v3].append(v1)无向图要双向加。4.3 避坑表示法选择与转换的3个实战陷阱现象题目要求“求v1的度数”你对着邻接矩阵把第一行所有1加起来得到1但答案是2。原因忘了无向图的邻接矩阵是对称的v1-v2这条边在矩阵里占了两个位置[0][1]和[1][0]。但度数是邻居个数不是矩阵里1的总数。解决算度数永远只看一行或一列别加总整个矩阵。第一行有1个1度数就是1。现象用邻接表表示有向图时把“v1→v2”只加在v1的列表里忘了v2的列表里不需要加v1。原因混淆了无向图双向添加和有向图单向添加。有向图的邻接表只记录“出边”。v1→v2只在v1的列表里加v2v2的列表里只有它指向的点。解决画个小箭头在草稿纸上箭头从谁出发就往谁的列表里加目标。现象需要判断两个图是否同构结构相同只是点标签不同你试图用邻接矩阵逐个比较发现标签顺序不同矩阵就不同于是判否。原因同构图的邻接矩阵只是行和列的顺序不同即存在一个置换矩阵P使得P·A1·P^T A2。直接比矩阵肯定不行。解决同构判定是难题新手应聚焦于不变量顶点数、边数、度数序列把所有顶点度数从小到大排序列相同才可能同构、是否存在三角形等。这份资料在相关题目解析里会提示用哪些不变量快速排除。5. 学完这四讲你的下一步该往哪里走——从“会做题”到“能建模”的跃迁路径学到这里你已经掌握了图论的核心骨架从基本概念点、边、图的类型到关键性质连通、补、偶再到两大经典问题欧拉、哈密顿最后落到了数据表示矩阵、表。但这只是开始。真正的图论能力不在于解出慕课的题目而在于当你面对一个新问题时能本能地问“这个问题能不能抽象成一张图”。比如你帮社团设计值班表发现“每个人不能连续值两天”“每天至少两人”这就可以建模成一个图顶点是所有“人-日期”组合边连接那些冲突的组合如张三周一和张三周二求一个独立集选中的点互不相邻就解决了。这种建模能力才是图论赋予你的“超能力”。下面是我为你规划的、可立即执行的三条进阶路径每条都配了具体动作不空谈5.1 路径一用Python把课堂知识跑起来推荐指数★★★★★理论不动手永远是雾里看花。用50行代码你就能亲手验证欧拉定理、画出邻接矩阵、甚至搜索哈密顿路径。这不是为了炫技而是为了获得“确定性反馈”——代码跑通了你就真的懂了报错了错在哪一清二楚。第一步安装并跑通基础环境确保你有Python 3.7然后安装NetworkX图论专用库pip install networkx matplotlib第二步复现“5点链图”的欧拉性判定import networkx as nx # 创建无向图 G nx.Graph() G.add_nodes_from([v1,v2,v3,v4,v5]) G.add_edges_from([(v1,v2), (v2,v3), (v3,v4), (v4,v5)]) # 打印每个顶点的度数 print(各顶点度数:, dict(G.degree())) # 输出: {v1: 1, v2: 2, v3: 2, v4: 2, v5: 1} # 判定所有度数是否为偶数 degrees [d for n, d in G.degree()] is_eulerian all(d % 2 0 for d in degrees) print(是否为欧拉图, is_eulerian) # False运行这段代码你会亲眼看到v1和v5度数是1奇数程序输出False。这就是最硬的证据。把边改成[(v1,v2), (v2,v3), (v3,v4), (v4,v5), (v5,v1)]首尾相连成环再运行度数全变2输出True。这种即时反馈比看十页解析都管用。5.2 路径二攻克一个真实小项目推荐指数★★★★☆选一个你生活中能接触到的小问题用图论建模解决。我当年第一个项目是优化宿舍楼的快递代取路线。目标让一个同学取件员一次性帮5个人取完快递路径最短。这本质上就是哈密顿路径问题5个快递点1个起点找最短访问顺序。步骤如下抽象把宿舍楼一层平面图简化标出5个快递柜位置v1-v5和取件员起点s。赋权用步数或秒数估算任意两点间的距离构成一个6×6的加权邻接矩阵。求解用NetworkX的nx.approximation.traveling_salesman_problem近似算法因精确解太慢求最短环。验证把算出的顺序如s→v3→v1→v5→v2→v4→s画在纸上量一下总长度和你随便走的路线比是不是真短了20%这个项目不追求完美但做完你会深刻理解哈密顿图不是纸上的概念它是解决“最优顺序”问题的数学语言。而且你顺手学会了如何把现实距离转化为图的权重这是建模的关键一步。5.3 路径三向“图神经网络GNN”眺望推荐指数★★★☆☆如果你对AI、机器学习感兴趣图论是GNN的基石。GNN能处理社交网络、分子结构、知识图谱等“关系型数据”而它的输入就是你刚学的邻接矩阵或邻接表。GNN的第一层就是对每个顶点聚合它邻居的特征就像你查graph[v3]拿到[v2,v4]然后把v2和v4的特征加起来。所以你现在学的邻接表就是未来读懂GNN代码的“母语”。不必现在就学GNN但可以做个标记当你看到一篇讲“GNN如何预测用户是否会购买某商品”的文章时试着去找到它的图结构——用户是点购买行为是边还是商品是点共同购买是边用你刚练熟的“建模三问”谁是点谁是边边有权重吗去拆解它。这种习惯会让你在未来接触前沿技术时少一层隔膜。从那以后我每次学一个新算法都强制自己用NetworkX造一个小图跑一遍再手动画出结果。哪怕只是验证一个度数我也要看到print()输出的数字和我心算的一致。这种“眼见为实”的确认感是驱散数学焦虑最好的后悔药。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
