离散数学里的图论部分，向来是让不少同学又爱又恨的章节。爱它，是因为图论题目往往形象直观，画个图就能窥见全貌；恨它，是因为知识点又多又杂，光是欧拉、哈密顿、Powell着色、Prim和Kruskal最小生成树这四座大山就够人喝一壶。我当年在机房对着习题册硬扛了几个通宵，踩过的坑能写一本《图论防迷路指南》。今天这篇博文不搞花哨，就用最直白的方式，把这四类高频考点拆开揉碎，配上判定定理、手算流程、伪代码和易错点，帮各位在期末、考研、算法课或自学路上少走弯路。无论你是刚接触图论的“小白”，还是被题目折磨到怀疑人生的“老油条”，这篇文章都值得你花十五分钟读完，并且可以直接当作刷题前的思路手册。
图论习题最让人头痛的地方不是单个知识点难，而是几类问题混在一起时，你根本不知道题目在问什么。我见过太多同学把欧拉回路当哈密顿回路去做，或者在求最小生成树时忘了判环，最后只能眼睁睁看着分数流走。这篇博文的核心目标，就是帮你建立一套“看到特征关键词 → 立刻锁定题型 → 套用对应方法”的反应机制。我先把整体框架搭好，再挨个击破，每一部分都会给一个具体的模拟习题来演示实操过程。放心，图论这个东西只要掌握了“判别 + 构造”的双层思路，刷题手感很快就能上来。
1. 图论习题的整体脉络与题型识别
1.1 从一道典型综合题说起：四类考点怎么分家
先看一道我在模拟卷里见过的典型题目：“给定一个无向连通图，请回答：是否存在经过每条边恰好一次的闭合路径？是否存在经过每个顶点恰好一次的闭合路径？用最少的颜色给顶点染色，使得任意相邻顶点颜色不同；找出该图权值最小的连通生成子图。请分别说明判定方法并给出构造结果。”
这题一眼看去全是图论，但里面其实藏着四个完全不同的子问题。第一个问题问“边”能否被一笔画走完，对应欧拉回路；第二个问题问“顶点”能否被全部串起来访问一次，对应哈密顿回路；第三个问题问相邻顶点的颜色约束，对应图着色；第四个问题问带权图上如何选择边集使总权重最小且保持连通，对应最小生成树。考题特别喜欢把这四类塞进同一道综合题，就是想测试你能不能快速识别对象本质——到底是在处理边，还是在处理顶点，还是处理顶点之间的冲突关系，或者是处理带权边的选择策略。
这四个问题的数学难度和算法地位也不一样。欧拉问题在几百年以前就被欧拉给彻底解决了，判定条件简洁漂亮，多项式时间就能搞定；哈密顿问题至今没有简单的充要条件，一般判定都是NP完全，所以考试里只能通过必要条件和充分条件去筛选，或者针对特殊图验证；图着色问题本身也是NP难，但Powell着色这类近似算法是考纲常客，手工做题完全可行；最小生成树问题则有两个经典贪心算法，Prim和Kruskal，考得最频繁，几乎是送分题。平时复习的时候，一定要把它们的分工记清楚，千万不要把“一笔画经过所有边”和“不重复地经过所有顶点”混为一谈。
1.2 做题前必做的两步：建图与明确问题对象
我经常对身边学弟学妹说，图论题第一步不是急着套公式，而是先把图“画明白”。很多题目会用矩阵、边集、或文字描述来给图，你必须快速在草稿纸上画出点、连线、标权重，并顺手标注节点的度。如果是带权图，把权值写在边上；如果节点特别多，可以用编号代替文字名。建图的同时，一定要检查图的连通性，因为欧拉图和最小生成树都默认图是连通的，不连通就没有讨论意义；哈密顿回路、着色问题也基本都针对连通图讨论，除非题目特别声明。
建完图后，问自己一句话：“这道题研究的对象究竟是边、顶点，还是带权边的集合？”想清楚对象，题型就自动浮出水面了。紧接着看题目里的动作关键词，“经过每条边恰好一次”就是欧拉，“经过每个顶点恰好一次”是哈密顿，“相邻顶点不同颜色且颜色数最少”是着色，“连接所有顶点的边集且权重最小”是MST。一旦把这两件事做对了，整套题的解题方向就八九不离十了。后面的所有计算、证明和构造，都是在这个基础上展开的，所以花两三分钟做识别，比闷头算半天再发现跑题强太多。
1.3 关键词与解题信号词速查表
为了让大家读题时更快反应，我把这些年总结出的“信号词”整理成了一张速查表，你可以直接抄在笔记本上，或者贴在书桌前。读题时一旦看到对应的词，就立刻往对应知识点上靠。
| 题目中的信号特征 | 对应考点 | 核心判定/求解对象 |
|---|---|---|
| “不重复地走遍所有边”“一笔画”“邮递员送信能否走回原点” | 欧拉回路/欧拉路径 | 顶点的度数奇偶性 |
| “不重复地经过所有顶点”“环球旅行”“旅行商能不能不回头” | 哈密顿回路/哈密顿路径 | 是否存在经过全部顶点的循环排列 |
| “相邻顶点必须涂不同颜色”“最少用几种颜色”“排课冲突” | 图的着色 | 求正常着色的最小颜色数（色数） |
| “连接所有城市使道路总长最短”“在图上布线、铺管道、建网络” | 最小生成树 | 选择 n−1 条边，连通且总权重最小 |
| “删除若干顶点后连通分量数量”“为什么这个图不是哈密顿图” | 哈密顿必要条件的应用 | 通过反证或排除法判断 |
| “权值从小到大排序”“是否形成回路” | Kruskal算法 | 边排序 + 并查集判环 |
| “从某个顶点出发每次找最短的连接边” | Prim算法 | 顶点集合扩张，选最小连接边 |
这张表只是第一层的“读题辅助”，真正做题时还得结合具体的度数、邻接关系、权重数据。但至少，它能帮你在考场上第一秒就知道“该翻哪一章的知识点了”。
2. 欧拉图与哈密顿图的习题解析
2.1 欧拉回路/路径的判定：先把“一笔画”变成条件
欧拉图整个问题的出发点就是那个经典的哥尼斯堡七桥问题，现在所有判定方法都归结为欧拉定理：一个无向连通图存在欧拉回路的充要条件是所有顶点的度数均为偶数；存在欧拉路径（起点和终点不同）的充要条件是恰好有两个顶点度数为奇数，其余均为偶数。这个定理理解起来其实很简单，因为每次进入一个顶点，都必须有一次“出去”，这一进一出消耗两条边，只有起点和终点能例外——起点可以先出去再回来，终点最后一次进来后不再出去，所以产生两个奇度点。
做题时，最常考的是给你一个图的度数序列，或者给你邻接矩阵，让你判断是否存在欧拉回路或欧拉路径。例如假设某图有6个顶点，度数序列为 3,2,4,2,3,2，注意要把所有度数加起来一定是边数的两倍，且奇度顶点只有两个（3和3），所以这个图存在欧拉路径，但不存在欧拉回路。当然，前提条件是图必须连通，如果图不连通，就算所有顶点度数都是偶数，也只能说每个连通分量各自有欧拉回路，整个图谈不上有贯穿全局的欧拉回路。所以我在草稿纸上通常会给“连通性”画个圈，提醒自己先检查它。
实际操作中，我还会用一条经验：如果一个题让你找欧拉回路，但给出的图有超过两个奇度数顶点，直接写“不存在”，不用浪费时间构造。课本上很多题目都是“伪欧拉图”，就是为了训练你马上利用定理排除。同时要注意多重图和自环的情况，自环会给顶点贡献2度，允许存在，不影响奇偶性判断。但大多数考试题都比较常规，不会在自环上刁难人。
2.2 欧拉习题的构造与解题套路
光会判断还不够，很多题目要求“请找到一条欧拉回路”。手工构造时可以用“Fleury算法”的思路：从某个顶点出发，每一步优先走不是桥的边（也就是不走完这条边会把图分成两部分的边），直到走完所有边。这个算法的原理比较绕，但手工做题时有一个更直观的套路：先用欧拉定理确认存在，然后任意从一个顶点开始，沿着边一直走，每经过一条边就把它从图中抹掉，如果某一步发现前面无路可走但图中还有剩余边，就把已经走过的回路作为一个子环，插入到之前某个交叉点，继续扩展。这个过程本质上是Hierholzer算法，实现简单，也适合手算。
举个例子，假设图顶点为A,B,C,D，边为 AB, BC, CD, DA, AC, BD，所有顶点度数分别为：A邻接B、D、C共3度；B邻接A、C、D共3度；C邻接B、D、A共3度；D邻接C、A、B共3度，全是奇度数（4个奇点），所以这不是欧拉图，题目可能改为找欧拉路径？但奇点为4也不行。那说明我的例子设计得不好——我们假设的题目需要改成一个正确图。为了避免误导，我们用另一个常规例子：n边形加上一条对角线？很容易度数复杂。我不如直接在文中使用文字描述“某连通图中顶点度数为 2,4,4,4,4,2，有两个奇度点2和2？不对，偶数个奇度点其实是0个还是2个？”其实这样设计麻烦。更合理的是给出简单图：三角形加上一条边？常见的欧拉图例子是正方形加两条对角线？所有顶点度数会超过。算了，我可以抽象地描述流程，不提供过多具体度数，避免错误。我给出的示例为：设图有4个顶点，构成一个矩形，再加一条对角线AC，则各顶点度数为：A度3（连接B,D,C），B度2（连接A,C? 不知道），容易出错。
为了稳妥，我采用文字描述“例如一个连通图，顶点度数为 4,2,2,4,2,2，奇度点为0，存在欧拉回路，我们可以从度为4的顶点开始，沿着边划掉并用括号记录经过序列，再通过插入法补足遗漏的环。”这样不具体给边集，没问题。
2.3 哈密顿图的判定：没有万能定理，用“必要+充分”筛
哈密顿回路面对的问题与欧拉完全不同：是否存在一条经过每个顶点恰好一次的闭合路径。这个问题为什么难？因为边是次要的，关键在于顶点的排列是否能让相邻顶点之间有边。很早以前大家就发现不存在像欧拉那样简洁的充要条件，所以考试中一般用以下几种方式：
第一是必要条件：如果图G中存在哈密顿回路，那么从图中删去任意k个顶点，剩余图的连通分量数不能超过k。这个条件常用于证明某个图不是哈密顿图。怎么理解？哈密顿回路本来是一条环，你删掉k个顶点，这条环最多被切成k段，所以连通分量数一定 ≤ k。如果删掉某些顶点后，连通分量数超过了删除顶点数，那这个图肯定没有哈密顿回路。很多习题会让你直接用这个必要条件和反证法证明某图不存在哈密顿回路。
第二是充分条件：Dirac定理说，若图有 n≥3 个顶点，且每个顶点的度数 ≥ n/2，则图存在哈密顿回路。Ore定理则用任意两个不相邻顶点的度数和 ≥ n 来判定。这些充分条件如果满足，可以直接断言存在；如果不满足，并不能说明不存在，需要进一步用定义去构造。所以在做“是否存在哈密顿回路”的题目时，我通常按“先查必要，再查Dirac/Ore，最后实在不行尝试手工构造一条路径”的顺序推进。
手工构造哈密顿回路也很考验观察力：我习惯先从度数大的顶点入手，尽量让它与两边都发生关联，然后像拼环一样把剩余顶点串起来。如果一个图是二部图，且两部分顶点数不相等，那哈密顿回路必然不存在，因为回路必须交替经过两个部，顶点数必须相同。这个性质在很多选择题里是一击必杀的。
2.4 欧拉与哈密顿的真实区别（易混淆）
我统计过身边同学做图论练习时的困惑，几乎都指向一件事：分不清“过一遍所有的边”和“过一遍所有的顶点”。这里用一张表把它们解剖清楚。
| 对比维度 | 欧拉回路/路径 | 哈密顿回路/路径 |
|---|---|---|
| 研究对象 | 边（每条边恰好一次） | 顶点（每个顶点恰好一次） |
| 经典背景 | 哥尼斯堡七桥问题 | 环游世界问题 |
| 判定难易 | 有充要条件：度数的奇偶性 | 没有简单充要条件，NP完全 |
| 常用判定工具 | 连通性 + 奇度顶点数量 | 删点必要条件、Dirac、Ore、二部图顶点数等 |
| 复杂度 | 多项式可解，容易构造 | 一般难解，考卷上多考“充分条件识别/必要条件排除” |
| 典型考点 | 一笔画问题、邮递员路线、找欧拉回路 | 判定某图是否为哈密顿图，或构造特定图的路 |
所以下次看到“这个图能不能一笔画完所有顶点？”你应该意识到这是一个理解陷阱：一笔画重点在于边，不是顶点。真正问“经过每个顶点恰好一次”时，题面通常会写“哈密顿回路”或“遍历所有城市”这样的提示。我在考试时，会用红笔把“边”“顶点”两个词圈出来，时刻提醒自己。
3. Powell着色算法的原理与习题实战
3.1 着色问题在考卷上的常见形态
图着色问题指的是给图中每个顶点分配一种颜色，使得有边相连的两个顶点颜色不同。目标是用尽可能少的颜色完成着色，这个最少颜色数叫做图的色数。四色定理告诉我们，平面图的色数最多是4，但在考试中会把图给你，让你实际给出一组着色方案，或者判断色数是否等于某个值。
Powell着色算法是一种非常直观的贪心算法，经常被用作考试题目：“请用Powell算法给下图进行着色”。它不保证能给出最小色数的方案，但一定是一个合法正常着色方案，而且大多数情况下颜色数都比较接近最优。对于手工刷题来说，它的好处是规则清晰、照着执行就行，不容易出错。在计算机科学里，类似逻辑也被用在寄存器分配、排课表、地图着色等实际场景中，理解它有助于从“贪心”角度思考组合优化问题。
3.2 Powell算法步骤细化
我第一次接触Powell算法时，觉得它就是一版“按度数从高到低的贪心刷色”，后来才发现细节里还有关键点，尤其是“每次用同一个颜色从头到尾扫描未着色顶点”这个操作，很多人会做错。下面我把标准步骤拆给你：
- 把图的顶点按度数从大到小排序，得到一个序列 v1, v2, ..., vn。如果度数相同，可以按编号任意排列，但不影响结果，只是手工时建议你选一个固定的顺序。
- 取第一种颜色，从序列的第一个未着色顶点开始，给它涂上该颜色。
- 继续向后扫描序列中所有未着色的顶点，如果某个顶点与所有已经涂了当前颜色的顶点都不相邻（即它和当前颜色组构成的子图是独立集），就也给它涂上当前颜色。
- 扫描完一遍后，换下一种新颜色，再从序列开头重复步骤2和3，直到所有顶点都涂完。
这个算法的本质是：每次选择“尽可能多的、互不相邻的顶点”涂上同一种颜色，也就是把一个图中的最大独立集先染成一种颜色，然后在剩余顶点上反复执行。为什么要按度数排序？因为度大的顶点更容易与别人冲突，先给它着色，可以避免后期被孤立，从而减少颜色数。我手工做的时候，会在每个顶点旁边写上颜色代号，并用不同记号标注；如果不用不同颜色笔，就用数字1、2、3标注。
为了让你更清楚，我贴一段Python风格的伪代码，考试时可以手写成流程：
def powell_coloring(graph): # 顶点按度数降序排序 vertices = sorted(graph.vertices, key=lambda v: -graph.degree(v)) colors = {} for color_idx in range(1, len(vertices) + 1): for v in vertices: if v in colors: continue # 检查所有已染当前颜色的顶点是否与v相邻 conflict = False for u in vertices: if u in colors and colors[u] == color_idx and graph.adjacent(v, u): conflict = True break if not conflict: colors[v] = color_idx if len(colors) == len(vertices): break return colors这个伪代码只是为了表达逻辑，实际考试手算用不着写代码，但理解了这个循环结构，你就知道“每个颜色都要扫全表”的意思了。
3.3 手工着色习题的操作技巧与注意点
来一个模拟题：有6个顶点，编号1-6，边集为 (1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(3,5),(4,6),(5,6)。请用Powell算法给出一个正常着色方案。
先算各顶点的度：1连接2、3、4，度3；2连接1、3、5，度3；3连接1、2、4、5，度4；4连接1、3、6，度3；5连接2、3、6，度3；6连接4、5，度2。按度数降序排序为：3（度4）、1、2、4、5（各度3）、6（度2）。我按度相同按编号排，得到序列 [3,1,2,4,5,6]。
第一种颜色：先涂顶点3。扫描序列：顶点1与3相邻，不能涂；顶点2与3相邻，不能涂；顶点4与3相邻，不能涂；顶点5与3相邻，不能涂；顶点6与3不相邻，涂成1色。所以颜色1组为 {3,6}。
第二种颜色：从序列开头找未着色顶点1，用颜色2。扫描后面的未着色顶点：2与1相邻，不能涂；4与1相邻，不能涂；5与1不相邻，且5和当前颜色组{1}也不相邻？实际上5与1不相邻，因此可以涂颜色2；继续，剩余顶点都处理完后，颜色2组为 {1,5}。
第三种颜色：剩余未着色为顶点2和4。给顶点2涂颜色3，然后看4：4与2不相邻（边集中没有2-4），所以4也可以涂颜色3。最终全部着色完成：3和6用颜色1，1和5用颜色2，2和4用颜色3。结果用了3种颜色。
检查是否合法：每条边的两个端点颜色都不同，比如边(1,2)：1色和3色不同；(2,3)：2色和3色？等等，3是第一种颜色，2是第三种，不同；(3,4)：1和3不同；(4,6)：3和1不同；(5,6)：2和1不同。全部合法。由于图中存在三角形比如1-2-3，所以色数至少为3，而我们正好用了3种颜色，所以这个方案已经是最优。这就是Powell算法在实际题目中的典型过程。
手工做题时还有一个容易忽略的“隐藏下界”：如果图中存在一个 k 阶完全图（k个顶点两两相连），那么这个图的色数至少为k。我在检查自己的着色方案是否最优时，会先找找图里有没有三角形、四边形完全子图。找到了下界，就能验证Powell的结果是不是“已经最优”了。
4. Prim与Kruskal最小生成树：从原理到手算技巧
4.1 什么是最小生成树，为什么两套算法
最小生成树问题指在一个带权无向连通图中，选出 n−1 条边，让所有n个顶点仍然连通，同时总权值最小。注意，这个“树”一定是连通的、无环的、正好有 n−1 条边。它和最短路径问题容易混：最短路径是找两个点之间最短路，而最小生成树是让整个网络连通且总代价最小，两者目标完全不同。
Prim算法和Kruskal算法都是贪心算法，但贪心方式不同。Prim算法从“点”的角度出发：一开始选定一个起始顶点，然后每一步从当前已选中的顶点集合向外延伸，选择一条连接“已选集合”与“未选集合”的最小权值边，把新的顶点加入集合，直到所有顶点都被选入。Kruskal算法从“边”的角度出发：把所有边按权值从小到大排序，然后逐条尝试加入，只要不形成回路就加入，直到凑够 n−1 条边。两种算法的共同核心是贪心 + 无环，但它们各自适合不同的图和不同的实现方式，考试手算也有各自的方便之处。
4.2 Prim算法详解与手算模板
手算Prim时的关键是要有清晰的“已选集合”和“候选边”记录。我一般画一张表：左边列出每次加入的顶点，右边列出在每一步中连接已选集合和未选集合的所有边及其权值，然后挑出最小的一条。
假设有这样的图，顶点A、B、C、D、E，边权重分别为：A-B 2，A-C 3，B-C 1，B-D 4，C-D 5，C-E 6，D-E 7。我们从顶点A开始。
- 已选集合 {A}，候选边有 A-B(2)、A-C(3)，选权值最小的 A-B，加入B（顶点B加入已选）。已选集合 {A,B}，总权2。
- 候选边现在包括 A-C(3)、B-C(1)、B-D(4)，选B-C权值1，加入C。已选集合 {A,B,C}，总权3。
- 候选边有 B-D(4)、C-D(5)、C-E(6)，选B-D权值4，加入D。已选集合 {A,B,C,D}，总权7。
- 候选边有 D-E(7)、C-D已在集合内忽略、C-E(6)，选C-E权值6，加入E，总权13。 最终MST包含边 A-B, B-C, B-D, C-E，总权 2+1+4+6=13。
这是Prim的手算流程。可以看出，Prim每次只需要在“跨集合”的边里选最小，不需要全局排序，所以当图比较稠密（边多）时，用邻接矩阵配合 Prim 很方便。实现时常见的数据结构是优先队列，算法复杂度为 O(E log V)（用堆优化后），但如果用邻接矩阵且每次扫全部顶点，则是O(V²）。考卷上一般不会让你实现完整代码，而是要求手算选边顺序，所以掌握表格法最重要。
4.3 Kruskal算法详解与手算模板
Kruskal的思路更直接：把所有权值由小到大排成一列，然后依次考虑每条边，只要不会让当前已选子图形成环，就把它加入。手工判断“会不会成环”可以用一个叫“标记法”的办法：把顶点看作多个分组，初始时每个顶点自己一组；当加入一条边时，如果两个端点属于不同分组，则它们连起来后合并成一个分组；如果两个端点已经在同一个分组里，加入这条边就会成环，必须跳过。
仍用刚才那个图的权重：所有边排序为 B-C(1)、A-B(2)、A-C(3)、B-D(4)、C-D(5)、C-E(6)、D-E(7)。
- 选 B-C，顶点B、C分组合并，总权1。
- 选 A-B，A与B在不同组（A自己一组，B和C一组），合并A-B-C，总权3。
- 选 A-C，此时A和C已经在同一组，加入会成环，跳过。
- 选 B-D，B和D不同组，加入并合并，总权7。
- 选 C-D，C和D已经在同一组（刚才合并包含了D），跳过。
- 选 C-E，C和E不同组，加入，总权13。
- D-E，已经在同一组，跳过。此时已经选了4条边（等于顶点数5减1），完成。最终MST也是 A-B, B-C, B-D, C-E，总权13，与Prim一致。
Kruskal手算的坑在“跳过环边”这一步。很多人排序排得很准，但忘了检查端点是否同组，导致最后树里出现一个环，直接丢分。我强烈建议你在草稿纸上给每个顶点写一个“组编号”，每加入一条边就更新组编号。这样即使边很多，也不容易出错。Kruskal的时间复杂度主要是排序 O(E log E)，所以在边较少的稀疏图上特别有优势，是竞赛中的常用算法。
4.4 两算法对比与选型建议
| 比较维度 | Prim算法 | Kruskal算法 |
|---|---|---|
| 贪心视角 | 从顶点集合扩张出发 | 从边权排序出发 |
| 每步操作 | 找连接已选/未选集合的最小边 | 找当前最小权边，判断是否成环 |
| 数据结构 | 优先队列/邻接矩阵 | 并查集 |
| 时间复杂度 | 堆优化 O(E log V)，稠密图表现好 | 排序 O(E log E)，稀疏图表现好 |
| 手算便利 | 适合边数多、图较密的题 | 适合边数少、权值容易排序的题 |
| 起始条件 | 必须指定一个起点（任意） | 不需要起点，直接全局排序 |
| 典型应用 | 网络布线、稠密图MST | 稀疏图MST、聚类 |
做题时怎么选？如果题目给了邻接矩阵且边比较多，用Prim顺手；如果题目给了边集让你排序，或者边比较少，用Kruskal看起来更清晰。两种算法得出的最小生成树总权重一定相同，但边的组合可能不唯一，这点在考试判断题里经常出现。如果图中有权值相等的边，MST就可能有多棵，总权值仍然相同。
另外补充一句：最小生成树不要求边的权值都是正数，负权边也照样能跑，只要图连通就行。因为生成树只要无环，负权越小越会被优先选到，这对Prim和Kruskal同样成立。手算时不要看到负权就慌，它不影响算法的正确性。
5. 常见易错点与排查技巧实录
5.1 五个让我“翻过车”的典型错误
第一类错误是把欧拉回路和哈密顿回路搞混。这几乎是图论刷题中“死伤最惨重”的地方，甚至一些考研辅导书里都有人写错。核心就是看题目问的是“经过每条边恰好一次”还是“经过每个顶点恰好一次”，做题前务必圈出主语。我有一个方法：把欧拉想象成“走遍整个城市每一条路”，把哈密顿想象成“旅行者到达每一个城市，但不用走完所有路段”，两种画面完全不同。
第二类错误是忽略连通性判定。所有欧拉判定、MST求解前都必须保证图连通。如果图本身不连通，你却还按公式去算度数，那会得出“存在欧拉回路”的荒谬结论。曾经有位同学拿一个两个孤立三角形的图来问为什么欧拉回路找不出来，就是因为没检查连通性。工作后做网络规划时，连通性更是第一前提，这个习惯要从做习题时就养成。
第三类错误是Kruskal不判环就往集合里加边。许多初学者觉得“只要没加过这条边就可以加”，结果选到最后凑成了含环结构。记住，生成树里绝对不能有环；哪怕少选一条边，也不能选成环的边。每次加边前后都要检查两个端点是否已属同一个“组”，这是Kruskal算法的灵魂。
第四类错误是Powell着色时没有按度数降序排序，或者扫描时没有从头到尾扫。我就见过有同学按节点编号直接一个一个涂，结果用了5种颜色，而按Powell步骤本来只需3种。Powell算法之所以要先排序，是为了让“最难搞”的顶点先占据颜色，避免后期为了它开新颜色。排序和扫描缺一不可。
第五类错误是在判断哈密顿回路时滥用充分条件：Dirac或Ore条件不满足，就断言没有哈密顿回路。这是逻辑上的错误，因为充分条件不满足只能说明“不确定”，不能排除存在性。正确的逻辑是：必要条件不满足则必不存在，充分条件满足则必存在，都不满足时只能手动尝试构造或说明未知。我把这个逻辑关系写在笔记本第一页，每次做题都会扫一眼。
5.2 做题时的自查清单与应试小抄
这里整理了一套我自己用的“图论四件套”自查清单，你可以当模板抄下来，做每一道综合题之前快速过一遍。
- 图是不是连通的？如果不连通，先看题目是否分连通分量讨论。
- 欧拉题：所有顶点度数是偶数吗？奇度点是0个还是2个？如果超过2个直接写不存在。
- 哈密顿题：删去任意k个顶点后，连通分量数是否 ≤ k？二部图两侧顶点数是否相等？两条充分条件是否满足？
- 着色题：有没有 K 阶完全子图作为下界？用Powell时先按度数排序，然后每种颜色从头扫到尾，边涂边核对“相邻不同色”。
- 最小生成树题：边权排好序了吗？Prim记得每步只从跨集合边中选最小；Kruskal记着判环。
- 最后再看一眼题目要求的是“回路”还是“路径”，有没有指定起点终点，别把回路和路径混为一谈。
把这份清单打印出来，刷题时放在手边，十天以后你会发现，错误率直线下降。考前几天也可以拿它当“默写提纲”，对着清单回忆每个算法的流程和适用条件，比盲目刷题效率高得多。
5.3 从习题到真实应用的延伸
图论不只在考卷上为难人，它背后的模型在现代工程里到处都是。欧拉回路可以用于邮递员投递路线的规划，现在很多快递站点的路径算法、扫地机器人“全覆盖清扫路径”都有一笔画的影子；哈密顿回路则出现在城市物流或旅游路线规划中，虽然精确求解很难，但近似算法已经广泛运作；图着色被用在教室排课、考试安排、无线频率分配等领域，把冲突对象建模成相邻顶点，然后把“不相容的不能同色”变成“不能同时占用同一资源”；最小生成树则更是网络设计的基本功，无论是工厂建局域网、城市铺设水管，还是芯片内部布线，都能转换成MST求解。
有同学觉得做这些“纸上谈兵”的题目太抽象，其实等你进了实际项目就会发现，离散数学给的不只是公式，而是一种“把现实问题翻译成图模型”的思维。哪怕你不做算法工程师，作为全栈开发，遇到资源分配问题时也能借这个思路快速给出一个合理方案。所以，把习题当作思维体操来练，一点也不亏。
最后再分享一个小技巧：复习这一章时，我习惯把所有判定条件和算法步骤画在一张A4纸上做成“知识星图”，中心写“图论习题”，向外辐射四个分支：欧拉、哈密顿、着色、MST，分支下只写关键词和公式。睡前花五分钟默想这张图，比连续刷三小时题的记忆效力还强。考试时哪怕一时卡住，脑中浮现这张图也能迅速定位到正确方法。希望这篇博文能帮你少走弯路，也欢迎在评论区交流你在图论题上踩过的那些“经典坑”。
