简介：本资源是哈尔滨工业大学《集合论与图论（下）》慕课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(data=True)))

运行后你会看到：

• 无向图的边是{('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. 我的顶点到底代表什么实体？（是人？是设备？是状态？）
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和Y（V = X ∪ Y, X ∩ Y = ∅），使得G中的每一条边，其两个端点必然一个在X中，一个在Y中。换句话说，所有边都“跨组”，组内绝不相连。

最经典的例子就是“求职匹配”：左边X是所有求职者，右边Y是所有职位，边表示“某人申请了某职位”。显然，求职者之间不会互相申请，职位之间也不会互相申请——所有关系都严格发生在“人”和“岗”这两个阵营之间。

另一个例子是“电影-演员”关系图：X是电影，Y是演员，边表示“某演员出演了某电影”。同样，电影不会出演电影，演员也不会出演演员。

偶图之所以重要，是因为它天然适配大量现实场景，并且拥有一些极其高效的算法。比如：

• 判断一张图是不是偶图，可以用“染色法”：尝试用两种颜色给所有顶点上色，要求相邻顶点颜色不同。如果成功，就是偶图；如果中途发现矛盾（相邻点被迫同色），就不是。这个算法时间复杂度很低，O(V+E)。
• 在偶图上求“最大匹配”（比如让最多数量的求职者找到工作），有著名的匈牙利算法，比在普通图上求匹配高效得多。

哈工大课程在第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个关键点

初学者在学完欧拉图和哈密顿图后，最容易在以下三点上栽跟头。这些不是小疏忽，而是认知框架的错位，必须掰开揉碎讲清楚：

这三张表，不是让你死记硬背，而是帮你建立一个清晰的“决策树”：遇到一个“走遍”问题，第一步，先大声问自己——“我要走遍的是边，还是点？” 答案一出，整个解题方向就定了。慕课答案集里那些看似相似的选项，往往就在这个岔路口设置了陷阱。

5. 什么时候该用图论建模，什么时候该果断放弃？

5.1 用图论的黄金信号：当你发现“关系”比“实体”更重要

图论不是万金油。强行把所有问题都套进“点和线”的框架，只会让模型臃肿、解释无力、计算爆炸。那么，什么情况下，图论是那个“对的工具”？

核心信号只有一个：问题的本质瓶颈，在于“连接关系”的结构、强度、方向或演化，而不是实体本身的属性。

我们来看三个真实场景的对比：

从这三个例子能提炼出一个极简的自查清单。当你面对一个新问题，花30秒问自己：

1. 我最头疼的，是不知道这个东西“长什么样”，还是不知道它“连着谁”？
   → 如果是前者（如“这个零件的公差是多少？”），图论帮不上忙；如果是后者（如“这个服务器宕机，会影响哪些下游服务？”），图论就是救星。

2. 如果我把所有“关系”都抹掉，只留下一堆孤立的实体，这个问题还有意义吗？
   → 如果答案是“没了”（如社交推荐、网络故障传播），那图论就是必选项；如果答案是“还有”（如单个商品的销量预测），那图论可能是画蛇添足。

3. 这个问题的答案，会不会随着“连接方式”的微小改变而剧烈波动？
   → 如果会（如“删掉一个关键中间人，整个合作链就断了”），说明关系结构是敏感变量，图论的连通性、中心性分析就至关重要；如果不会（如“换一家供应商，成本变化不大”），那可能更适合用统计或运筹模型。

哈工大这门课的答案集，其真正价值，不在于让你抄到正确答案，而在于它用几十道精心设计的题目，反复锤炼你对这个自查清单的肌肉记忆。每一道关于“这个图是否连通？”“这条边在补图里是否存在？”“这个路径是欧拉还是哈密顿？”的题目，都在无声地训练你：在拿到任何数据之前，先用图论的透镜，扫描一遍问题的骨骼。

5.2 别用图论的红色警报：当“点”和“线”只是你的幻觉

与黄金信号相对，也有一些情况，表面上看很像图，但强行建模会南辕北辙。识别这些“伪图场景”，是避免踩坑的关键。

警报1：顶点定义模糊，边界漂移。
比如，有人想用图论分析“企业创新生态”，把“企业”当顶点，“专利合作”当边。乍看合理。但问题来了：“初创公司”和“百年老店”在创新中扮演的角色、资源、风险，天差地别。把它们强行放在同一个顶点集合里，就像把蚂蚁和大象关在一个笼子里研究“动物行为”——分类失当，模型必崩。此时，应该先按规模、阶段、领域做分层建模，而不是硬塞进一张大图。

警报2：边的含义杂糅，无法量化。
比如，“用户满意度”分析，有人把“用户”当顶点，“投诉”当边。但“投诉”这个关系，可能源于产品质量、客服态度、物流延误、甚至天气影响……原因五花八门，无法统一赋予权重或方向。这种边，不是清晰的“关系”，而是混乱的“结果”。此时，应该回归因果分析或文本挖掘，而不是在一张语义模糊的图上徒劳计算。

警报3：动态性极强，静态图无法捕捉。
比如，实时股票交易网络。顶点（股票）和边（资金流向）每毫秒都在剧烈变化，旧的连接瞬间失效，新的连接疯狂涌现。用一张静态图去建模，就像用一张去年的地图导航今天的交通——刻舟求剑。这类问题，需要动态图神经网络（DyGNN）或流式图算法，而慕课的基础内容，恰恰是为你打下理解这些高级工具的基石。

从那以后，我每次接到一个新需求，不管客户描述得多天花乱坠，我都会先拿出一张白纸，强迫自己只写两行：

• 第一行：这里的“点”到底是谁？（必须具体、可枚举、无歧义）
• 第二行：这里的“线”到底是什么？（必须可定义、可验证、最好能量化）

如果这两行写不出来，或者写出来后自己都摇头，我就知道，该停下来，重新和客户聊需求了，而不是急着打开IDE写代码。图论不是魔法，它是一面诚实的镜子，照出问题最本真的结构。用对了，事半功倍；用错了，缘木求鱼。

希望帮到你。

本文还有配套的精品资源，点击获取