离散数学里图论这一块，历来是考试和实际应用中的“分水岭”。很多人觉得它抽象、题型多变，尤其是欧拉图、哈密顿图、着色和最小生成树这四座大山压在面前，光是看着概念就已经开始头疼。但说实话，这四块内容恰恰是图论里最“实在”的部分——它们都直接对应着现实里的路线规划、电路设计、资源分配这些问题。我当年学的时候也是一路踩坑过来的，今天这篇就把这些经典题型揉碎了讲，把判定定理、构造方法、算法步骤全部拆开，配合具体的习题演示计算过程，帮大家一次性把这块硬骨头啃下来。
整个图论的体系和刷题逻辑，可以概括成一条主线：图的连通性问题（欧拉、哈密顿）、图的最优化问题（最小生成树）、图的资源分配问题（着色）。这三类问题看似独立，实际上底层都是围绕“边”和“点”的关系在做文章。理解了这一点，你会发现所有题目都只是同一个核心逻辑的不同包装。
1. 内容整体设计与思路拆解
1.1 图论习题为什么绕不开这五个关键词
先说欧拉图。欧拉图的本质是“一笔画”问题，它关心的是是否存在一条路径，能把每条边恰好走一次。这个问题的起源是著名的柯尼斯堡七桥问题，算是图论这门学科的真正起点。到今天，欧拉路径和欧拉回路依然是快递路线规划、洒水车路线设计、电路板钻孔路径优化这些场景里的核心数学模型。
再说哈密顿图。哈密顿图关心的是是否存在一条路径，能把每个顶点恰好访问一次。这个问题表面上看和欧拉图只是“边”和“点”的差别，但难度完全不同。欧拉图有非常简洁的充要条件，看一眼度数就能判断；而哈密顿图的判定在一般情形下是一个NP完全问题，也就是说没有已知的多项式时间算法能完美判定所有图。考试里只会考一些充分条件和必要条件，这个区别很多人没意识到，导致做题时总想把哈密顿图也套一个简单的公式，结果就是越套越乱。
Powell着色解决的问题是“地图染色”问题的扩展。相邻的区域不能用同一种颜色，那么给一张图染色，最少需要几种颜色？Powell算法是一种基于顶点度数降序排列的贪心着色法，它不保证能得到最优的色数，但在实际使用中效率很高，而且对于大部分图来说效果已经足够好。考试中考察Powell算法时，重点往往不是证明，而是能不能按步骤把着色过程和最终色数算出来。
Prim和Kruskal两种最小生成树算法，解决的则是“连通所有点且总边权最小”的问题。这个问题的实际背景是网络布线：要把一堆节点用最低成本连通起来，怎么选线？两种算法的思路完全不同——Prim是“加点法”，从某个点开始不断把最近的未加入点拉进来；Kruskal是“加边法”，把所有边按权值排序后从小到大选，选边时保证不成环。这两种方法的对比本身就是考试常客，后面的具体习题里我会详细拆。
1.2 从实战角度看这几类题型的分布与难度层级
从我刷过的题和带过的经验来看，这五块内容的考察频率和难度是有梯度的。
欧拉图属于“送分题”，只要记住两个判定定理（无向图连通且无奇度顶点 => 存在欧拉回路；连通且恰有两个奇度顶点 => 存在欧拉通路），再配合实际问题里的“一笔画”变形，基本都能拿满分。难点在于很多人忽略了“连通”这个前提，导致判断失误——这一点我在后面的常见错误里会专门强调。
哈密顿图则是最容易让人困惑的。命题者特别喜欢拿那些“看起来很像哈密顿图但实际不是”的图来出题，让你应用必要条件和充分条件时栽跟头。必要条件是：如果图存在哈密顿回路，那么删去任意k个顶点后，剩余连通分量数不超过k。这个条件说起来简单，但真下手做题时需要细心数连通分量，一步数错就全盘皆输。充分条件主要是Dirac定理和Ore定理，它们给出了足够强的保证，但要注意这些条件不满足不代表不存在哈密顿回路。
Powell着色是“操作题”，只要理解“度数大者优先”和“不邻接可同色”这两条规则，一步步往下画就行。真正的麻烦在于颜色分配顺序的排布，尤其是当多个未着色顶点与已着色顶点都不相邻时，选择谁先着色会直接影响后续的颜色分配，最终导致色数不同。
Prim和Kruskal是“计算题”，难度取决于图中节点和边的数量。Prim的典型错误是在“已选集合”和“未选集合”之间选边时把两边都视为可连通，结果选出了环；Kruskal的典型错误是在判断“是否成环”时只看局部，忽视了间接形成环的情况。这两块我会在习题演示环节详细展示每一步怎么操作。
2. 欧拉图核心细节解析与实操要点
2.1 判定定理深入理解：不要只背结论
先明确定义。无向图G中存在欧拉回路，当且仅当G是连通的，并且所有顶点的度数均为偶数。存在欧拉通路（不需要回到起点），当且仅当G是连通的，并且恰好有两个顶点的度数为奇数。
这里有个容易被忽略的点：连通性判断。考试时题目给的图往往视觉上看起来连成一片，但实际上可能存在孤立的顶点或孤立的子图。一个最典型的例子：图中有两条互不相连的环状结构，每个环上的顶点度数都是偶数，你一看所有顶点度数都是偶数，马上判断存在欧拉回路——错了，因为图本身不连通，根本不可能有一条路径覆盖所有边又回到起点。所以做题时第一步永远先检查连通性，确认只有一个连通分量。
为什么会这样？可以直观想：欧拉回路需要一次性走完所有边，如果图不连通，从A部分走到B部分就没有“桥”可以过，那条路径根本不存在。这个道理很简单，但考场上因为时间紧张而忽略检查连通性的人非常多。
2.2 构造欧拉回路的阶梯法（Hierholzer算法）
判断完存在性之后，习题里经常要求构造出一条具体的欧拉回路。这里推荐用阶梯法，也叫Hierholzer算法，理解起来比Fleury算法更直观，操作起来也更不容易出错。
算法核心出发点是：从一个顶点出发，沿着未走过的边走，每走一条边就把它标记为已用，直到走回起点，得到一条回路。如果这条回路覆盖了所有边，工作完成；如果没有，找到回路中某个仍然有未使用边的顶点，从这个顶点出发再跑一个新回路，然后把新回路“拼接”到原回路中。
我拿个例子说明。假设有一个图，顶点集合为{a, b, c, d, e}，边集合为ab, bc, ca, ad, de, ea。检查度数：a度数3，b度数2，c度数2，d度数2，e度数3。有两个奇度顶点a和e，所以存在欧拉通路，不过凑巧这个图也满足所有偶数度数的要求就是回路，这里刚好存在，不过先按通路来处理。如果题目要求欧拉回路，图必须调整。这个例子更典型的做法是找通路：从a出发，沿a-b-c-a走回a，此时a处还能继续走a-d-e-a，拼接起来得到a-b-c-a-d-e-a，所有边都覆盖到了。这正好是一条欧拉回路。
实际构造时需要注意拼接位置的选择。在“回路中有顶点仍有未使用边”时，选择哪个顶点继续扩展，会影响最终回路的形态，但不会影响正确性。考场时间有限，原则是：随便选一个还有边可走的点，继续跑就行。
注意：阶梯法构造欧拉回路时，不需要考虑边的删除顺序是否合理，因为回路拼接保证了每条边恰好走一次。如果你使用的是Fleury算法，则需要谨慎选择“桥”——也就是会断开未走过部分的边——否则可能走进死胡同。阶梯法更推荐考试中使用。
2.3 欧拉图习题演示：从判定到构造完整走一遍
来看一道综合题。题目给出无向图G，顶点为v1到v6，边列表如下：v1v2, v2v3, v3v1, v4v5, v5v6, v6v4, v1v4。这道题的图表面上看起来是两个三角形和一个连接边。
第一，检查连通性。从v1出发能到v2、v3、v4，从v4能到v5、v6，所以所有顶点在同一个连通分量内，连通性满足。
第二，计算每个顶点的度数。v1与v2、v3、v4相连，度数为3；v2与v1、v3相连，度数为2；v3与v2、v1相连，度数为2；v4与v5、v6、v1相连，度数为3；v5与v4、v6相连，度数为2；v6与v5、v4相连，度数为2。统计结果：v1度数为3（奇），v4度数为3（奇），其余顶点度数均为偶数。
第三，根据定理判断：连通且恰好两个奇度顶点，所以存在欧拉通路，但不存在欧拉回路。如果你非要在图里找欧拉回路，会发现怎么走都有一个边落到一边，这就是数学定理给出的确定性结论。
第四，构造欧拉通路。起点必须是奇度顶点之一，从v1开始：v1-v2-v3-v1-v4-v5-v6-v4。检查每条边：v1v2、v2v3、v3v1、v1v4、v4v5、v5v6、v6v4，所有边都恰好走了一次，起点v1和终点v4都是奇度顶点，符合定理预期。
这道题里最容易踩的坑是：第一时间看到所有边连接自然，下意识判断为欧拉回路，忽视了两个奇度顶点的存在。所以每次做题，度数计算一定要列成表，不要心算，尤其在考场那种容易出错的氛围下，列表是最稳的。
3. 哈密顿图：条件判定与常见陷阱
3.1 必要条件与充分条件的边界感
哈密顿图的定义是：经过每个顶点恰好一次的回路（哈密顿回路）；经过每个顶点恰好一次但不要求回到起点的路径（哈密顿通路）。考试考查的重点集中在回路的判定上。
必要条件是：如果图G存在哈密顿回路，那么对于任意一个非空真子集S，从图G中删除S中的所有顶点后，得到的连通分量数p(G-S)必须满足p(G-S) ≤ |S|。这个条件的逻辑是：哈密顿回路是一根完整的环，你从环上拿走k个点，环最多被切成k段，不可能产生k+1个互不相连的片段。
这里就需要特别注意：这是一个必要条件，不是充分条件。也就是说存在某些图满足这个条件但没有哈密顿回路。很多初学者把这个条件当成充要条件去用，拿一个满足条件的图就说它是哈密顿图，这是逻辑错误。
充分条件方面，最常用的两个定理：
- Dirac定理：如果图G有n个顶点，且n≥3，每个顶点的度数至少为n/2，那么G存在哈密顿回路。
- Ore定理：如果图G有n个顶点，且n≥3，对于图中任意两个不相邻的顶点u和v，都有deg(u)+deg(v)≥n，那么G存在哈密顿回路。
注意这两个条件的语气：满足就一定有哈密顿回路；但不满足并不代表一定没有。考试中常见的出题思路恰恰是利用这种“不满足但不代表不存在”的情况来制造干扰项。
3.2 用判定条件的角度拆解经典习题
来看一道高频题目。图G有7个顶点，各顶点度数分别为3, 3, 4, 4, 4, 5, 5。需要判断它是否为哈密顿图。
首先检查Dirac定理的适用条件：n=7，n/2=3.5，所以每个顶点的度数至少应为4。但这里有顶点度数为3，低于4，Dirac定理条件不满足。
然后检查Ore定理的适用条件：任意两个不相邻顶点度数之和至少为7。由于存在度数为3的顶点点，另一个如果度数也为3且不相邻，那么度数和为6 < 7，Ore定理条件不满足。
这时候容易得出结论“不是哈密顿图”——错了。两个充分条件不满足，只能说明无法通过这两个定理保证存在哈密顿回路，并不能排除哈密顿回路的存在。事实上这种度数序列的图很可能仍然有哈密顿回路。命题者在这里埋的坑是：把“充分条件不满足”偷换为“结论不成立”。
反过来，如果一道题给出图有8个顶点，每个顶点度数都是4，那么n/2=4，所有顶点度数恰好等于4，满足Dirac定理条件，可以直接判断存在哈密顿回路。这种题就是送分题。
还有一个经典的必要条件应用场景：考试给出一张图并要求“证明不存在哈密顿回路”，这时就需要找一个特定的顶点子集S，使得删除S后剩余连通分量数大于|S|。怎么找这个S？经验是优先找“割点”周围的结构，具体来说找一个顶点删除后产生大量连通分量的情况。比如一张图如果有一个中心顶点连接着其余所有的团块，把这个中心顶点拿出来当S={v}，如果删除后产生2个以上连通分量，那么p(G-S)≥2 > 1=|S|，直接就能否定哈密顿回路的存在。
3.3 构造哈密顿回路的实操经验
如果题目要求你直接找出一条哈密顿回路（而非证明存在性），最朴素的策略是手工回溯。从一个顶点出发，看有没有未访问过的相邻顶点可以走，优先走那些“看起来没有其他退路”的顶点——也就是邻居最少的顶点。
这个原则本质上和迷宫问题中的Warnsdorff规则类似：优先访问下一步可选路径最少的顶点，这样不容易走到死胡同。比如一个顶点i只有一个未访问邻居j，从其他任何顶点到达i后必须立刻走j，否则i就无法被访问。人类手工解哈密顿回路时，盯着这种“低自由度”顶点下手，效率远高于随便乱走。
我拿一个具体图形来说明。给定图G的顶点为1到6，边为12, 23, 34, 45, 56, 61, 13, 46。从顶点1出发。顶点1的邻居有2, 3, 6；顶点3的邻居有1, 2, 4；顶点6的邻居有1, 4, 5。看起来所有顶点的自由度差不多，那就按字典序走：1-2-3-4-5-6-1。检查路径覆盖了所有顶点，且每对相邻顶点之间都有边，1和6之间有边61，所以1-2-3-4-5-6-1是一条哈密顿回路。
再换一个更“阴间”的图。顶点1到6，边为12, 16, 23, 26, 34, 35, 45, 46。试着从1开始走：1-2-3-4-5，现在在5，邻居是3和4，都已经访问过，卡死了，这不是一条哈密顿回路，但这只说明这条路径失败，不代表这个图没有哈密顿回路。换条路：1-6-2-3-4-5，走到5了，5的邻居是3和4，都访问过，依然卡死。再试：1-6-5-4-3-2，走到2，2的邻居是1、3、6，都访问过，卡死。好几条路线都死掉后，可以怀疑没有哈密顿回路了，但不经过严格排除（例如用必要条件排除）不能下结论。这也体现出哈密顿图的判定为什么比欧拉图难那么多——没有“万能钥匙”，每一步都是在试探。
4. Powell着色算法：步骤拆解与习题实战
4.1 从四色定理到Powell贪心策略
图着色问题的核心是：给每个顶点分配一种颜色，要求任何一条边连接的两个顶点颜色不同，目标是使用尽可能少的颜色数（即色数）。
真实的“四色定理”说任何平面图都可以用四种颜色完成地图着色，但计算一个给定的图最少需要多少种颜色，在一般情况下同样是NP难的。考试跑Powell算法就是为了在多项式时间内得到一个“足够好”的近似方案——虽然不一定是最优色数，但步骤清晰、操作可复现，非常适合出题。
Powell算法的核心规则是：把所有顶点按度数从大到小排序；按这个顺序遍历顶点，给每个顶点分配第一个可用的颜色（即与所有已着色邻居都不同的颜色中编号最小的那个）。这个“贪心”体现在选择颜色时只盯着当前局部约束，不往回考虑已经分配好的颜色是否还能优化。
4.2 完整的Powell着色习题演示：表格全流程
来看一道典型的练习题。图G有8个顶点，邻接关系如下：
- v1与v2, v3, v4, v5相连
- v2与v1, v3, v6相连
- v3与v1, v2, v4, v7相连
- v4与v1, v3, v5, v8相连
- v5与v1, v4, v6相连
- v6与v2, v5, v7相连
- v7与v3, v6, v8相连
- v8与v4, v7相连
第一步，计算所有顶点的度数： v1与v2, v3, v4, v5相连，度数为4； v2与v1, v3, v6相连，度数为3； v3与v1, v2, v4, v7相连，度数为4； v4与v1, v3, v5, v8相连，度数为4； v5与v1, v4, v6相连，度数为3； v6与v2, v5, v7相连，度数为3； v7与v3, v6, v8相连，度数为3； v8与v4, v7相连，度数为2。
第二步，按度数从大到小排列顶点序列：v1(4), v3(4), v4(4), v2(3), v5(3), v6(3), v7(3), v8(2)。度数相同的情况下，按照编号从小到大排。
第三步，依次着色：
- 先着色v1，使用颜色1。
- 接着v3，v3与v1相邻，不能使用颜色1，使用颜色2。
- v4，与v1和v3都相邻，不能使用颜色1和2，使用颜色3。
- v2，v2与v1和v3相邻，不能使用颜色1和2，但v2与v4不相邻，所以颜色3可以分配给v2。这里注意，颜色编号越小越优先，颜色3已经被v4占用，但只要v2与v4不相邻，颜色3就能复用。所以v2使用颜色3。
- v5，v5与v1和v4相邻，不能使用颜色1和3，与v2也不相邻，那么颜色2是否能使用？需要检查v5与v3是否相邻——v5与v6、v4、v1相连，不与v3相连，也不与v2相连，所以颜色2已经使用在v3上，v5与v3不相邻，可以复用颜色2。v5着色为颜色2。
- v6，v6与v2和v5相邻，与v7相连。v6不与v1相邻，但颜色1已经被v1占用，v6和v1不相邻，可以复用？不对，要看v6和v1是否有一条边——图中没有，所以v6可以使用颜色1。现在v6着色为颜色1。
- v7，v7与v3、v6、v8相连。v7与v1不相邻，颜色1已分配给v1和v6，而v7与v6直接相邻，所以不能使用颜色1。v7与v3相邻不能使用颜色2；v7与v4不相邻，颜色3可以复用。v7着色为颜色3。
- v8，v8与v4、v7相连。v8与v1不相邻，颜色1可用；与v3不相邻，颜色2可用，但颜色1编号更小，所以v8使用颜色1。
最终着色结果：颜色1集合为{v1, v6, v8}，颜色2集合为{v3, v5}，颜色3集合为{v4, v2, v7}。一共用了3种颜色。
这就是Powell算法的完整操作。整个过程的关键是每次分配时，只需要检查“已着色邻居的集合”用了哪些颜色，从中排除，然后取编号最小的可用颜色。
4.3 为什么Powell不保证最优色数：反例与认知
这里必须说清楚一个事实：Powell算法给出的色数不一定是最小色数。一个经典的反例是二部图（比如K_{3,3}），它的最小色数是2，但如果顶点度数排列导致了贪心分配每步都恰好避开2色方案，Powell给出的结果可能是3甚至更多。
考试中如果题目问“用Powell算法着色，给出至少需要多少种颜色”，你要回答的是Powell算法算出来的那个数，而不是最优色数——两者可能不相等。如果题目问“这个图的色数是多少”，那就需要你另想办法去证明最优性，比如证明存在k着色且任何k-1着色都不可能。
实操中还有一个小技巧：为了获得更好的着色效果，可以在Powell排序之后，对“当前未着色顶点”动态更新可用颜色检查顺序。说白了，按度数降序排完之后，如果度数相同，优先选那些邻接已着色顶点数量更多的顶点先着色，这样能在后续保持更低颜色的可能性更大。这个方法在考试里不一定要求，但平时练习用能加深理解。
提示：验证Powell着色结果正确性的最快方法，是逐一检查每条边的两个顶点颜色是否不同。全部不同才说明没有违反着色规则；如果有一处相同，就要回到对应步骤检查颜色选择是否出错。
5. Prim与Kruskal最小生成树算法对比与习题实操
5.1 两种算法的底层逻辑与适用场景对比
最小生成树问题：给定一个带权无向连通图，寻找一棵生成树，使得树上所有边的权值之和最小。经典的两个算法是Prim和Kruskal。它们本质都是贪心算法，但贪心的对象不同。
Prim算法从一个起始顶点出发，维护一个“已选入生成树的顶点集合S”，每一步从连接S内顶点与S外顶点的所有边中，选择权值最小的那条边，把这条边“桥接”进来的顶点加入S，直到所有顶点都加入S。它的核心数据结构是“候选边集合”，每一步只从横跨内外的边里挑，不会产生成环问题。
Kruskal算法把所有边按权值从小到大排序，从最小权值开始逐条考虑，如果一条边的两个端点当前不在同一个连通分量里，就选择这条边，合并这两个连通分量；否则跳过。它的核心难点是判断“是否成环”，这需要维护并查集或者某种连通性结构。
对比一下：
- Prim适合稠密图（边数多），如果用邻接矩阵实现复杂度为O(V^2)，与边数无关；如果用二叉堆优化则复杂度为O(E log V)。
- Kruskal适合稀疏图（边数少），复杂度主要来自排序O(E log E)，后续并查集操作几乎线性。
考试时两种都要熟练掌握。Prim的操作直观但计算量偏大，Kruskal的排序前置步骤在那里，需要细心排错。
5.2 Prim算法手算流程：完整步骤表
先看一道涉及7个顶点的图，顶点命名为A到G，带权边列表如下：
- AB=7, AD=5, BC=8, BD=9, BE=7, CE=5, DE=15, DF=6, EF=8, EG=9, FG=11
用Prim算法，起点选A。整个过程用一个表格记录每一步S集合、候选边、选择的边：
步骤0：S={A}，候选边为A到B(7)、A到D(5)，最小值是AD=5，选择AD，加入D。S={A, D}。
步骤1：现在考虑所有从{A, D}连向外部顶点的边。需要仔细列出：A到B(7)，A到D已经选过不再考虑，D到B(9)，D到C(15)，D到E(15)，D到F(6)。其中最小值是D到F的6，选择DF，加入F。S={A, D, F}。
步骤2：S={A, D, F}，候选边包括：A到B(7)，D到B(9)，D到C(15)，F到E(8)，F到G(11)。最小值为A到B的7，选择AB，加入B。S={A, D, F, B}。
步骤3：S={A, D, F, B}，现在候选边是连接内外的所有边。内点A、D、F、B，外点C、E、G。列出：B到C(8)，B到E(7)，D到C(15)，D到E(15)，F到E(8)，F到G(11)。最小值为B到E的7，选择BE，加入E。S={A, D, F, B, E}。
步骤4：S={A, D, F, B, E}，外点为C、G。候选边为：B到C(8)，D到C(15)，E到C(5)，E到G(9)，F到G(11)。最小值为E到C的5，选择EC，加入C。S={A, D, F, B, E, C}。
步骤5：S={A, D, F, B, E, C}，只剩G一个外部点。候选边为：E到G(9)，F到G(11)，C到G没有直接边（图中不存在），所以最小值是E到G的9，选择EG，加入G。S={A, D, F, B, E, C, G}，全部顶点加入。
最终最小生成树的边集为AD(5), DF(6), AB(7), BE(7), EC(5), EG(9)，权值总和为5+6+7+7+5+9=39。
这个手算过程演示了Prim算法的本质：每一次都是“从已选集合跨越到未选集合”的最小边。注意在第3步中，B到E的7和F到G的11同时出现在候选列表里，最小值是B到E，选择了E而不是F或G，这个选择完全由权值大小决定。
注意：Prim算法每一步产生的新树一定是一棵树，不需要额外判断成环——因为加入的边永远连接着“已选”和“未选”两个集合，天然不会形成环。这一点和Kruskal非常不同，也导致手算Prim比手算Kruskal少一道判环工序。
5.3 Kruskal算法手算流程：排序、加边、判环
同样用上面那张图。第一步，把所有边按权值从小到大排列： AD=5, CE=5, DF=6, AB=7, BE=7, BC=8, EF=8, BD=9, EG=9, DE=15, FG=11。 等等，这里排序需要仔细检查：FG=11，DE=15，所以正确的升序序列为： AD=5, CE=5, DF=6, AB=7, BE=7, BC=8, EF=8, BD=9, EG=9, FG=11, DE=15。
第二步，逐条考虑，边是否加入取决于两个端点是否已经在同一连通分量：
- 加入AD。当前连通分量：{A, D}。
- 加入CE。当前连通分量：{A, D}, {C, E}。
- 加入DF。D和F原本不在同一分量，加入后连通分量变为{A, D, F}, {C, E}。
- 加入AB。A和B不在同一分量，加入后变为{A, D, F, B}, {C, E}。
- 加入BE。B在第一个分量，E在第二个分量，加入后合并为一个大分量{A, B, D, F, C, E}。
- 加入BC。B和C已经在同一分量内，如果加入BC会形成环（B-E-C-B），所以跳过。
- 加入EF。E和F已经在同一分量内，加EF会形成环（E-C-?不对，看路径：E到C已选，C到B已选，B到A已选，A到D已选，D到F已选，所以E和F已经连通），跳过。
- 加入BD。B和D已经在同一分量，跳过。
- 加入EG。E和G不同分量，加入。此时所有顶点都已经被覆盖了，算法可以提前结束。最终边集为AD, CE, DF, AB, BE, EG，权值和也是5+5+6+7+7+9=39。
和Prim的结果一致，这验证了最小生成树唯一性在这个例子中的体现。注意两种算法得到的边集可能不同，但权值和一定相同。
Kruskal手算时最常见的错误是排序错了。边一多，点一多，排序时稍微走神就把9和11的位置排反了。我的习惯是：先单独写一列不带原图的边权表，排序完再对照原图检查两三遍。在考场上这个“检查”动作能帮你避免至少半分以上的损失。
5.4 两种算法选型：什么情况下用哪个
实际解决问题时选哪种算法，主要看数据规模。邻接矩阵存储的稠密图，Prim写起来方便，复杂度稳定；边数特别多的图，如果硬用Kruskal，排序本身开销就会很大。反过来，稀疏图用Kruskal更舒服，因为只需要把所有边排个序，然后并查集判环，不需要维护复杂的“候选边集合”。
另外，Prim有个天然适合并行化的地方：每一步只需要考虑当前集合的边界边，可以用优先队列维护，代码结构清晰。Kruskal的并查集在考试中往往需要自己实现路径压缩，并且排序算法需要稳定，否则会出现“权值相同的边选哪一个”的分歧。考试里如果两道最小生成树题目同时出现，我个人的习惯是：先看了一眼图的表示，边数小于顶点数两倍就无脑Kruskal，否则无脑Prim。这个经验不一定是最优解，但足够稳。
6. 常见错误与排查技巧实录
6.1 欧拉图判定里的三大致命误判
第一个错误，也是最常见的：忘了检查连通性。我见到太多同学拿到图，数完度数就下结论。明明图被拆成了两个子图，每个子图内部所有顶点度数都是偶数，但整体就是一个不连通图，根本不存在欧拉回路。判定的前提是连通，这一步永远放在最前面。
第二个错误：把欧拉回路和欧拉通路混为一谈。题目问“是否存在欧拉回路”，你发现恰好两个奇度顶点，回答“存在”——错了。两个奇度顶点只对应欧拉通路的存在性，回路要求所有顶点都是偶数度。反之，如果所有顶点都是偶数度，那么欧拉回路必然存在，同时也隐含欧拉通路的存在（因为你把回路截断就是通路）。逻辑要分清。
第三个错误：在构造欧拉通路时，起点选错了。通路的起点必须是奇度顶点，终点是另一个奇度顶点。如果你从偶数度顶点出发，走到后面会发现有边没走完但已经走不动了。这个错误在阶梯法的实现中尤其隐蔽，因为第一步走回起点形成回路看起来“一切正常”，但剩下的边根本拼不上。
6.2 哈密顿图判定中“充分条件当充要条件用”
这个错误的频次非常高。Dirac定理和Ore定理如果满足，我们就可以放心写“该图存在哈密顿回路”；但如果两个都不满足，绝对不要直接写“该图不存在哈密顿回路”。逻辑上的区别在于充分条件和必要条件的单向性，考试中的命题陷阱基本都围绕这个点。
还有一个实用技巧：当你想证明一个图不存在哈密顿回路时，优先找一个“删点破坏连通”的顶点子集。很多图的“弱点”往往围绕在度数最低的几个顶点附近，不要只在中心顶点上使劲找。找到一个删一个顶点就导致图分成三块的情况，直接得出p(G-S)=3 > 1，否证完成。这种题在考场上思路通了，一分钟就能写完。
6.3 Powell着色时“颜色优先级”被忽视
很多人在Powell着色时，给一个顶点分配颜色时只思考“能和上一个顶点颜色不同”，于是随手填了下一个编号，导致后面颜色数量暴涨。实际上每次都要从头看：颜色1能不能用？如果所有邻居都没用颜色1，就用颜色1；颜色1不能用，再看颜色2。这个“重新从头找最小可用的颜色”的动作，是节省色数的关键。
另外一个问题出现在检查环节：完成着色后如果没有逐边检查，一旦颜色冲突，你需要倒回去重新修改所有后续分配。我建议养成表格记录的习惯：每一行一个顶点，记下“已着色邻居用了哪些颜色”和“当前顶点使用的颜色”，这样出问题时可以直接定位。
6.4 Prim与Kruskal的判环错误和排序失误
Kruskal最经典的手算错误是：加边顺序按照排序来，但漏看了某条边的两个端点已经在同一分量中，直接加进去，结果生成树里出现了环。手工判断时，如果图复杂，可以在草稿纸上不断更新“分量图”，每加入一条边就重新画一幅简图，确认所有选中的边构成的子图是一棵树。这个方法虽然耗时，但正确率最高。
Prim最经典的错误是：在候选边列表里加入了“内-内”边。比如上面例子中，当S={A, D, F, B}时，有些同学会不小心把D到F（已选边）又重新列进候选边，虽然不影响最终选择，但会干扰判断。实际上Prim的候选边必须严格是“一个端点在S内，另一个端点在S外”的边，不然“加入后不成环”的承诺就不成立了。
还有一种手算错误是：遍历的时候只盯着“最新加入的顶点”的邻边看，忽略了其他S内顶点可能有更小的连接外部点的边。比如Prim第3步，最新加入的顶点是B，很多人只关注B的邻边就选了B到C(8)，忽略了B到E(7)更小；更进一步，甚至忽略了A到B已经选过的边不算候选，导致起点误判。这个细节必须反复提醒自己。
6.5 综合训练：混合题型的解题顺序策略
考试时的综合大题经常会把多个知识点串起来：给一张带权图，第一问判断是否存在欧拉回路，第二问判断是否是哈密顿图，第三问用Powell着色，第四问求最小生成树。这种题型的核心价值在于考查概念之间的边界。
我的经验是：拿到题先花两分钟整体看一遍全图，把所有顶点的度数列出来，把所有边的权值标好，再用铅笔勾画可能的哈密顿回路试探路线。度数表是所有后续操作的共用基础——欧拉判定直接看度数，Powell排序也按度数，哈密顿定理检查也离不开度数。先把这张表做出来，整道题的节奏就稳了。
做Powell着色时如果发现用了4种颜色，但你在试探中肉眼观察到3种颜色可行，一定不要急着改答案，先按题目要求来。题目说“Powell算法着色”就按Powell的步骤出结果，算法的结果和最优色数之间有差距是正常现象，命题老师扣分是扣在步骤分上，不会因为你没用更优方案而加分。
6.6 实战经验总结：从错误里提炼的速查表
我在刷题过程中总结了一张自查表，每次做完整图论习题都会对照一遍，现在分享给大家：
- 欧拉判定的第一步永远是连通性，不是数度数。
- 欧拉回路要求所有点偶度；欧拉通路要求恰好两个奇度点。
- 哈密顿图充分条件不满足，不能推出“不存在哈密顿回路”。
- 幂次数列的度数排序建议从左到右降序，同度数按编号升序，减少歧义。
- Powell着色时颜色编号永远从1开始，不要跳号。
- 构造欧拉回路用阶梯法，手工回溯时优先处理“自由度低”的点。
- Kruskal选边前先排序，判环画图；Prim选边前先标出内点、外点，再找最小边。
- 所有计算题步骤都写下来，不要心算——这是考场拿分的关键。
这张表看起来简单，但每一条都是从大量错题里提炼出来的。做题前看一遍，比埋头硬刷十道题还有用。
7. 综合演练：一道多知识点融合题型全程解析
7.1 题目呈现与第一遍审题
为了把前面所有的内容串起来，我们看一道综合题。给定一个带权无向图H，顶点集合为{a, b, c, d, e, f}，边及其权值如下：ab=4, ac=3, ad=6, bc=5, bd=7, be=8, cd=2, ce=9, de=4, df=5, ef=6。
题目有几道设问： 第一，判断图H是否存在欧拉回路或欧拉通路； 第二，判断图H是否满足Dirac定理的条件； 第三，用Powell算法给图H着色（要求写出步骤和颜色分配）； 第四，分别用Prim和Kruskal求最小生成树，比较两种结果。
拿到题，先做基础信息整理。算度数：a连接b、c、d，度数为3；b连接a、c、d、e，度数为4；c连接a、b、d、e，度数为4；d连接a、b、c、f，度数为4；e连接b、c、d、f，度数为4；f连接d、e，度数为2。度数序列：a为3（奇），b为4，c为4，d为4，e为4，f为2。恰好一个奇度顶点？实际上把所有度数列出来：3, 4, 4, 4, 4, 2，奇度顶点只有a一个。这个情况欧拉定理怎么说？每个无向连通图中奇度顶点的个数一定是偶数，所以这里的度数统计必然有问题。
重新检查邻接列表。题目给出的边是ab、ac、ad、bc、bd、be、cd、ce、de、df、ef。计算a与b、c、d相连，度数为3；b与a、c、d、e相连，度数为4；c与a、b、d、e相连，度数为4；d与a、b、c、e、f相连——注意de边和df边似乎漏了dc？回到题目，cd=2，所以d与c相连，再加上a、b、e、f，d的度数为5；e与b、c、d、f相连，度数为4；f与d、e相连，度数为2。修正后的度数序列：a=3, b=4, c=4, d=5, e=4, f=2。奇度顶点为a和d，共两个，这下就符合“奇度顶点个数为偶数”的规律了。因此答案是：存在欧拉通路，起点为a，终点为d；不存在欧拉回路。
这个例题就是想强调度数的统计必须极端仔细，稍有一个邻边漏数，后面所有判定全都会错。
7.2 第二问：Dirac定理条件检验
n=6，n/2=3。Dirac定理要求每个顶点度数至少为3。当前最小度数是f的度数2，低于3，所以Dirac定理条件不满足。但按前面强调的，不能因此就说这个图不是哈密顿图。如果题目继续问是否存在哈密顿回路，需要另行判断。实际上这个图是否存在哈密顿回路可以尝试构造：a-b-c-d-f-e-a？检查边：ab有，bc有，cd有，df有，fe有（ef=6），ea有吗？e-a之间没有直接边，所以这个序列不成立。再试：a-c-b-d-f-e-a，检查ac有，cb有，bd有，df有，fe有，ea没有，还是不成立。可以尝试其他路径，但是想要严谨否定就得用必要条件，这里就不继续展开了，重点在于让大家意识到判断过程的严谨性要求。
7.3 第三问：Powell着色操作记录
依然先按度数降序排列顶点：d(5), b(4), c(4), e(4), a(3), f(2)。同度数按字母序。
着色过程：
- d用颜色1。
- b与d相邻，不能用颜色1，改用颜色2。
- c与d、b都相邻，不能用颜色1和2，用颜色3。
- e与b、c、d都相邻，这三种颜色都不能用，用颜色4。
- a与b、c、d相邻，与e不相邻，颜色1-3都已被邻居占用，但颜色4也已经被e占用，且a与e不相邻，所以a可以用颜色4。
- f与d、e相邻，f与a不相邻，颜色1被d占用且d与f相邻，不能用；颜色2被b占用但b与f不相邻，所以f可以用颜色2。
最终着色结果：颜色1={d}，颜色2={b, f}，颜色3={c}，颜色4={e, a}。一共用了4种颜色。
这个示例说明一个关键点：即使看起度数最高的d一口气占用了颜色1，后续顶点的颜色选择仍然要逐一检查与所有邻居的冲突关系，而不是只和上一个顶点比。
7.4 第四问：两种最小生成树算法结果对比
用Prim算法，可选起始点为a。排序候选边：从a出发，ac=3为最小，选择ac；当前集合{a, c}，候选边为c到b(5)、c到d(2)、c到e(9)，以及a到b(4)、a到d(6)。最小值是c到d的2，选择cd；当前集合{a, c, d}，候选边为d到f(5)、d到b(7)、d到e(4)，以及a到b(4)、c到b(5)、c到e(9)。最小值是a到b的4和d到e的4，出现同权。规范做法是任选其一。
选择ab，当前集合{a, c, d, b}，候选边为b到e(8)、d到e(4)、d到f(5)、c到e(9)。最小值是d到e的4，选择de；当前集合{a, c, d, b, e}，候选边为e到f(6)、d到f(5)。注意b到e虽然是候选边的端点连接内外，权值为8，但8>5，所以不选。选d到f的5，加入f。最终边集为ac(3)、cd(2)、ab(4)、de(4)、df(5)，总权值3+2+4+4+5=18。
用Kruskal算法，先排序全部边：cd=2, ac=3, ab=4, de=4, bc=5, df=5, ad=6, ef=6, bd=7, be=8, ce=9。
逐条加边：
- cd加入。
- ac加入。连通分量：{c, d, a}。
- ab加入。连通：{a, b, c, d}。
- de加入。d和e不同分量，合并为{a, b, c, d, e}。
- bc，b和c已同分量，跳过。
- df，d和f不同分量，加入。所有顶点已覆盖，算法结束。 最终边集为cd(2)、ac(3)、ab(4)、de(4)、df(5)，总权值也是18。两种算法的结果完全一致，相互印证了结果的正确性。
这道综合题几乎覆盖了本节所有知识点，如果每一步都能独立完成，那么离散数学图论部分的这五座大山，就基本拿下了。
8. 一些心得和补充
我个人在实际做题过程中最大的体会是：图论题最怕的不是算法不会，而是看题不仔细、统计不严谨。无论欧拉、哈密顿、着色还是最小生成树，本质上都是在一张具体的图上做精确的数学推理。步骤写得越详细，出错概率越低。尤其是那些看起来“差不多”就能得到结果的题，写全步骤和心算出答案，得分差别往往很大。
最后再分享一个小技巧：图论题目做之前，先花三十秒把整张图的顶点度数表写出来。这不仅是为了应对欧拉判定，它同时为Powell排序、Dirac检查、甚至构造欧拉路径都提供了基础数据。一张好的度数表就是整张图的“索引”，有了它，图论综合题从被动接招变成主动布局，做题体验完全不一样。
