图论入门：从微信好友到地铁线路的关系建模-开发者社区

简介：本资源是哈尔滨工业大学《集合论与图论（下）》慕课MOOC课程的配套习题答案整理，面向计算机、数学及相关专业本科生及自学者，助力系统掌握图论核心概念与解题思路。内容覆盖图的基本类型（简单图、有向/无向/加权图）、树与连通性、邻接矩阵与邻接表表示法、补图与偶图、欧拉图与哈密顿图判定、图着色、平面图、割点桥及最短路径算法等关键章节，紧扣第1–4讲知识脉络，特别标注题型重复规律与选项辨析要点，提升应试效率与理解深度。资源为单个PDF文件，大小3.16MB，排版清晰、重点突出，便于离线查阅与笔记批注。已有361人学习下载，适合作为MOOC学习的同步巩固材料、期末复习提纲或图论入门者的结构化参考笔记。

1. 图论到底是什么？——别被“顶点”“边”吓住，它其实就是你每天都在用的“关系地图”

你有没有想过，微信好友列表里谁和谁互相关注、地铁线路图上哪几站能直达、甚至外卖小哥怎么规划送餐顺序——这些看起来八竿子打不着的事，背后都藏着同一套数学语言？这套语言就叫图论。它不研究几何图形，也不算三角函数，而是专门琢磨“谁连着谁”“怎么连最省事”“断掉哪根线整个网络就瘫了”这类问题。这里的“图”，不是照片或图表，而是一张由点（顶点）和线（边）构成的抽象关系网：点代表人、车站、网页、设备；线代表关注、轨道、超链接、数据连接。你刷短视频时平台推荐下一个视频，靠的也是图论算法在用户-视频这张大图里找“最近的邻居”。《哈工大集合论与图论（下）慕课MOOC答案》这份资源，不是让你背公式，而是带你用哈工大这门课的真实习题当“练习册”，从“看懂一道选择题”开始，亲手拆解连通性、欧拉路径、哈密顿回路这些听起来玄乎的概念。它适合零基础但想搞懂算法底层逻辑的编程新手、备考计算机专业课的学生、或者单纯被“为什么导航总能绕开堵点”勾起好奇心的普通人——只要你愿意把“图”当成一张可触摸、可画、可试错的关系草稿纸，这就不是数学课，是思维工具课。

2. 为什么先啃“图的基本概念”？——因为90%的翻车，都栽在没分清“有向”和“无向”上

很多新手一上来就想跑通Dijkstra最短路径代码，结果调试两小时发现邻接矩阵填反了方向，最后发现连“有向图的边带箭头，意味着A→B不等于B→A”这种基本设定都没真正内化。哈工大这门课把“图的基本概念”放在第一讲，不是凑课时，而是给你配了一副防雾眼镜：看清结构，才能不踩坑。我们不用先背定义，直接用生活场景对齐——比如你整理微信好友关系：如果只记“我和小王是好友”，这就是无向图（边没方向，A-B = B-A）；但如果记录“我关注了小王，但小王没回关”，这就成了有向图（边有箭头，A→B ≠ B→A）。再比如给每条地铁线标上票价，这条边就带了权重，变成加权图。这些不是术语游戏，而是你后续所有分析的前提。下面我们就用课程里最常考的“简单图”概念，手把手走一遍判断逻辑。

2.1 简单图的三重门：自环、重边、方向性

简单图是图论里最“干净”的起点，它必须同时满足三个条件：

没有自环：一个顶点不能连向自己（比如你不能给自己发好友申请）；
没有重边：任意两个顶点之间最多只有一条边（你和小王只能有一条好友关系，不能有两条）；
无向：所有边都不带方向（默认双向认可）。

提示：考试题常在这里设陷阱。比如题干说“某社交网络中用户A向用户B发送了3条消息”，这描述的是有向图（A→B），且可能含重边（3条消息=3条有向边），所以它一定不是简单图。别急着选“是”，先默念这三重门。

2.2 邻接矩阵：一张“谁和谁挨着”的速查表

邻接矩阵是把图翻译成数字表格的方法。假设你有4个微信好友：A、B、C、D，你想快速知道谁和谁互相关注，就画个4×4表格，行和列都标上ABCD。规则很简单：如果A关注了B，就在第A行第B列填1；如果没关注，填0。注意！这是有向图的填法。如果是无向图（比如好友关系），表格会关于对角线对称——因为A-B存在，B-A也必然存在。

# 假设这是4个顶点A,B,C,D构成的无向简单图，边为A-B, B-C, C-D # 邻接矩阵（Python列表表示） adj_matrix = [ [0, 1, 0, 0], # A行：A只连B [1, 0, 1, 0], # B行：B连A和C [0, 1, 0, 1], # C行：C连B和D [0, 0, 1, 0] # D行：D只连C ]

这段代码不是让你死记，而是帮你建立直觉：矩阵里每个1，就是现实中一条“连接”。数一数某一行有几个1，就是这个人的“朋友数”（度数）；整个矩阵有多少个1，除以2（因为无向图每条边被算了两次），就是总边数。现在你可以拿张纸，按课程PPT里的图，自己画一个3顶点的图，再填出它的邻接矩阵——这比背定义管用十倍。

2.3 邻接表：当好友太多时，我们只记“我关注了谁”

邻接矩阵清晰，但有个硬伤：如果微信有10亿用户，建个10亿×10亿的表格？内存直接爆掉。这时候就得换邻接表——它不存整张表，只给每个顶点建个“小本本”，上面只写“我连了谁”。还是A、B、C、D四人，如果A只关注B，B关注A和C，C关注B和D，D只关注C，邻接表长这样：

# 邻接表（字典形式，键是顶点，值是它连接的顶点列表） adj_list = { 'A': ['B'], 'B': ['A', 'C'], 'C': ['B', 'D'], 'D': ['C'] }

看到区别了吗？邻接矩阵是“全局视角”，邻接表是“个人视角”。课程里强调“稀疏图用邻接表更省空间”，意思就是：当你的关系网里大部分人都互不相关（比如1000人里平均每人只连5个），邻接表只存那5个名字，而邻接矩阵却要为其他995个空位留位置。这也是为什么实际项目（比如社交APP后端）几乎全用邻接表——它不是理论妥协，而是工程常识。

2.4 常见问题排查：为什么我的邻接矩阵和答案对不上？

新手在这一步最容易卡住，不是不会算，而是没意识到题目在“偷换概念”。以下是3个高频翻车点，按现象→原因→解决三步拆解：

现象1：我按题图画的邻接矩阵，和参考答案行列顺序不一样，全盘皆输
→ 原因：邻接矩阵的行列顺序必须和题目约定的顶点编号顺序严格一致。比如题干说“顶点按v1,v2,v3,v4排列”，你却按v4,v1,v2,v3填，哪怕数值全对，位置错了就是错。
→ 解决：动笔前，先在草稿纸上用大号字写下顶点顺序：v1 v2 v3 v4，然后矩阵第一行强制对应v1，第一列也强制对应v1。宁可多写一遍，不猜。

现象2：题目说“无向图”，我填的矩阵不对称，但检查三遍都没发现哪里漏了边
→ 原因：漏掉了“无向图的边是双向的”这一条。比如你只画了A-B边，却只在A行B列填1，忘了在B行A列也填1。
→ 解决：养成习惯——每画一条无向边，立刻在矩阵里填两个1，并用铅笔在两个位置画个小圈确认。对称性不是检查项，是操作铁律。

现象3：我用邻接表表示有向图，但答案里B的列表是['A']，我的却是['C']，完全相反
→ 原因：混淆了“谁指向谁”。邻接表中，'B': ['A']表示B→A（B指向A），不是A→B。很多同学潜意识里认为“B连A”就是B认识A，所以B的列表里该有A，却忘了箭头方向。
→ 解决：在邻接表旁手写箭头：B → A。或者记口诀：“冒号左边是起点，右边列表是终点”。起点射出的箭头，落在列表里的每一个终点上。

3. 连通图、补图、偶图：别被名字唬住，它们只是“关系网是否完整”“关系网的镜像”“关系网的奇偶计数器”

第二讲的三个概念，名字听着像密码，其实全是围绕“一张图的整体状态”在提问。连通图问的是：“这张网里，任意两个人能不能通过关系链找到对方？”补图问的是：“如果我把所有没连线的地方都连上，会得到什么新图？”偶图问的是：“这张网里，边的数量是奇数还是偶数？”——别笑，最后这个问题看似无聊，但它直接关联到图的对称性验证和某些算法的终止条件。哈工大这门课把它们放在一起讲，是因为它们共享同一个底层动作：遍历图的所有边和顶点。我们不从定义出发，而是用一个具体例子贯穿三者：假设你有5个微信群聊（顶点V1-V5），群内成员互相拉人，形成一张关系图。

3.1 连通图：一张网的“生命力检测”

连通图的核心是“任意两点间有路径”。注意，这里说的“路径”不要求直接相连，可以拐弯。比如V1认识V2，V2认识V3，那么V1和V3就算连通（路径V1-V2-V3）。判断一张图是否连通，最笨但最可靠的办法是深度优先搜索（DFS）：从任意一个顶点出发，沿着边一路走下去，把所有能走到的顶点打个标记；走完后，如果所有顶点都被标记了，就是连通图；否则，没被标记的顶点就属于另一个“孤岛”。

# 模拟一个5顶点图的邻接表（无向） graph = { 'V1': ['V2', 'V3'], 'V2': ['V1', 'V4'], 'V3': ['V1'], 'V4': ['V2', 'V5'], 'V5': ['V4'] } def is_connected(graph): if not graph: return True vertices = list(graph.keys()) visited = set() # 从第一个顶点开始DFS stack = [vertices[0]] visited.add(vertices[0]) while stack: current = stack.pop() for neighbor in graph[current]: if neighbor not in visited: visited.add(neighbor) stack.append(neighbor) # 检查是否所有顶点都被访问 return len(visited) == len(vertices) print(is_connected(graph)) # 输出 True，因为所有点都能连通

这段代码的关键不在语法，而在逻辑：stack是你的“待探索清单”，visited是你的“已到达地图”。每次从清单里取一个人（current），就看他拉了谁进群（graph[current]），把没去过的人加进清单和地图。等清单空了，地图上没画到的点，就是断开的孤岛。课程里所有连通性判断题，本质都是这个流程的手动模拟——你不需要写代码，但得在脑子里跑一遍这个“探路过程”。

3.2 补图：原图的“负片”，专治关系遗漏

补图的概念特别容易误解。它不是“把图变得更复杂”，而是“把图里所有没出现的关系，全部补上”。比如原图只有V1-V2、V2-V3两条边，5个顶点总共可能有C(5,2)=10条无向边，那么补图就要包含剩下的8条边（V1-V3,V1-V4,V1-V5,V2-V4,V2-V5,V3-V4,V3-V5,V4-V5）。补图的价值在于对比：如果原图很难分析，它的补图可能结构清晰；反之亦然。考试题常考“原图不连通，补图一定连通吗？”答案是：不一定，但对n≥2的图，原图和补图至少有一个是连通的——这个结论背后，就是补图把“缺失的连接”全暴露出来，反而更容易找到通路。

3.3 偶图：边数的奇偶性，为什么重要？

偶图的定义简单到令人怀疑：边数为偶数的图。但它的意义藏在应用里。比如你设计一个自动配对系统（类似相亲APP），要求每次匹配都消耗一对用户（即一条边），那么系统能否持续运行，就取决于当前关系网的边数是奇是偶。再比如图论证明中，“若某性质对所有偶图成立，则可通过补图转换到奇图”——因为补图的边数 = 最大可能边数 - 原图边数，而最大可能边数（完全图）是固定的，所以原图偶 ↔ 补图偶。课程里提到偶图与“对称性、平衡性有关”，指的就是这种数学上的镜像守恒。做题时，遇到偶图判断，别想太深，直接数边：题目给邻接矩阵，就数1的个数（无向图记得除以2）；给邻接表，就遍历所有列表，把长度加起来再除以2。

3.4 常见问题排查：连通性判断的3个隐形陷阱

连通图是高频考点，也是隐藏陷阱最多的概念。以下是阅卷老师最爱埋雷的3处：

现象1：题目给的图看着“散”，但我手动DFS后发现能连通，答案却说是不连通
→ 原因：你忽略了“无向图”的隐含条件。题目可能画的是有向图（带箭头），而你按无向图DFS，错误地把反向边当作了通路。例如V1→V2有边，但V2→V1没有，你却从V2往V1走，这在有向图里是非法的。
→ 解决：第一步永远先看题干和图示——有没有箭头？有箭头就是有向图，DFS只能顺着箭头走；没箭头才是无向图，可以双向走。

现象2：我从V1出发DFS，标记了V1,V2,V3，但V4,V5没走到，我就判不连通；结果答案说“从V4出发能走到V5”，所以是连通的
→ 原因：连通图的定义是“任意两点间有路径”，不是“从某点出发能走到所有点”。对于有向图，这叫“强连通”；对于无向图，只要整个图是一个整体，从哪出发都一样。但如果你的图是有向的，且V4→V5有边，V5→V4没有，那么V4能到V5，V5到不了V4，它就不强连通。
→ 解决：无向图只需一次DFS；有向图要验证“强连通”，必须对每个顶点都DFS一次，或使用Kosaraju算法。考试题若没特别说明“强连通”，默认指无向连通。

现象3：邻接表里V1的列表是['V2','V3']，我DFS时先取V2，再取V3，路径是V1-V2-V3；但答案路径是V1-V3-V2，说我错了
→ 原因：DFS路径不唯一！只要覆盖所有顶点，顺序不同完全OK。考试只看“是否连通”，不看你走的哪条路。
→ 解决：放下对路径顺序的执念。重点检查：你标记的顶点集合，是否和答案一致？只要集合相同，过程随意。

4. 欧拉图与哈密顿图：一个问“能不能一笔画完所有边”，一个问“能不能不重复经过所有点”

第三讲和第四讲是图论的分水岭：欧拉图解决的是“边的遍历”问题，哈密顿图解决的是“点的遍历”问题。它们像一对孪生兄弟，名字相似（欧拉/哈密顿），判定条件相似（都跟顶点度数有关），但难度天差地别——欧拉图有明确充要条件，能秒答；哈密顿图是著名的NP难问题，至今没有高效通用解法。哈工大把它们紧挨着讲，正是为了让你体会：数学里有些门，推开门就有光；有些门，推一辈子都可能摸不到锁孔。我们不碰理论证明，只聚焦考试中最常考的“判断题怎么做”。

4.1 欧拉图：无向图的“一笔画”判定口诀

欧拉图的核心是“存在一条路径，经过每条边恰好一次”。这就是小学奥数里的“一笔画”问题。判断它，记住一个口诀：无向图是欧拉图，当且仅当所有顶点度数都是偶数；是半欧拉图（存在欧拉路径但非回路），当且仅当恰好有两个顶点度数为奇数，其余全为偶数。度数就是顶点连出的边数。比如一个三角形（3个顶点，3条边），每个顶点度数都是2（偶数），所以它是欧拉图，能从任一点出发，画完所有边回到起点。再比如一个“工”字形（横一竖一，交于中点），中间交点度数是4（偶），四个端点度数都是1（奇），有4个奇度顶点，所以既不是欧拉图，也不是半欧拉图，无法一笔画。

# 判断无向图是否为欧拉图（所有顶点度数为偶数） def is_eulerian_undirected(graph): if not graph: return False # 计算每个顶点的度数（邻接表中列表长度即为度数） degrees = {v: len(neighbors) for v, neighbors in graph.items()} odd_count = sum(1 for d in degrees.values() if d % 2 == 1) return odd_count == 0 # 示例：三角形图 V1-V2, V2-V3, V3-V1 triangle = {'V1': ['V2', 'V3'], 'V2': ['V1', 'V3'], 'V3': ['V1', 'V2']} print(is_eulerian_undirected(triangle)) # True

这段代码的精髓在degrees = {v: len(neighbors) ...}——它把“数边”这个动作自动化了。你不需要真去画图，只要看邻接表里每个顶点的列表有多长，就知道它的度数。考试时，拿到邻接矩阵，就数每行1的个数；拿到邻接表，就看每个列表的长度。然后心算奇偶，3秒出结果。

4.2 哈密顿图：没有万能钥匙，但有“排除法”救命

哈密顿图要求“存在一条路径，经过每个顶点恰好一次”。这就像旅行商问题：走遍所有城市，不重复，不遗漏。它没有像欧拉图那样简洁的充要条件，但有若干必要条件可用来快速排除。哈工大课程强调的“NP难”，意思是：随着顶点数增加，穷举所有路径的计算量会爆炸式增长（n!级），所以考试题绝不会让你真的找路径，而是考“哪个图一定不是哈密顿图”。

最常用排除法：割点（Cut Vertex）
如果删除某个顶点（及其所有边）后，图的连通分量数量增加，这个顶点就是割点。含有割点的图，一定不是哈密顿图。为什么？因为哈密顿回路必须经过每个顶点一次，如果它经过割点，就必须“进来再出去”，但割点一旦被删，图就分裂，说明它原本是多个部分的唯一连接点，回路无法绕过它完成闭环。比如一个“星形图”（中心V0连V1,V2,V3），V0就是割点，删掉它，剩下三个孤立点，连通分量从1变成3，所以它不可能有哈密顿回路。

4.3 欧拉 vs 哈密顿：一张表看清本质区别

特征	欧拉图	哈密顿图
遍历对象	所有边（每条边一次）	所有顶点（每个顶点一次）
判定难度	有明确充要条件（度数奇偶性）	NP难，无高效通用判定法
考试重点	直接判断（口诀秒杀）	排除法（找割点、奇度顶点过多）
现实类比	快递员送完所有街道（边）	旅行商走遍所有城市（顶点）

注意：别混淆“欧拉路径”和“欧拉回路”。路径可以起点≠终点（半欧拉图），回路必须起点=终点（欧拉图）。考试题若说“存在欧拉回路”，必须所有度数为偶；若说“存在欧拉路径”，允许两个奇度顶点。

4.4 常见问题排查：欧拉/哈密顿判断的3个致命误区

这两个概念是挂科重灾区，因为名字像、条件像，但逻辑南辕北辙。

现象1：我看到图里所有顶点度数都是偶数，就选“是欧拉图”，结果答案是“不是”
→ 原因：你忘了图必须是连通的！欧拉图的充要条件是“连通 + 所有顶点度数为偶数”。如果图由两个分离的三角形组成，每个三角形内部度数都是2（偶），但整体不连通，它就不是欧拉图。
→ 解决：判断欧拉图，永远两步走：① 先用DFS确认连通性；② 再检查度数奇偶。缺一不可。

现象2：题目给的是有向图，我用无向图的度数口诀去判欧拉图，结果全错
→ 原因：有向图的欧拉图条件是“每个顶点入度=出度”，且图强连通。你用无向的“度数为偶”去套，相当于用尺子量温度。
→ 解决：看到箭头，立刻切换模式。入度=指向该顶点的边数，出度=从该顶点射出的边数。邻接表中，'V2': ['V1','V3']表示V2→V1、V2→V3，所以V2出度=2；要算V2入度，得遍历所有列表，看有多少次V2出现在别人列表里。

现象3：我用“割点排除法”判哈密顿图，发现没割点，就自信选“是”，结果答案是“无法确定”
→ 原因：割点是必要但不充分条件！没有割点，只说明“有可能是”，绝不保证“一定是”。比如一个5顶点的环（V1-V2-V3-V4-V5-V1），没有割点，但它确实是哈密顿图；但一个5顶点的完全图（每两点都相连），也没有割点，它也是哈密顿图。可考试题偏要出一个“没有割点但也不是哈密顿图”的反例（如彼得森图），你就只能选“无法确定”。
→ 解决：哈密顿图判断题，选项里有“无法确定”，大概率就是正确答案。别硬刚，学会放弃。

5. 从慕课习题到真实能力：为什么“抄答案”不如“抄思路”，以及第一个实战项目怎么选

看到这里，你可能已经做了几十道哈工大慕课的选择题，甚至能秒判欧拉图。但真正的分水岭不在“会不会”，而在“能不能迁移到新问题”。很多同学学完图论，面对LeetCode上一道“课程表”（判断有向图是否有环）的题，还是懵——明明课上讲过“有向无环图（DAG）”，但就是想不到用拓扑排序。问题出在哪？出在你把“答案”当成了终点，而它其实只是路标。这份《哈工大集合论与图论（下）慕课MOOC答案》最大的价值，不是让你对出选项，而是让你通过反复对照“我的思路哪步断了”，把抽象概念焊接到自己的神经回路上。下面我用自己第一次学图论的血泪经验，告诉你怎么把这份资源用透。

5.1 “抄答案”的正确姿势：三遍法，把答案变成你的脚手架

第一遍：裸做。不看答案，就当考试。哪怕完全不会，也强迫自己写点什么——画个简图、列几个顶点、猜个度数。这一步激活的是你的原始直觉，暴露的是你真正的知识盲区。
第二遍：对照答案，只看思路断点。不是核对ABCD，而是问：“我卡在了哪一步？是没看出这是有向图？还是忘了连通性要先DFS？或是把‘补图’理解成了‘子图’？”把断点写在题号旁边，比如“断点：误以为补图要保留原图边”。
第三遍：闭卷重做，强制走完断点。盖住答案，只看题干，从断点处开始推。比如断点是“忘了DFS”，那就真的在草稿纸上画栈、画visited集合，手动模拟一遍。这三遍下来，你收获的不是50道题的答案，而是50个“下次遇到类似坑，我该怎么刹车”的肌肉记忆。

5.2 第一个实战项目：用图论重构你的微信好友关系

别一上来就挑战社交网络分析，先从最小闭环开始：分析你自己的微信好友关系。步骤极简：

导出你的好友列表（微信PC版设置里可导出CSV，含昵称、备注、地区）；
用Excel筛选出同城好友（比如都标“北京”），假设有20人；
手动标注其中10对“你确认互相关注”的关系（比如你和A、B都互关，A和B也互关，就画A-B边）；
用纸笔画出这10个顶点的图，标出所有边；
用本课所学，回答：
- 这张图是连通的吗？（DFS手动走一遍）
- 它有欧拉回路吗？（数每个点的度数）
- 如果删掉你（作为中心顶点），图会分裂吗？（找割点）

这个项目不写代码，不联网，但你会第一次感受到：图论不是黑匣子，而是你手里一把能切开现实关系的刀。做完后，你再看慕课题，会发现那些V1、V2不再是符号，而是你通讯录里的真人。

5.3 下一步学什么？一张拒绝焦虑的路线图

学完哈工大这门课，你已经有了图论的“主干认知”：点、边、连通、欧拉、哈密顿。下一步不是狂啃新概念，而是让主干长出枝叶。我建议按这个顺序推进，每一步都紧扣你已有的认知：

阶段	学什么	为什么选它？	怎么验证学会了？
1	最短路径：Dijkstra算法	它是欧拉/哈密顿的“近亲”——同样是遍历，但目标是找最优而非全覆盖；代码结构和DFS一脉相承。	给你一张地铁图（5个站，带票价），手算从A到E的最便宜路线。
2	图的着色：四色定理入门	它把“顶点”和“约束”联系起来，和你判断“哪些好友能分到同一组聚会”完全同构。	用4种颜色给中国地图省份填色，确保相邻省不同色。
3	树：最小生成树（Kruskal）	树是图的特例，而Kruskal算法本质是“贪心版的连通性检测”，你会惊呼“这不就是补图思想的变体？”	给你6个村庄和它们间的修路成本，画出最省钱的联通方案。