图论入门：从快递路线到社交网络的建模思维

简介：本资源是哈尔滨工业大学《集合论与图论（下）》慕课MOOC的配套习题答案整理，面向计算机、数学及相关专业本科生及图论自学者，助力系统掌握图论核心概念与解题思路。内容覆盖图的基本类型（简单图、有向/无向/加权图）、树与连通性、邻接矩阵与邻接表表示法、补图与偶图、欧拉图与哈密顿图判定、图着色、平面图、割点桥及最短路径算法等关键模块，紧扣课程讲授逻辑，每讲对应清晰（如第1讲图的基本概念、第2讲连通图与补图、第3讲欧拉图、第4讲哈密顿图），并附有选项辨析提示，强调易混淆点识别。资源为1个PDF文件，大小3.16MB，排版紧凑、重点突出，适合作为课后复习、作业核对与考前梳理的轻量级参考材料。目前已有361人学习下载，答案基于高频重复题型归纳整理，虽非官方发布，但结构完整、逻辑连贯，可有效提升学习效率与解题准确率。

1. 图论到底是什么：一个快递员、地铁图和朋友圈的共同语言

你有没有想过，为什么送外卖的系统能自动规划出最快路线？为什么地铁换乘图一眼就能看懂所有连接关系？为什么社交软件总能精准推荐“你可能认识的人”？这些看似不相关的事，背后都藏着同一套思维工具——图论。它不研究具体的数字或公式，而是专注一件事：点和点之间怎么连、连得稳不稳、能不能走通、走通要花多少代价。这里的“点”可以是城市、人、服务器、网页，而“边”就是它们之间的公路、好友关系、网络连接或超链接。

哈工大这门《集合论与图论（下）》慕课，不是让你背定义，而是带你用图论这把“万能尺子”，去量一量现实世界里那些复杂关系的骨架。比如，“连通图”问的是：如果某个城市停电了，整个电网会不会瘫痪？“欧拉图”对应的是：扫地机器人能不能不重复清扫任何一条走廊，最后回到起点？“哈密顿图”则像极了旅行商的终极纠结：跑遍所有客户只去一次，哪条路最省油？这些题目在慕课里反复出现，并非为了刁难，而是因为——真实世界的优化问题，90%都能翻译成图的语言。如果你曾被“度数”“补图”“偶图”这些词绕晕，别急，它们不是数学黑话，只是给日常逻辑换了一身工装。接下来，我们就一层层剥开这层外壳。

2. 图的基本概念：从一张白纸到能说话的结构

2.1 顶点和边：图的“细胞”与“神经”

图论里最基础的两个元素，叫顶点（Vertex）和边（Edge）。你可以把顶点想象成微信里的一个个头像，边就是头像之间那根“添加好友”的连线。但注意：这条线本身没有方向——A加了B，B也默认成了A的好友，这就是无向图。可如果换成“公众号推文→读者阅读”这个关系，箭头就很重要了：推文能发给读者，但读者不能反向给公众号发推文。这种带箭头的图，就叫有向图。

提示：慕课题里常考一个细节——“朋友关系”默认是无向的（互为好友），但“关注关系”是有向的（你关他，他未必关你）。选错选项，往往就栽在这一个箭头上。

2.2 简单图、多重图、自环：哪些连接是“合法”的？

不是所有连线都算数。图论先立下几条“交通规则”：

• 简单图：任意两个顶点之间，最多只允许一条边；而且不允许自己连自己（即不能有“自环”）。就像现实中两个人只能加一次好友，不能给自己发好友申请。
• 多重图：允许多条边连接同一对顶点。比如北京到上海，既有高铁、也有航班、还有货运专线——它们都是“北京↔上海”这条关系的不同实现方式。
• 自环：顶点连向自己。这在某些场景合理，比如“某用户点赞自己的动态”，但在大多数基础图论题中，题目默认排除自环，除非特别说明。

2.3 加权图：给关系标上“价格标签”

现实中的连接都有成本：

• 北京→上海高铁票价553元，飞行时间2小时；
• 北京→上海货车运费8000元，耗时3天；
• 你给同事发消息，延迟50毫秒，流量消耗2KB。

把这些“代价”写在边上，这张图就升级成了加权图。权重可以是数字、时间、概率、甚至负数（比如优惠券抵扣）。慕课第1讲的习题里，经常出现“求两点间最短路径”，这个“短”指的就是权重之和最小，而不是边数最少——这点初学者极易混淆。

2.4 邻接矩阵 vs 邻接表：图的两种“身份证”

怎么把一张图存进电脑？两种主流方式：

邻接矩阵，像一张全班同学的座位表：行是起点，列是终点，格子里填1表示有边，0表示没边。

# 4个顶点的无向图：A-B, B-C, C-D adj_matrix = [ [0, 1, 0, 0], # A连B [1, 0, 1, 0], # B连A和C [0, 1, 0, 1], # C连B和D [0, 0, 1, 0] # D连C ]

优点：查任意两点是否相连，O(1)搞定（直接看矩阵对应位置）；缺点：太费空间——1000个顶点就要100万格子，哪怕只有10条边。

邻接表，像每个人的通讯录：只记“我连了谁”。

# 同样的图，用字典表示 adj_list = { 'A': ['B'], 'B': ['A', 'C'], 'C': ['B', 'D'], 'D': ['C'] }

优点：省空间，稀疏图（边很少）时效率碾压矩阵；缺点：查A和D是否直连，得翻遍A的列表找D，最坏O(n)。

慕课习题虽不考代码，但理解这两种表示，能帮你秒懂“为什么这道题说‘邻接矩阵中第i行和为偶数’就代表顶点i度数是偶数”。

3. 连通性与特殊图类：一张网的“健康体检报告”

3.1 连通图：整张网是不是“活”的？

想象一张全国物流网络图：顶点是仓库，边是运输线路。如果从哈尔滨仓库出发，能通过若干次转运，把货送到三亚仓库，那这两个点就是连通的。如果图中任意两个顶点都连通，这张图就叫连通图。

但现实很骨感：台风可能冲垮某座桥，黑客可能攻陷某个服务器节点。这时，图会裂成几块互不通信的“孤岛”。每一块内部连通、块间断开的部分，就叫一个连通分支。慕课第2讲的题常问：“删掉顶点v后，图分裂成几个连通分支？”——这其实在模拟：如果某个核心路由器宕机，整个网络会碎成几片？

3.2 补图：原图的“镜像世界”

补图是个很玄的概念。给你一张图G，它的补图Ḡ，就是把G里所有没连的边全连上，所有已连的边全拆掉后得到的新图。

打个比方：G是你班级的“已组队名单”（A和B一起做过实验，就连边）；那么Ḡ就是“从未合作过名单”——A和C没合作过，就在Ḡ里连上；A和B合作过，Ḡ里就坚决不连。

为什么学这个？因为很多性质是“互补”的。比如：G是完全图（所有点两两相连） ↔ Ḡ是空图（所有点孤立）；G有割点（删掉它图就散架） ↔ Ḡ可能更健壮。慕课题喜欢考：“若G连通，Ḡ一定连通吗？”答案是否定的——反例：G是星形图（一个中心连所有外围点），Ḡ就很可能不连通。

3.3 偶图（二分图）：能“分组站队”的图

偶图又叫二分图，核心特征：所有顶点能分成两组（比如男生/女生、任务/工人、网页/关键词），且所有边都只跨组连接，组内绝不相连。

经典例子：

• 求职网站：左边是求职者，右边是职位，边表示“该人投递了该职位”；没人会投递自己，所以组内无边。
• 国际象棋棋盘：黑格和白格天然二分，马走日只能从黑跳到白，或白跳到黑。

判断一个图是不是偶图？有个血泪经验：看它有没有奇数长度的环。三角形（3环）、五边形（5环）……只要存在任一奇环，它就不是偶图。慕课题常给一个环状图，问“能否二着色”，本质就是在考这个。

3.4 树：最精简的连通图

树是图论里最优雅的结构之一：无环 + 连通。就像一棵真树——没有回路（不会绕圈长枝），但所有枝杈又都连在主干上。

关键性质：n个顶点的树，恰好有n−1条边。多一条就成环，少一条就不连通。这个数字关系，是慕课计算题的黄金线索。例如题干说“某图有10个顶点、9条边、且连通”，那你立刻能断定：它是一棵树——不用再验证有没有环。

树的变体也很实用：

• 生成树：从一张连通图里，砍掉一些边，留下一棵包含所有顶点的树。就像给城市电网做冗余备份——保留最低限度线路，确保不断电。
• 最小生成树（MST）：在加权图中，找一棵总权重最小的生成树。修高速公路网时，这就是“花最少钱连通所有城市”的方案。

4. 欧拉图与哈密顿图：两种“走遍天下”的通关条件

4.1 欧拉图：一笔画完所有边

传说哥尼斯堡有七座桥，居民想试试：能否从某地出发，走过每座桥恰好一次，最后回到起点？欧拉证明了不可能——并由此开创图论。

• 欧拉路径：经过图中每条边一次的路径（起点≠终点）；
• 欧拉回路：起点和终点相同的欧拉路径；
• 欧拉图：存在欧拉回路的图。

判定口诀（无向图）：
✅ 所有顶点度数都是偶数 → 是欧拉图（存在欧拉回路）；
✅ 恰好两个顶点度数为奇数 → 存在欧拉路径（但不是回路）；
❌ 超过两个奇度顶点 → 既无欧拉路径，也无欧拉回路。

注意：度数指连边数量。在有向图中，要区分入度（箭头指向它）和出度（箭头从它发出），欧拉回路要求每个顶点入度=出度。

4.2 哈密顿图：走遍所有顶点一次

和欧拉图“走遍所有边”不同，哈密顿图追求“走遍所有顶点一次”。比如旅行商问题（TSP）：拜访n个城市各一次，哪条路线总里程最短？

• 哈密顿路径：经过每个顶点恰好一次的路径；
• 哈密顿回路：起点终点重合的哈密顿路径；
• 哈密顿图：存在哈密顿回路的图。

⚠️ 关键区别：欧拉图有明确判定法则，哈密顿图没有！目前没有任何多项式时间算法能100%判断任意图是否哈密顿——它被归为NP难问题。慕课题不会让你证明一个复杂图是哈密顿图，而是考充分条件，比如：

• 若图中任意两顶点度数之和 ≥ n（顶点总数），则它是哈密顿图（Ore定理）；
• 若每个顶点度数 ≥ n/2，则它是哈密顿图（Dirac定理）。

这些定理像“保险条款”：满足就一定行；不满足，不代表不行——只是没拿到保单而已。

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

4.4 常见误区：这五个点，90%初学者都踩过坑

误区1：把“连通图”等同于“有欧拉回路”
→ 为什么混：都带“连通”俩字，容易联想。
→ 怎么区分：连通图只要求点之间有路；欧拉图还额外要求每条边都被走且只走一次。一个连通图可能有奇度顶点（比如星形图），那就不是欧拉图。

误区2：“哈密顿图一定有生成树”是对的，但反之不成立
→ 为什么混：树是连通无环图，哈密顿图也是连通的，误以为有树就有哈密顿回路。
→ 怎么区分：生成树只要求连通+无环；哈密顿回路要求走遍所有顶点一次——树可能长得歪歪扭扭，根本绕不成一个圈。反例：一条直线型的树（A-B-C-D），就没有哈密顿回路。

误区3：“补图连通，原图就一定连通”
→ 为什么混：觉得“镜像”该对称。
→ 怎么区分：原图可能是完全图（极度连通），补图却是空图（完全不连通）。反过来，原图是空图，补图是完全图——所以连通性不传递。

误区4：“偶图里不能有环”
→ 为什么混：偶图强调“分两组”，误以为环会破坏分组。
→ 怎么区分：偶图可以有环，但只能是偶数长度的环（4环、6环…）。三角形（3环）会强制三个点两两相连，无法分成两组不组内连接——所以偶图禁止奇环，不禁止所有环。

误区5：“邻接矩阵对称就一定是无向图”
→ 为什么混：无向图的邻接矩阵确实对称（A连B ⇔ B连A）。
→ 怎么区分：有向图如果恰好“双向都有边”，矩阵也对称。判断依据永远是题干描述，不是矩阵形态。慕课题常设这个陷阱：给一个对称矩阵，却说“这是有向图的邻接矩阵（AB和BA边都存在）”。

5. 图论工具箱：从理论到解题的实战心法

5.1 解题三步法：把文字题翻译成图语言

慕课题再绕，本质都是“建模→转化→套结论”。举个典型题：

“某社交平台有n个用户，任意两人之间要么互相关注，要么互相不关注。现知：对任意两个用户A、B，总存在第三个用户C，使得C同时关注A和B。问：该平台的关注关系图是否一定存在哈密顿回路？”

第一步：建模

• 顶点 = 用户；
• 有向边 A→B = A关注B；
• “互相关注”即A→B且B→A；“互相不关注”即无边。

第二步：转化
题干条件“对任意A,B，存在C使C→A且C→B”，翻译成图论术语：每个顶点对都有公共入邻居。这提示我们往“强连通”或“入度”方向想。

第三步：套结论
回忆Dirac定理：若每个顶点出度 ≥ n/2，则存在哈密顿回路。但题干没给出度数信息。再想：条件其实暗示图很“稠密”，可能满足Ore定理变体——不过慕课题一般不会考这么深，更可能是引导你发现：当n≥3时，该条件足以保证图是强连通的，进而结合其他定理判断。

提示：遇到陌生描述，先强行替换成“顶点/边/度数/连通性”等基础词，80%的迷雾就散了。

5.2 避坑检查清单：交卷前必扫的5个雷区

1. 方向雷：题干说“导师指导学生”，默认有向（导师→学生）；说“同学合作”，默认无向。箭头错，全盘皆输。
2. 计数雷：问“度数为3的顶点有几个”，注意自环算2度（起点终点都是它），普通边算1度。
3. 存在性雷：“是否存在欧拉路径” ≠ “是否存在欧拉回路”。前者允许两个奇度点，后者要求零个。
4. 补图雷：求补图的边数，别硬画——原图边数 + 补图边数 = 完全图边数 = n(n−1)/2（无向）或 n(n−1)（有向）。
5. 树雷：看到“n顶点，n−1边”，先默念三遍：“它连通吗？它无环吗？”——缺一不可。不连通就是森林，不是树。

5.3 真题还原：一道慕课高频题的完整拆解

题目（第3讲典型题）：

无向图G有8个顶点，12条边。已知G中恰有3个顶点度数为3，其余顶点度数均为x。求x的值，并判断G是否可能为欧拉图。

解法：

1. 用握手定理：所有顶点度数之和 = 2 × 边数 = 24。
2. 列方程：3个顶点度3 → 贡献9度；剩下5个顶点度x → 贡献5x度；总和：9 + 5x = 24 → x = 3。
3. 判断欧拉图：所有8个顶点度数都是3（奇数）→ 奇度顶点数=8 > 2 →不可能是欧拉图，也不可能有欧拉路径。

这个题把“握手定理”“度数计算”“欧拉图判定”全串起来了。慕课题库重复率高，吃透这一道，类似题基本秒杀。

6. 什么时候用图论？什么时候该放下笔？

6.1 该抄起图论的5个信号

当你面对的问题出现以下任一表述，立刻启动图论模式：

• “所有节点之间”“任意两点”“彼此连接” → 考察连通性、完全图、补图；
• “只经过一次”“不重复”“遍历” → 锁定欧拉路径/回路 或 哈密顿路径/回路；
• “最小代价”“最短距离”“最少资源” → 涉及加权图、最短路径、最小生成树；
• “分组”“配对”“匹配”“互斥” → 往偶图（二分图）、最大匹配、着色问题上靠；
• “关键节点”“脆弱点”“断开影响” → 分析割点、桥、连通分支数。

比如，某公司要做员工技能匹配系统：前端工程师（A类）只能对接需求文档（B类），不能直接对接数据库（C类）。这天然构成二分图（A-B边存在，A-C边不存在），后续“如何让最多工程师有活干”，就是标准的最大二分图匹配问题——匈牙利算法登场。

6.2 该放下笔的3个红灯

图论不是万能锤，乱用反而南辕北辙：

• 问题本质是数值计算：比如“求1到100的和”，用图论建模纯属炫技，徒增复杂度；
• 数据量极小且静态：只有3个点、2条边，手动画图比写算法快十倍；
• 关系无法明确定义“连接”：比如“用户心情相似度”，如果相似度是连续小数且无阈值，强行二值化（相似=1，不相似=0）会丢失关键信息，此时更适合用聚类或向量空间模型。

我带过的一个模拟项目X，团队曾试图用哈密顿回路优化快递员每日取件顺序。结果发现：实际约束远超“访问每个客户一次”——还要考虑交通管制、客户预约时段、包裹体积重量、电动车续航……最后回归混合整数规划（MIP），图论只作为初始解生成器。从那以后我每次看到“优化路径”，都强制走一遍约束清单：时间窗？载重？优先级？——图论只解决其中“连通性”和“访问顺序”部分，其余交给更专精的工具。

6.3 一份务实的学习路线图

哈工大这门慕课的答案整理，不是让你抄作业，而是帮你建立问题-模型-工具的反射弧。建议这样用：

1. 先遮住答案，读题5分钟：用纸笔把题干转译成图（标顶点、画边、写权重）；
2. 对照答案，只看“建模思路”栏：为什么这里用邻接表而非矩阵？为什么判定用Dirac而非Ore？
3. 改一个参数重做：比如把“8个顶点”改成“9个”，重新算x，验证规律是否普适；
4. 找一个现实场景自测：看到小区快递柜分布图，马上想：“这是连通图吗？有割点吗？最短取件路径是哪种算法？”

图论真正的力量，不在于解出某道题，而在于你开始习惯问：这件事，能不能画成点和线？当你看到朋友圈转发链、看到芯片布线图、看到蛋白质相互作用网络，第一反应不再是“好复杂”，而是“让我给它建个模”——那一刻，你就真正拿到了这把钥匙。

希望帮到你。

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