简介本资源是哈尔滨工业大学《集合论与图论下》慕课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。类比公司组织架构图。如果所有汇报关系都是“基层员工→组长→部门总监”那么你可以把人分成“员工层”和“管理层”两组所有箭头都从员工层指到管理层——这就是二部图。但如果有个组长也向另一个组长汇报这条边就在“管理层”内部破功。慕课判断题常用“画图法”给一个图让你判断是否为偶图方法任选一点涂红色它连的所有点涂蓝色这些蓝点连的未涂色点再涂红色……直到涂完。如果过程中出现“某点已被涂红但它连的一个点也被涂红” → 冲突 → 不是偶图。这就是二染色法本质是检查图里有没有奇数长度的环三角形、五边形等。因为偶图禁止奇环——你可以试试三角形ABCA红→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→AA出度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只删A4 1 → 违反必要条件 → 无哈密顿回路。5.3 “充分条件”不等于“一定能用”但能救命虽然没充要条件但有些充分条件满足则一定有哈密顿回路在慕课题中高频出现Dirac定理若图有n≥3个顶点且每个顶点度数 ≥ n/2则图有哈密顿回路Ore定理若图有n≥3个顶点且对任意不相邻的顶点u,v都有deg(u)deg(v) ≥ n则图有哈密顿回路。别背公式用例子理解6个点的完全图每两点都相连每个点度数5n/235≥3 → 满足Dirac → 有哈密顿回路5个点的图某两点u,v不相邻deg(u)2, deg(v)2和4 5 → 不满足Ore但不等于没有回路只是不能保证。避坑 / 常见问题 / 排查现象看到“每个点度数≥3”就认为5个点的图一定有哈密顿回路。原因Dirac要求度数≥n/25个点需≥2.5→即≥3看似满足。但Dirac是充分条件不是必要条件且必须图连通。解决先确认连通性再检查是否满足定理前提不满足≠不存在只是不能用此定理保证。现象把哈密顿路径的判定和欧拉路径混淆用奇度顶点数去判断。原因欧拉看边哈密顿看顶点判定逻辑完全不同。解决在草稿纸上写两行提醒自己“欧拉边→度数哈密顿顶点→连通性/割点”。现象试图用“画出来”验证哈密顿性结果卡在第4个点就绕不回去了。原因手工穷举效率极低且易遗漏。解决优先用必要条件排除如找割点、检查连通性而不是硬画。慕课题设计时通常留有明显破绽如一个顶点只连1条边它必是路径端点。6. 下一步学什么从“看懂答案”到“自己推导”我的三步踩坑路线你已经知道这份《哈工大集合论与图论下慕课MOOC答案》是什么、为什么能帮你避开常见陷阱、怎么用它看懂连通性、欧拉性、哈密顿性的核心逻辑。但真正的门槛不在“看懂”而在“自己动手推”。我第一次学时也以为背熟判定条件就能通关结果第一次作业就翻车题目给了一个带权图问“是否存在哈密顿回路”我盯着度数看了十分钟完全没注意题干里藏着“边权为负数”这个伏笔——而哈密顿问题本身不涉及权值它只关心连通结构。那一刻我才明白图论的“应用题”考的不是记忆而是“识别问题类型”的反射能力。所以接下来你要做的不是继续刷更多题而是建立自己的问题分类流水线。我把它拆成三步每步对应一个你能立刻执行的动作6.1 第一步给每道题贴“问题标签”强制归类拿到一道新题别急着算先用30秒做这件事在题干旁手写三个标签【欧拉】/【哈密顿】/【连通性】三选一如果涉及边权距离、费用、容量额外加【加权】如果图里有箭头加【有向】。为什么有效因为慕课题库的重复率高本质是同一类问题换马甲。比如“能否从A出发走完所有道路回到A” → 【欧拉】【回路】【无向】“能否从A出发访问所有城市一次最后到B” → 【哈密顿】【路径】【无向】“删除哪个点会让网络断成三块” → 【连通性】【割点】。贴标签的过程就是在训练你的大脑自动匹配“问题场景→数学模型”。坚持一周你会发现自己读题速度提升50%因为80%的题标签一贴解法就浮出来了。6.2 第二步用“最小反例”验证直觉比背定理更可靠定理容易忘但亲手造一个反例会刻进肌肉记忆。建议你为每个核心概念准备一个“最小反例本”概念最小反例手动画为什么它反例慕课题里怎么防连通图两个孤立点A、B任意两点间无路径题干若说“图由两部分组成”立刻警觉欧拉回路三角形ABC3个点全连每个点度数2偶数但它是连通的 → 实际有回路等等这不算反例… 正确反例两个分离的三角形 → 不连通度数全偶却无欧拉回路看到“度数全偶”马上补问“图连通吗”哈密顿回路星形图中心A连B,C,D删除A后B,C,D互不连通3分支 S每天花5分钟画一个新反例写清“它为什么能推翻某个错误直觉”。一个月后你面对任何题第一反应不再是“套公式”而是“这个结构我见过它的反例吗”6.3 第三步把答案资源当“解题地图”而不是“答案书”这份MOOC答案最大的价值不是告诉你第3题选C而是暴露慕课出题人的思维断点。比如你发现第2讲所有“补图”题选项里总有一个陷阱把有向图的补图当成无向图算。这意味着出题人认定“学生容易混淆有向/无向的补图定义”。所以我的用法是做完一讲习题后不急着对答案先整理自己错的题按错误类型分类【概念混淆】/【计算失误】/【漏看条件】再打开这份答案重点看“它在哪一题标注了‘注意此处有向’‘提示补图仅对简单图’”把这些提示抄到你的错题本对应位置。久而久之你的错题本会变成一张“高频雷区地图”上面标记着这里容易忘连通性这里常错有向图度数这里总漏看“简单图”前提……从那以后我每次打开慕课视频都会先暂停拿出这张地图快速扫一遍本讲可能踩的坑再继续听课。不是为了不犯错而是让错误发生得更早、更轻——在理解阶段暴露漏洞总好过在考试时才发觉。希望帮到你。本文还有配套的精品资源点击获取