★ FEATURED ARTICLE 简介本资源是哈尔滨工业大学《集合论与图论下》慕课MOOC课程的配套习题答案整理面向计算机、数学及相关专业本科生及自学者助力系统掌握图论核心理论与解题方法。内容覆盖图的基本类型简单图、有向/无向/加权图、树与连通性、邻接矩阵与邻接表表示法、补图与偶图、欧拉图与哈密顿图判定、图着色、平面图、割点桥及最短路径算法等关键模块紧扣第1–4讲知识脉络特别标注高频重复题型与选项辨析要点。资源为单个PDF文件体积3.16MB排版清晰、便于打印与离线查阅适合作为课后巩固、考前复习与自学核验的权威参考。已有361人学习下载答案虽非万能覆盖但结构完整、逻辑严谨辅以实用提示显著提升学习效率与解题准确率。1. 图论到底是什么一个快递员、一张地铁图和朋友圈关系网就能讲明白的数学语言你有没有想过为什么手机地图能秒算出“从家到公司最快要多久”而不用把全城每条小路都试一遍为什么社交软件总能精准推荐“可能认识的人”好像它偷偷翻过你的通讯录又或者为什么物流系统能用最少的货车跑遍所有小区却不会漏掉一单快递这些看似风马牛不相及的问题背后共享着同一套底层“思维语法”——图论。打个比方图论就像给世界装上了一副“关系透视镜”。它不关心一栋楼有多高、一条路有多宽、两个人长什么样它只盯着“谁连着谁”这个最朴素的事实。把城市路口看作点顶点把道路看作线边整张交通网就变成了一张抽象的“图”把微信好友看作点把“互为好友”看作边你的社交圈就成了一张“关系图”把快递站点看作点把运输线路看作边整个物流网络也是一张“调度图”。图论干的事就是研究这张“点线关系图”里藏着什么规律、能推演出什么结论、怎样才能让这张图跑得更稳、更快、更省。这门学问听起来像纯数学但它的根早已扎进我们每天刷的App、用的导航、点的外卖里。哈工大这门《集合论与图论下慕课MOOC答案》不是教你怎么解一道冷僻的数学题而是带你亲手拆开这些日常技术的“黑匣子”看清那些被封装好的智能背后最原始、最有力的逻辑骨架。它不考你背公式而是训练你一眼识别“这个问题本质上是不是一张图”以及“这张图里真正关键的连接关系在哪里”。搞懂它你就拿到了一把理解数字世界底层结构的通用钥匙——不是为了当数学家而是为了不被算法牵着鼻子走。2. 图的基本概念从“点和线”开始重新定义你眼中的世界2.1 什么是图不是画出来的图而是关系的快照在图论里“图”Graph这个词和你平时说的“统计图表”“流程图”完全不是一回事。它没有坐标轴不标数据也不讲步骤。它就是一个极简的数学对象由两样东西组成——顶点Vertex也叫节点和边Edge也叫连线。顶点代表你要研究的“实体”。它可以是人、城市、网页、服务器、化学原子……只要是你想关注的“东西”就可以把它抽象成一个点。边代表两个顶点之间的“关系”。这种关系可以是“有路可通”“互为好友”“存在引用”“发生反应”……只要你想表达“这两样东西之间有某种联系”就可以画一条线把它们连起来。提示图论里的“图”是纯粹的抽象模型它不关心顶点在纸上画在哪、边是直是弯、图看起来美不美。它只关心“哪些点连了哪些点”。就像一张地铁线路图站名位置可以随意调整只要换乘关系不变它就还是同一张图。举个生活例子假设你整理自己的微信好友列表想看看“谁和谁共同好友最多”。你不需要知道每个人的职业、年龄、发朋友圈频率——你只需要一张表列出所有好友顶点再在每对有共同好友的人之间画一条线边。这张纸上的所有点和线就是你私人社交网络的一张“图”。它不漂亮但足够锋利能直接切中问题核心。2.2 四种基础图型方向、数量、权重决定一张图能说什么话不是所有“点线关系”都一样。图论根据边的性质把图分成了几类每一种都对应着现实世界里一类典型问题。搞不清它们的区别就像用菜刀去修手表——工具不对事倍功半。无向图Undirected Graph边没有箭头表示关系是双向的、对称的。比如“朋友关系”A是B的朋友B自然也是A的朋友“道路连通”A城到B城有路B城到A城当然也有。它的边就像一根没方向的绳子两端拉哪边都一样。有向图Directed Graph简称Digraph边带箭头表示关系是单向的、有来有往的。比如“关注关系”A关注了B不代表B也关注A“网页链接”页面X上有指向页面Y的超链接但Y未必链回X。它的边像一条单行道方向错了路就走不通。简单图Simple Graph这是最“干净”的图。它满足两个条件① 任意两个顶点之间最多只有一条边不能重复连线② 不允许自己连自己没有“自环”。就像你加微信好友不能给同一个人发两次好友申请也不能自己加自己为好友。加权图Weighted Graph边不仅存在还带着一个“数值标签”叫权重Weight。这个数可以代表距离、时间、费用、信任度、流量大小……比如地图App里的路线图每条边的权重是“开车耗时”电商推荐系统里用户A对商品B的评分就是他们之间那条边的权重。权重让图从“有没有关系”升级到“关系有多强/多贵/多快”。下面这段 Python 代码用networkx库创建了三种不同类型的图直观展示区别import networkx as nx import matplotlib.pyplot as plt # 创建一个无向简单图 G_undir nx.Graph() G_undir.add_edges_from([(A, B), (B, C), (C, A)]) # 三角形无方向 # 创建一个有向图 G_dir nx.DiGraph() G_dir.add_edges_from([(A, B), (B, C), (C, A)]) # 箭头形成环 # 创建一个加权图无向 G_weighted nx.Graph() G_weighted.add_weighted_edges_from([(A, B, 5), (B, C, 3), (C, A, 8)]) # 数字是权重 print(无向图边, list(G_undir.edges())) print(有向图边, list(G_dir.edges())) print(加权图边含权重, list(G_weighted.edges(dataTrue)))运行后你会看到无向图的边是{(A, B), (B, C), (C, A)}顺序无关有向图的边是{(A, B), (B, C), (C, A)}但(A,B)和(B,A)是两条不同的边加权图的边是[(A, B, {weight: 5}), (B, C, {weight: 3}), (C, A, {weight: 8})]每条边都绑着一个数字。理解这四种图型等于拿到了四把不同形状的钥匙。面对一个新问题先问自己“这里的关系是双向的还是单向的会不会出现重复连接或自指关系本身有没有强弱/成本之分”——答案会直接告诉你该选哪把钥匙开门。2.3 为什么必须学这些“废话”图论不是炫技是给复杂世界做减法初学者常觉得“不就是点和线吗有什么好学的我早就会画了。” 这种想法很危险因为它混淆了“会画”和“会建模”。你当然会画点和线但你能保证画出来的那张图恰好只保留了问题最关键的连接信息同时把所有干扰项都剔除干净吗举个反例某高校开发了一个“校园失物招领平台”。工程师拿到需求第一反应是画一张校园平面图把所有教学楼、宿舍、食堂、小卖部都标出来再用线连起“常去地点”。结果呢系统上线后匹配效率奇低。为什么因为他画的是一张“地理图”而不是一张“行为关系图”。真正该连的不是“图书馆离打印店近”而是“经常在图书馆丢东西的人也常去打印店取资料”。前者包含太多冗余地理细节后者才直击“人-物-地点”的行为关联本质。图论的价值正在于提供一套强制性的抽象纪律。它逼你回答三个灵魂拷问我的顶点到底代表什么实体是人是设备是状态我的边到底代表什么关系是物理连接是逻辑依赖是数据流向这种关系需要方向性或数值标签吗是单向通知还是双向同步是固定路径还是有成本差异每一次回答都是一次对问题的“降噪”和“提纯”。哈工大这门课的答案集表面看是习题解析内核其实是带你反复操练这套建模肌肉从第1讲的“基本概念”开始就让你在选项里反复辨析“这个描述对应的是无向图还是有向图”“这条边能不能反向”“这个权重值在这里合理吗”。这不是抠字眼而是在训练一种工程师的核心本能——在混沌信息流中一眼锚定那个不可替代的“关系骨架”。3. 连通性与特殊图结构一张图的“生命力”藏在它的连通方式里3.1 连通图为什么有些网络一断就瘫有些却越断越强想象两座城市之间有三条独立的高速公路。如果其中一条因暴雨塌方另外两条还能保证车流通行——这个交通网是“健壮”的。但如果这三条路其实都挤在同一个隧道里隧道一塌三路全断——这个网就是“脆弱”的。图论里衡量一张图“断不断得了”的核心指标就叫连通性Connectivity而最基础的形态就是连通图Connected Graph。定义很简单一张无向图如果其中任意两个顶点之间都至少存在一条由边组成的路径那么它就是连通图。换句话说你从任何一个点出发总能“走”到其他任何一个点哪怕要绕远路、转几次弯。注意这个定义只针对无向图。有向图的连通性更复杂分为“弱连通”忽略方向后连通、“单向连通”任两点间至少有一个方向可达、“强连通”任两点间两个方向都可达。慕课第2讲重点讲的是无向图的连通性这是理解后续所有高级概念的地基。连通性不是非黑即白的“是/否”判断而是一个光谱。一张图可以“勉强连通”只有一条命脉也可以“超级连通”多条并行路径。图论用两个关键概念来刻画这种韧性割点Cut Vertex / Articulation Point删掉它整张图就分裂成多个不连通的部分。它就像网络里的“单点故障”——比如一个数据中心的主交换机一旦宕机整个部门业务中断。桥Bridge删掉它整张图就分裂。它就像一条独木桥桥断了两岸就隔绝了。在通信网中一条跨洋光缆常常就是关键的“桥”。哈工大课程在第2讲引入补图、偶图之前先夯实连通图的概念正是因为它太基础、太致命。很多算法失败不是因为逻辑错而是建模时忽略了“这张图是否真的连通”。比如你写了一个“找最短路径”的程序输入的却是一张不连通的图——程序可能永远找不到A到B的路径但它不会报错只会沉默地返回“无穷大”。这种“静默失败”比报错更难调试。3.2 补图原图的“镜像世界”专治关系分析的思维盲区如果说原图描述的是“哪些关系存在”那么补图Complement Graph描述的就是“哪些关系不存在”。它是图论里一个极其巧妙的“逆向思维工具”。定义对于一个有n个顶点的简单图G它的补图Ḡ是指这样一张图它拥有和G完全相同的顶点集但任意两个顶点之间有边当且仅当它们在G中没有边。简单说补图把原图的“邻接矩阵”里所有0变成1所有1变成0对角线保持0因为简单图不允许自环。举个例子一个班级有5个学生顶点V1-V5原图G表示“谁和谁同桌过”。如果G里只有(V1,V2)和(V3,V4)两条边说明只有这两对人同桌过。那么它的补图Ḡ里就有所有其他可能的边(V1,V3)、(V1,V4)、(V1,V5)、(V2,V3)、(V2,V4)、(V2,V5)、(V3,V5)、(V4,V5)——也就是“从未同桌过”的所有组合。为什么需要补图因为它能帮你发现原图里“看不见的模式”。比如在社交网络分析中原图显示“谁关注了谁”补图就显示“谁没关注谁”。研究补图的结构比如补图是不是连通的有没有大团簇有时比研究原图更能揭示群体的隔离、小圈子的排他性甚至预测未来的关系断裂。慕课第2讲把补图和连通图放在一起讲是有深意的它在暗示你分析一个系统不能只盯着“发生了什么”更要思考“没发生什么”。这种双重视角是高级建模者和初级使用者的根本分水岭。3.3 偶图当所有关系都必须“配对”时图就有了性别偶图Bipartite Graph也叫二分图是图论里最具“设计感”的一种结构。它的名字就暴露了核心特征“偶”意味着“成双成对”“图”意味着“关系网络”。定义一张无向图G是偶图当且仅当它的顶点集V可以被划分为两个互不相交的子集X和YV X ∪ Y, X ∩ Y ∅使得G中的每一条边其两个端点必然一个在X中一个在Y中。换句话说所有边都“跨组”组内绝不相连。最经典的例子就是“求职匹配”左边X是所有求职者右边Y是所有职位边表示“某人申请了某职位”。显然求职者之间不会互相申请职位之间也不会互相申请——所有关系都严格发生在“人”和“岗”这两个阵营之间。另一个例子是“电影-演员”关系图X是电影Y是演员边表示“某演员出演了某电影”。同样电影不会出演电影演员也不会出演演员。偶图之所以重要是因为它天然适配大量现实场景并且拥有一些极其高效的算法。比如判断一张图是不是偶图可以用“染色法”尝试用两种颜色给所有顶点上色要求相邻顶点颜色不同。如果成功就是偶图如果中途发现矛盾相邻点被迫同色就不是。这个算法时间复杂度很低O(VE)。在偶图上求“最大匹配”比如让最多数量的求职者找到工作有著名的匈牙利算法比在普通图上求匹配高效得多。哈工大课程在第2讲就把偶图和连通图、补图并列说明它不是一个孤立知识点而是构建复杂模型的“乐高基础件”。当你看到一个系统里天然存在两类角色、且关系只发生在两类之间时立刻想到“偶图”就能跳过大量试错直奔最优解法。4. 欧拉图与哈密顿图两种“走遍全图”的终极挑战难度天差地别4.1 欧拉图邮递员的完美闭环边的旅行设想一位社区邮递员他的任务是骑车走遍辖区内每一条街道边至少一次最后回到起点。怎样规划路线才能让总路程最短这就是著名的“中国邮路问题”而它的数学原型就是欧拉图Eulerian Graph。核心问题是否存在一条路径经过图中每一条边恰好一次如果存在这样的路径叫欧拉路径Eulerian Path如果这条路径还能回到起点就叫欧拉回路Eulerian Circuit一张图如果包含欧拉回路它就是欧拉图。欧拉图的判定条件堪称图论里最优雅的定理之一无向图是欧拉图的充要条件所有顶点的度数连接的边数都是偶数。无向图有欧拉路径但非回路的充要条件恰好有两个顶点的度数是奇数其余全是偶数。这两个奇度顶点就是路径的起点和终点为什么因为每次你“经过”一个顶点都要消耗两条边一进一出。只有起点多出一条出边和终点多出一条入边可以是奇数度。而欧拉回路要求起点终点所以所有点都必须是“进出平衡”的偶数度。这个定理的威力在于它把一个看似要穷举所有路径的难题变成了一个只需数数的简单操作。你甚至不用画图只要列出每个顶点连了几条边加加减减就能100%确定这条路存不存在。提示慕课第3讲的题目很多就是在考察你能否快速识别“这个图的度数序列是否全为偶数”。这是典型的“送分题”但前提是你得真懂“度数”和“边”的关系而不是死记硬背。4.2 哈密顿图旅行商的噩梦顶点的巡礼现在把邮递员问题换个玩法这次他不关心街道只关心每一个小区顶点都要拜访一次而且每个小区只去一次最后回到出发点。怎样安排顺序能让总里程最短这就是鼎鼎大名的“旅行商问题TSP”它的数学模型就是哈密顿图Hamiltonian Graph。核心问题是否存在一条路径经过图中每一个顶点恰好一次这样的路径叫哈密顿路径Hamiltonian Path如果还能回到起点就叫哈密顿回路Hamiltonian Cycle包含哈密顿回路的图就是哈密顿图。乍看和欧拉图很像都是“走遍全图”。但难度是云泥之别。欧拉图判定有明确、快速的充要条件看度数算法复杂度是线性的。哈密顿图至今没有已知的多项式时间判定算法它是计算机科学里最著名的NP完全问题之一。目前最好的通用算法时间复杂度是O(n²2ⁿ)意味着顶点数从20增加到30计算量就暴涨上千倍。为什么这么难因为哈密顿问题关注的是“顶点的访问顺序”而顺序的可能性是阶乘级增长的n个点有(n-1)!/2种可能回路。你无法像数度数那样用一个局部特征如某个点连了几条边来全局判定。它更像一个“整体涌现”的性质——取决于所有点、所有边如何精密咬合。哈工大课程把欧拉图第3讲和哈密顿图第4讲紧挨着讲绝非偶然。它是在给你上一堂深刻的“计算复杂性启蒙课”同一个“走遍”的诉求只因关注对象边 vs 顶点不同就导致了算法难度的断崖式分化。理解这一点你就不会再天真地认为“所有图论问题都能快速解决”也会对“为什么某些优化问题如此难解”产生真正的敬畏。4.3 常见误区欧拉和哈密顿90%的新手都混淆的3个关键点初学者在学完欧拉图和哈密顿图后最容易在以下三点上栽跟头。这些不是小疏忽而是认知框架的错位必须掰开揉碎讲清楚易混点为什么混怎么区分一句话口诀目标对象混淆以为欧拉图也要“经过每个点”哈密顿图也要“经过每条边”。因为中文描述都带“走遍”“经过”容易望文生义。欧拉管“边”哈密顿管“点”。记住邮递员数的是“走了几条街”边旅行商数的是“进了几个小区”顶点。判定逻辑混淆试图用“度数”去判断哈密顿图或用“访问顺序”去判断欧拉图。两者都涉及“路径”让人误以为判定方法类似。欧拉看局部每个点的度数哈密顿看全局所有点的排列组合。欧拉条件是“体检报告”哈密顿问题是“拼图游戏”前者查单子就行后者必须动手试。存在性与构造性混淆认为“存在欧拉回路”就等于“我能轻松画出来”或“哈密顿图很难判定”就等于“一定找不到路径”。把数学存在性和算法可行性混为一谈。存在性 ≠ 可构造性。欧拉定理只保证“路存在”不保证你一眼看出怎么走哈密顿虽难判定但对特定结构如完全图、偶图仍有高效启发式算法。别被“NP难”吓住先看图的结构特点这三张表不是让你死记硬背而是帮你建立一个清晰的“决策树”遇到一个“走遍”问题第一步先大声问自己——“我要走遍的是边还是点” 答案一出整个解题方向就定了。慕课答案集里那些看似相似的选项往往就在这个岔路口设置了陷阱。5. 什么时候该用图论建模什么时候该果断放弃5.1 用图论的黄金信号当你发现“关系”比“实体”更重要图论不是万金油。强行把所有问题都套进“点和线”的框架只会让模型臃肿、解释无力、计算爆炸。那么什么情况下图论是那个“对的工具”核心信号只有一个问题的本质瓶颈在于“连接关系”的结构、强度、方向或演化而不是实体本身的属性。我们来看三个真实场景的对比场景实体属性是否关键关系结构是否关键是否适合图论原因预测房价用房屋面积、房龄、楼层、学区等特征预测价格。✅ 极其关键。面积差10㎡价格可能差几十万。❌ 关系次要。隔壁房子的价格对本房影响有限除非是豪宅集群。❌ 不适合。这是典型的回归问题核心是实体特征与目标值的映射用线性模型、树模型更直接。推荐好友给用户A推荐可能认识的人。❌ 用户A的年龄、职业是辅助信息。✅ 极其关键。“共同好友数”“互动频率”“群组重叠度”这些关系指标才是推荐质量的决定性因素。✅ 高度适合。这是标准的关系挖掘。把用户当顶点互动当边用图算法如Adamic-Adar指数计算“潜在连接强度”效果远超单纯看个人资料。芯片布线在硅片上规划晶体管之间的金属连线避免短路、减少延迟。❌ 晶体管类型、尺寸是固定参数。✅ 决定性关键。哪两个晶体管必须连连线长度、交叉次数、并行度直接决定芯片性能和良率。✅ 必须用图论。这是经典的图划分与布局问题。把晶体管当顶点必须连接的需求当边用最小割、谱聚类等图算法优化是工业界标准流程。从这三个例子能提炼出一个极简的自查清单。当你面对一个新问题花30秒问自己我最头疼的是不知道这个东西“长什么样”还是不知道它“连着谁”→ 如果是前者如“这个零件的公差是多少”图论帮不上忙如果是后者如“这个服务器宕机会影响哪些下游服务”图论就是救星。如果我把所有“关系”都抹掉只留下一堆孤立的实体这个问题还有意义吗→ 如果答案是“没了”如社交推荐、网络故障传播那图论就是必选项如果答案是“还有”如单个商品的销量预测那图论可能是画蛇添足。这个问题的答案会不会随着“连接方式”的微小改变而剧烈波动→ 如果会如“删掉一个关键中间人整个合作链就断了”说明关系结构是敏感变量图论的连通性、中心性分析就至关重要如果不会如“换一家供应商成本变化不大”那可能更适合用统计或运筹模型。哈工大这门课的答案集其真正价值不在于让你抄到正确答案而在于它用几十道精心设计的题目反复锤炼你对这个自查清单的肌肉记忆。每一道关于“这个图是否连通”“这条边在补图里是否存在”“这个路径是欧拉还是哈密顿”的题目都在无声地训练你在拿到任何数据之前先用图论的透镜扫描一遍问题的骨骼。5.2 别用图论的红色警报当“点”和“线”只是你的幻觉与黄金信号相对也有一些情况表面上看很像图但强行建模会南辕北辙。识别这些“伪图场景”是避免踩坑的关键。警报1顶点定义模糊边界漂移。比如有人想用图论分析“企业创新生态”把“企业”当顶点“专利合作”当边。乍看合理。但问题来了“初创公司”和“百年老店”在创新中扮演的角色、资源、风险天差地别。把它们强行放在同一个顶点集合里就像把蚂蚁和大象关在一个笼子里研究“动物行为”——分类失当模型必崩。此时应该先按规模、阶段、领域做分层建模而不是硬塞进一张大图。警报2边的含义杂糅无法量化。比如“用户满意度”分析有人把“用户”当顶点“投诉”当边。但“投诉”这个关系可能源于产品质量、客服态度、物流延误、甚至天气影响……原因五花八门无法统一赋予权重或方向。这种边不是清晰的“关系”而是混乱的“结果”。此时应该回归因果分析或文本挖掘而不是在一张语义模糊的图上徒劳计算。警报3动态性极强静态图无法捕捉。比如实时股票交易网络。顶点股票和边资金流向每毫秒都在剧烈变化旧的连接瞬间失效新的连接疯狂涌现。用一张静态图去建模就像用一张去年的地图导航今天的交通——刻舟求剑。这类问题需要动态图神经网络DyGNN或流式图算法而慕课的基础内容恰恰是为你打下理解这些高级工具的基石。从那以后我每次接到一个新需求不管客户描述得多天花乱坠我都会先拿出一张白纸强迫自己只写两行第一行这里的“点”到底是谁必须具体、可枚举、无歧义第二行这里的“线”到底是什么必须可定义、可验证、最好能量化如果这两行写不出来或者写出来后自己都摇头我就知道该停下来重新和客户聊需求了而不是急着打开IDE写代码。图论不是魔法它是一面诚实的镜子照出问题最本真的结构。用对了事半功倍用错了缘木求鱼。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
