★ FEATURED ARTICLE 离散数学里的图论部分向来是让不少同学又爱又恨的章节。爱它是因为图论题目往往形象直观画个图就能窥见全貌恨它是因为知识点又多又杂光是欧拉、哈密顿、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,CB度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, keylambda 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度32连接1、3、5度33连接1、2、4、5度44连接1、3、6度35连接2、3、6度36连接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然后看44与2不相邻边集中没有2-4所以4也可以涂颜色3。最终全部着色完成3和6用颜色11和5用颜色22和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 2A-C 3B-C 1B-D 4C-D 5C-E 6D-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总权 214613。这是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-BA与B在不同组A自己一组B和C一组合并A-B-C总权3。选 A-C此时A和C已经在同一组加入会成环跳过。选 B-DB和D不同组加入并合并总权7。选 C-DC和D已经在同一组刚才合并包含了D跳过。选 C-EC和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分支下只写关键词和公式。睡前花五分钟默想这张图比连续刷三小时题的记忆效力还强。考试时哪怕一时卡住脑中浮现这张图也能迅速定位到正确方法。希望这篇博文能帮你少走弯路也欢迎在评论区交流你在图论题上踩过的那些“经典坑”。
阅读完成 · 觉得有帮助？
