企业官网建设流程全解析

离散数学的“图论”章节，很多人第一反应是“一堆点和线有什么好学的”。但说实话，这章恰恰是整个离散数学里最贴近真实世界、也最容易跟实际工作产生交集的部分——你现在用的社交网络好友推荐、地图导航的最短路线、电商系统的“猜你喜欢”，底层跑的都是图算法。甚至这些年大火的图神经网络、图计算，根基就是这一章的“邻接矩阵”“遍历”“最短路径”这些概念。

这篇博文就当是陪你过一遍第8章图的完整内容，从基本定义、存储表示，到欧拉图、哈密顿图、树、最短路径，再到期末高频题型，全部按我复习时的思路串一遍。不管你是在校学生准备期末考，还是工作后想补离散数学的底子，这篇都能给你一个能直接“抄作业”的复习框架。

1. 图的整体认知：先搞懂它到底在研究什么问题

1.1 图的定义：不止是“点和线”那么简单

教材上对图的定义往往写得比较严谨，但理解起来容易绕。我用大白话翻译一下：图就是由顶点集合和边集合构成的二元组，记作 G = (V, E)。V 是顶点集合，E 是边的集合。每一条边都连接两个顶点，表示这两个顶点之间存在某种关系。

我本科第一次学的时候，总觉得这定义太朴素了——两个集合而已，能有啥深度？后来才发现，真正要理解的是“关系”这个词。图和普通集合的最大区别，就是它显式地建模了元素之间的关联。比如你把全班同学当顶点，如果两个人认识就画一条边，那你得到的就是一张人际关系图；你把网页当顶点，如果页面 A 有超链接指向页面 B 就画一条有向边，那得到的就是万维网的简化模型。

有些教材会强调“图可以用图形表示”，但我建议你反过来理解：图形只是图的可视化手段，本质还是集合论里的结构。这也就解释了为什么第8章会放在学完集合、关系、函数之后——图就是关系的一种更直观、更结构化的表达。

1.2 图的基本术语：不背熟这些，后面全崩

离散数学考试有个特点，名词解释和判断改错题特别喜欢抠基本术语。第二章的基础概念你如果模糊，后面学欧拉图、哈密顿图、树的时候，做题速度会直接慢一半。

我自己复习时整理了一张速查表，建议你也自己动手做一遍：

• 简单图：无多重边、无自环的图。考试里绝大多数题目写的“图”默认都是简单图。
• 多重图：允许两个顶点之间存在多条边。现实中比如两座城市之间的多条航线。
• 有向图 vs 无向图：有向图的边有方向，无向图的边没有方向。注意有向图里“入度”和“出度”是两个独立概念。
• 顶点的度：无向图中与顶点关联的边数，记作 deg(v)。有向图里分为入度 deg⁺(v) 和出度 deg⁻(v)。
• 握手定理：所有顶点的度数之和等于边数的两倍，即 Σdeg(v) = 2|E|。这是图论里第一个重量级定理，证明思路就是每条边贡献两个“端点度数”。
• 路径与回路：路径是顶点序列，相邻顶点之间有边连接；回路是起点和终点相同的路径，且路径长度至少为1。
• 连通：无向图中任意两个顶点之间都有路径，则称图连通。有向图的连通性更复杂，分成弱连通、强连通，这个后面细说。

我踩过的坑是混淆“路径”和“迹”。路径要求顶点不重复（因此边也不重复），迹只要求边不重复。考试特别喜欢在这两个概念上挖坑，题目问“是否存在一条经过所有边恰好一次的路径”，说的其实是欧拉迹，不是普通路径。

1.3 图论到底有什么用：从社交网络到芯片设计

如果你觉得“图论离我很远”，那下面这几个例子应该能扭转你的印象：

• 社交网络分析：把每个用户当成顶点，关注关系当成有向边，好友关系当成无向边，你就能用图的连通性算法找出“社交圈”，用中心性算法找出“关键人物”。
• 地图导航：道路交叉口是顶点，道路段是带权边（权值可以是距离、时间），Dijkstra 算法就是导航软件显示“最快路线”的核心。
• 芯片布局与电路设计：芯片里的逻辑门是顶点，连线是边，平面图相关的理论直接决定了电路板能否单层布线。
• 推荐系统：用户和商品作为顶点，购买行为作为二分图中的边，基于图的协同过滤就是这么做的。

学科是抽象的，但应用是具体的。带着“这个东西能做什么”的疑问去学第8章，你会觉得每个公式和定理都有落地的影子。

2. 图的表示与存储：当数学概念遇上代码实现

2.1 邻接矩阵：直观但未必高效

邻接矩阵是表示图最直接的方式。假设图有 n 个顶点，就建一个 n×n 的矩阵 M。M[i][j] = 1 表示顶点 i 到顶点 j 之间有边；如果是带权图，就把 1 替换成权值；如果无边，可以用 0 或者无穷大表示。

邻接矩阵最大的优点是判断两点之间是否有边的时间复杂度是 O(1)，这在稠密图（边很多）场景下非常好用。但缺点也明显：空间复杂度是 O(n²)，如果图有 1 万个顶点，光矩阵就需要 1 亿个存储单元。所以稀疏图（边很少）用邻接矩阵就很浪费。

考试里还有一种“关联矩阵”，行对应顶点、列对应边，M[i][j] = 1 表示顶点 i 与边 j 关联。这个在教材里出现频率不高，但偶尔会在填空题、简答题里冒出来，我个人觉得了解概念、能看懂即可，不需要花太多精力。

2.2 邻接表：工程里更常用的方案

邻接表的核心思想是：只存储实际存在的边。做法是为每个顶点维护一个链表，链表里存的是“与该顶点相邻的所有顶点”。这样空间复杂度降为 O(|V| + |E|)，在稀疏图场景下优势巨大。我们常见的图算法（DFS、BFS、Dijkstra）在工程实现里基本都是用邻接表，而不是邻接矩阵。

下面是我复习时用 Python 写的一个非常简化的版本，用来加深对两种表示方式差异的理解：

# 用 Python 字典模拟邻接表 # 顶点：0, 1, 2, 3 # 边：(0,1), (0,2), (1,2), (2,3) graph = { 0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2] }

这段代码几乎就是邻接表的“活教材”。每个字典的 key 是顶点，value 是邻居列表。做深度优先搜索的时候，你遍历 graph[v] 就是在遍历 v 的所有邻接点。

当时的考试里常出这样一道题：“给定某个图的邻接矩阵，写出对应的邻接表。”反过来也考。这种题没有技巧，就是练习手速和细心，多画几遍就有感觉了。

2.3 图的同构：看着像才是真的像

图同构是第8章里比较抽象的概念，也是期末考里容易出判断、选择的点。简单来说，两个图 G1 和 G2 如果存在一个顶点之间的双射函数 f，使得“u 和 v 在 G1 里有边”当且仅当“f(u) 和 f(v) 在 G2 里有边”，就说这两个图同构。

用人话说，两个图只是顶点名字不同，但“连接结构”完全一样，就是同构。

要证明两个图同构，核心是找一个合适的顶点对应关系。要证明两个图不同构，则要找一些“同构不变量”——如顶点度数序列、边数、连通分量个数、回路长度分布等。如果两个图这些性质不一样，那肯定不同构；如果都一样，也不一定同构，但至少更可疑。这块考试的套路非常固定，反复做几道课后题就熟练了。

3. 图的遍历与连通性：考试核心中的核心

3.1 DFS 和 BFS：两种“走迷宫”的思路

图的遍历是第8章的重头戏，期末必考。考试形式通常有两种：给出图让你写出 DFS 或 BFS 的顶点访问序列；或者让你判断两个序列分别是哪种遍历的结果。

DFS（深度优先搜索）的核心思想是“一条路走到黑，撞了南墙再回头”。实现可以是递归，也可以是显式的栈。实际写代码时递归更直观：

def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start, end=' ') for neighbor in graph[start]: if neighbor not in visited: dfs(graph, neighbor, visited) return visited

BFS（广度优先搜索）的核心思想是“一圈一圈往外扩”，用队列实现。你从起点出发，先把起点的所有邻居访问完，再去访问这些邻居的邻居：

from collections import deque def bfs(graph, start): visited = set([start]) queue = deque([start]) while queue: v = queue.popleft() print(v, end=' ') for neighbor in graph[v]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)

考试中画序列的时候，注意事项是：如果题目中的图没有指定邻接点的访问顺序，默认按顶点编号从小到大访问。这个约定教材和真题里一般都有，不特别注意的话，DFS 序列容易因为访问顺序不同被扣分。

3.2 连通性：一个图是不是“整块”的

无向图的连通性判断比较直接：从任意顶点做一次 BFS/DFS，如果能访问到所有顶点，说明图连通；否则说明图不连通，被分成了若干个连通分量。

如果考试出“求下图的连通分量”，你只需要把每个连通块标出来就行。但如果是带答题过程的大题，建议你用 DFS 对每个未访问顶点启动一次遍历，记录每次遍历访问到的顶点集合，这几个集合就是连通分量。

有向图的连通性就复杂一些：

• 强连通：任意两个顶点 u、v 之间，既有 u 到 v 的路径，也有 v 到 u 的路径。
• 弱连通：把有向边当作无向边处理之后，整个底图是连通的。

判断有向图是否强连通，最简单的办法是对每个顶点作为起点都做一次 BFS/DFS，看看能否到达所有顶点。如果顶点数很多，工程上会用 Kosaraju 算法或 Tarjan 算法，但离散数学的期末考一般不会让你实现这些，知道概念即可。

我做题时最容易漏的是单点强连通的判断——单个顶点视作强连通的，但这个结论在考试场景里一般不影响答案。

3.3 割点、桥与二连通：进阶但常考

割点（articulation point）是指：如果删除这个顶点，图的连通分量数量会变多。桥（bridge）类似，只是删除的是边。

考试里最常考的是“给出一个图，找出所有割点和桥”。直接暴力做法：对每个顶点尝试删掉之后做 DFS，看连通分量数量是否变化。顶点数少的时候，这个方法完全够用，而且思路清晰，不容易错。

再进阶一点是二连通图：没有割点的连通图就是二连通图（也称作块连通图）。这个概念和图的双连通分量相关，期末考一般只要求判断一个图是否二连通，不太会考双连通分量的分解算法。

4. 欧拉图与哈密顿图：两个经典“路径难题”

4.1 欧拉图：从“七桥问题”到一笔画

柯尼斯堡七桥问题可以说是图论的“开山之题”——这个城市有七座桥连接四块陆地，市民想知道能否从某块陆地出发，每座桥恰好走一次，最后回到起点。欧拉的结论是：不可能。理由就是四块陆地的度数分别是奇数、奇数、偶数、偶数，不符合“每个顶点的度数必须是偶数”的条件。

于是就有了欧拉图的核心判定定理：

• 无向图存在欧拉回路（回到起点，且每条边恰走一次）：图连通，且所有顶点度数为偶数。
• 无向图存在欧拉通路（不要求回到起点，但每条边恰走一次）：图连通，且恰好有两个顶点度数为奇数（这两个顶点是通路的起点和终点）。
• 有向图存在欧拉回路：图连通，且每个顶点入度等于出度。

考试里的题目大多是“判断下图是否存在欧拉回路/欧拉通路”。你只需要三步：

1. 判断图是否连通；
2. 数每个顶点的度数或出度入度；
3. 套上述定理。

我自己第一次做题时漏了“连通”这个前提，因为一个不连通的图即使所有点度数都为偶数，也无法一条路径遍历完所有边。这个点反复出现，一定要记得先检查连通性。

4.2 哈密顿图：比欧拉图难的不是一点半点

哈密顿图研究的是“经过每个顶点恰好一次的回路”，叫哈密顿回路。它不像欧拉图那样有充要条件，而只有一些必要条件和充分条件。这也导致哈密顿图的判定本质上是个 NP 完全问题，跟欧拉图不在一个难度层级上。

考试中常用的判定定理：

• 必要条件：如果图 G 存在哈密顿回路，则删去 k 个顶点后，剩余的连通分量数不超过 k。这是最常用的判定“不是哈密顿图”的工具。
• Dirac 定理（充分条件）：如果 G 是 n 个顶点的简单图，n≥3，且每个顶点的度数都至少是 n/2，则 G 必有哈密顿回路。
• Ore 定理（充分条件）：如果 G 中任意两个不相邻顶点 u、v 都有 deg(u) + deg(v) ≥ n，则 G 必有哈密顿回路。

初学的时候特别容易把欧拉图和哈密顿图搞混。区分诀窍：欧拉图管的是“边”，哈密顿图管的是“顶点”。欧拉图关心能不能每条边走一次，哈密顿图关心能不能每个点走一次。

4.3 实际应用中的图模型问题

图论在工业界的应用，很多时候就是在欧拉图和哈密顿图这两种模型上做变体。

比如快递员送信问题（中国邮递员问题）本质上就是找欧拉回路的最小权重版本：街道是边，路口是顶点，要求每条街道至少走一次且总路程最短。如果图本身是欧拉图，那直接走欧拉回路即可；如果不是，就要给某些边加“复制边”，把图补成欧拉图。

旅行商问题则是典型的哈密顿回路优化问题：每个城市只能访问一次，最后回到起点，求最短环路。这类问题求解难度极大，工程上一般用近似算法或启发式算法（如模拟退火、遗传算法）来逼近最优解。

把教材里的定理和现实问题做映射，复习起来会明显更有方向感。

5. 树与生成树：图论里最“实用”的子类

5.1 树的等价定义：不画图也能搞懂

树就是连通且无回路的无向图。教材上往往会给出一堆等价定义，考试常考“互推”：

• G 连通且无回路；
• G 连通且边数 = 顶点数 - 1；
• G 中任意两个顶点之间有唯一路径；
• G 无回路，但加入任意一条新边会产生唯一回路；
• G 连通，但删去任意一条边会变得不连通。

核心是掌握 n 个顶点的树，边数一定是 n-1。很多大题都会用到“连通图边数至少是 n-1”这个结论来证明或推断。

5.2 最小生成树：Kruskal 和 Prim 的相爱相杀

最小生成树问题是考试大题的高频考点。它的背景是：在带权图中找一棵包含所有顶点的树，使得树中所有边的权重之和最小。最常用的两种算法是 Kruskal 和 Prim。

Kruskal 算法：把边按权值从小到大排序，每次选出不会形成回路的边加入集合，直到所有顶点连通。判断是否会形成回路，可以用并查集（一种高效处理集合合并与查询的数据结构）来实现。

Prim 算法：从任意一个顶点开始，每次从当前树到未加入树顶点之间的边中，选一条权值最小的边，把对应顶点加入树中，重复直到所有顶点加入。

下面我用 Python 快速演示一下 Kruskal 的逻辑（核心部分）：

def kruskal(n, edges): # edges: list of (u, v, weight) edges.sort(key=lambda x: x[2]) parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(a, b): ra, rb = find(a), find(b) if ra != rb: parent[ra] = rb return True return False mst = [] total = 0 for u, v, w in edges: if union(u, v): mst.append((u, v, w)) total += w return mst, total

考试作答题里，不要求写代码，但要求逐步列出选择边、判断回路、确定加入的过程，并写出最终最小生成树的权和。这种题得分点在于过程清晰，每一步的“判断是否成环”理由要写清楚，别跳步。

Prim 和 Kruskal 的选择：稀疏图用 Kruskal 通常更快，稠密图用 Prim 更合适。考试一般不会考到复杂度层面的复杂度优化，但了解这一点能帮助你在实际项目里做选型。

5.3 最短路径：Dijkstra 与 Floyd

最短路径问题是图论中考试频率最高的应用型题目。Dijkstra 算法适用于边权非负的单个源点最短路径问题，是导航系统的核心基础算法。

Dijkstra 的执行过程要重点掌握：

1. 维护一个数组 dist，dist[v] 表示源点到 v 的当前最短距离；
2. 每次从未确定最短路的顶点中，选一个 dist 最小的顶点 u；
3. 用 u 去更新它的所有邻接点的 dist；
4. 标记 u 为“已确定”，重复上述过程。

做考试题时，建议画一张表，每一轮记录哪些顶点已确定以及更新后的 dist 数组，最后写出从源点到各目标顶点的最短路径及距离。步骤清晰是拿满分的诀窍。

如果要求所有顶点对之间的最短路径，且图的边权可能为负，那么可以用 Floyd 算法。它用三重循环动态更新：

for k in range(n): for i in range(n): for j in range(n): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Floyd 的“中间点中转”思想，面试里也经常考，理解它的本质是动态规划。

6. 平面图与图着色：把“画得出来”变成数学定理

6.1 平面图的判定和欧拉公式

平面图就是能把所有边画在平面上、且边与边只在顶点处相交的图。期末考一般不会让你用 Kuratowski 定理去判定，更常见的题型是：给出一个图，问它是不是平面图，并用到欧拉公式解题。

欧拉公式是最常用的工具：对于一个连通的平面图，有 V - E + F = 2，其中 F 是面数（包括外部无限面）。

这个公式的推导思路非常经典：从只有一个顶点的图开始，不断加边。每加一条边，如果引入了一个新顶点，F 不变；如果没有引入新顶点，F 加 1。无论哪种情况，V - E + F 的值都保持不变。

做题时需要区分“面”的定义，尤其是外部面千万别漏。我见过很多同学在计算面数时把外部面漏了，导致欧拉公式两边对不上。复习时多画几个图，把内部面、外部面都标出来，形成肌肉记忆。

6.2 四色定理与图着色：从地图到调度

图着色问题是平面图理论最出名的应用。四色定理说任何平面图都能用不超过四种颜色对顶点着色，使得相邻顶点颜色不同。这个定理曾被计算机辅助证明，也是图论历史上一个极富争议和戏剧性的问题。

考试里一般不会让你证明四色定理，更多是给出一个小图，让你尝试用最少的颜色给顶点着色。步骤通常是：

1. 找度数最大的顶点，先给它着色；
2. 沿着它的邻接点逐步扩展；
3. 每次选一个“与已经着色邻接点颜色都不同”的最小可用颜色。

本质上是贪心算法，不保证给出全局最优色数，但对简单图来说足够应付考试了。

图着色的现实应用场景包括考试安排（不能在同一时间考试的学生分到不同时间）、地图制图（相邻区域不同颜色）、无线频谱分配（相邻基站不同频段）等。明白了这些应用，上考场遇到图着色题时就不会觉得它是一个孤立的知识点。

7. 期末复习与考试的实战经验

7.1 高频考点和题型汇总

我复习了往年期末真题之后，发现第8章的考试重点非常集中。按出现频率排序：

根据这个频率表安排复习精力，Dijkstra、最小生成树、欧拉图/哈密顿图判定、DFS/BFS 遍历，这四块是绝对不能失分的项目。

7.2 常见错误与避坑清单

错误一：忽略握手定理的“每条边贡献2度”

度数之和和边数的关系是个多选题常客。大意是“一个图有 6 条边，所有顶点度数之和是多少？”正确答案是 12，不是 6。这个错误常见到让我怀疑人生的程度——考试时间紧，一紧张就容易想成“度数之和等于边数”。

错误二：判断欧拉图只查度数、不查连通性

如前所述，一个不连通的图，即使每个顶点度数都是偶数，也不存在欧拉回路。每次判断欧拉图，先问自己“这个图连通吗”。

错误三：Dijkstra 过程表画乱了

Dijkstra 大题丢分一般不丢在结论，而丢在过程不清晰。建议每次都用规范的表头：| 已确定顶点集 | dist[各顶点] | 更新说明 |。按轮次写清楚哪些顶点被确定，哪些距离被更新，一步都不要省。

错误四：把欧拉路径和哈密顿路径搞混

考试题目如果写“经过每条边恰一次”就是欧拉路径，“经过每个顶点恰一次”就是哈密顿路径。题干里这两个词换一下，答案可能完全不一样。

错误五：平面图的面数数漏外部面

欧拉公式 V - E + F = 2，F 包含外部无限面。练习题里大多数图都会有一个“外部大区域”，这个区域如果忘了算，公式立刻对不上。

7.3 我的复习节奏与资料建议

我个人复习第8章的顺序，供你参考：

1. 先通读一遍教材，把定义和定理过一遍，建立整体框架；
2. 对照往年真题，把每道题考的考点标注在教材对应章节旁边；
3. 针对高频考点做专项练习，每类题做3-4道，做完对答案并分析错因；
4. 把做错的题整理成一张纠错表，考前最后一天只看错题；
5. 考前动手画一遍重点图（比如自创一个6个顶点的图，手动做一遍 DFS/BFS、Kruskal、Dijkstra），保持手感。

教材方面，手边常备一本屈婉玲老师的《离散数学》或者 Rosen 的《离散数学及其应用》，两者对图论章节的覆盖都足够应付国内高校的期末考试。Rosen 的优点是例子丰富，入门轻松；屈婉玲的优点是和国内考点匹配度高。我个人的阅读顺序是先用 Rosen 建立理解，再用屈婉玲的课后题做巩固。

写在最后的小建议

第8章图的内容量在整本离散数学教材里算是中等偏多，但好在它极度结构化——只要把“表示方法、遍历方式、两类特殊图（欧拉/哈密顿）、树、最短路径、平面图”这几个模块串联起来，整章的知识框架就立住了。我当年复习的时候，把每一类题目的解法步骤单独抄在一张 A4 纸上，考试前只看这些纸上写的步骤，基本就能应对大部分题目。

最后分享一个我到现在还在用的技巧：学图论的时候，每学一个新概念，就强行想一个现实场景。比如学到“桥”，就去搜“社交网络中存在的桥”；学到“最小生成树”，就想想“公司布线时怎么省钱”。这听起来有点费时间，但一旦建立了现实映射，你以后碰上相关算法，回忆速度和理解深度会远超死记硬背的同学。

图论不是离散数学里最难的一章，但绝对是最能拉开分数差距的一章。花一周时间把这里吃透，期末考的这一章分数稳稳拿下，后面学数据结构里的图算法也会轻省得多。