数学建模图论习题精解：从算法原理到MATLAB/Python实战

1. 图论习题的价值与本书定位拿到司守奎老师这本《数学建模算法与应用》第二版翻到第四章图论部分很多同学可能和我当初一样心里会犯嘀咕教材里的例题和算法讲解都看懂了但课后习题怎么下手尤其是那些没有标准答案的开放性或综合性习题常常让人感到无从验证学得心里没底。这正是我决定花时间整理和推演这一章习题解答的核心动机。这本书在数学建模圈子里地位相当扎实。它不像一些纯理论的图论教材那样追求数学上的严密和抽象而是紧扣“数学建模”这个应用目标。第四章图论部分从最基础的图、树、最短路到网络流、匹配、着色覆盖了建模竞赛中最常遇到的几类图论模型。它的习题设计非常有层次前一部分是巩固概念和基础算法的手算题中间部分开始需要编程实现主要是MATLAB这也是本书的特色最后则是一些综合性的建模应用题模拟了竞赛中从抽象问题到建立图模型的全过程。因此啃下这些习题绝不仅仅是为了“对答案”。它是一个将书本上静态的算法描述转化为动态问题解决能力的关键训练。通过动手做你才能真正理解Dijkstra算法在处理负权边时的局限体会Floyd算法中那个三重循环的精妙也才能在未来面对“快递网点配送路径优化”、“通信网络可靠性分析”、“人员排班冲突规避”这类实际问题时迅速反应出这背后可能是一个最短路、最小生成树或二分图匹配问题。接下来的内容我将以第二版第四章的习题为纲不仅给出我推演后的参考答案和思路更重要的是分享在求解过程中容易卡壳的“坑点”以及如何将习题与MATLAB或Python作为更通用的补充工具结合把理论落地为代码。我们不会停留在“是什么”而会深入探讨“为什么这么做”以及“怎么想到的”。2. 基础概念与手算题精解这一部分的习题主要检验对图论基本概念的掌握程度包括图的表示、度序列、树的性质、欧拉图与哈密顿图的判定等。虽然以手算为主但却是构建直观理解的基石。2.1 图的表示与度序列问题这类题目通常给出一段关于顶点和边的描述要求画出图或判断某个度序列能否构成图。这里的关键是掌握“握手定理”及其推论无向图中所有顶点的度数之和等于边数的两倍任何图的奇度顶点个数必为偶数。例如一道典型题判断序列 (3,3,3,3,2) 是否能构成一个简单无向图的度序列。思路首先度数之和3333214是偶数满足握手定理。其次需要判断它是否可图化并且是简单图无自环无重边。我们可以用Havel-Hakimi定理来判定。Havel-Hakimi算法实操将序列降序排列(3,3,3,3,2)。取出首元素3将后续的3个元素第2到第4个各减1。得到新序列(3,3,2,1)。注意原序列第5个元素2不变因为它未被选中减去1。对新序列(3,3,2,1)降序排列(3,3,2,1)。取出首元素3将后续的3个元素第2到第4个各减1。得到新序列(2,1,0)。排列(2,1,0)取出2将后续2个元素(1,0)减1得到(0, -1)。出现了负数。结论与踩坑点出现负数说明该序列无法构成简单图。这里一个常见的坑是在应用Havel-Hakimi算法时必须严格执行“取出度数d则将后续d个顶点度数各减1”。如果后续顶点不足d个或者减的过程中出现负数则判定为不可图。很多同学在手工计算时容易在“选中后续哪几个顶点”上出错。对于本题序列(3,3,3,3,2)实际上对应5个顶点每个顶点都想连接3条边但总边数有限必然导致冲突Havel-Hakimi算法将其精确地揭示了出来。2.2 树、最小生成树与Prim/Kruskal算法书中关于树的习题常涉及证明树的性质如边数顶点数-1或对于给定的加权图手工执行Prim或Kruskal算法寻找最小生成树。手工执行Prim算法的心得任选起点选择任意一个顶点作为初始集合U。通常选顶点1但选任何一个结果都一样只是中间过程不同。找最小边每次寻找连接集合U内部顶点与外部顶点V-U的所有边中权值最小的一条。迭代更新将该边及其在V-U中的那个顶点加入集合U。重复直到U包含所有顶点。手工执行Kruskal算法的心得边排序首先将所有边按权值从小到大排序。这是最关键的一步务必仔细手工操作时建议列个表。贪心加边按序检查每条边如果加入这条边不会与已选择的边构成回路即边的两个端点属于当前森林的不同连通分支则选中它。终止条件当选中边的数量达到(顶点数-1)时算法结束。一个易错点在手工进行Kruskal算法时判断“是否构成回路”需要动态地维护连通分量。一个实用的手工技巧是每加入一条边就在图上轻描淡写地连上线并观察这条边的两个端点是否已经在同一个由已选边构成的连通子图里。更系统的方法是心里默记每个顶点所属的“集合”但手工操作时直观看图往往更快前提是图不能太复杂。2.3 欧拉图与哈密顿图判定这部分是概念题的重灾区关键在于牢记充要条件。欧拉图一笔画无向图G是欧拉图存在欧拉回路的充要条件是G连通且没有奇度顶点。存在欧拉通路非回路的充要条件是G连通且恰有2个奇度顶点。哈密顿图没有简单的充要条件常用的是充分条件如Dirac定理顶点数n≥3每个顶点度≥n/2和必要条件若图是哈密顿图则删除任意k个顶点后剩余连通分支数不超过k。解题策略对于欧拉图先检查连通性直观或简单验证再统计各点度数。对于哈密顿图题目通常给一个具体图让你判断。可以先尝试找一条哈密顿回路遍历所有顶点一次且仅一次。如果找不到再尝试用必要条件去否定它比如尝试删除一个度数较小的顶点及其邻居看剩余图是否变得太“破碎”连通分支数过多。个人体会这类判定题在建模中直接应用可能不多但它训练了一种严谨的逻辑思维。特别是在用必要条件否定哈密顿图时你需要像一个侦探一样寻找图的“脆弱点”这种分析思路在后续研究网络可靠性、关键节点识别时非常有帮助。3. 最短路算法从Dijkstra到Floyd的实战深化第四章最短路部分是绝对的重点习题涵盖了Dijkstra算法、Floyd算法及其变种。光看懂算法步骤不够必须通过习题来理解它们的细微差别和适用场景。3.1 Dijkstra算法的正确操作与局限Dijkstra算法用于求解单源非负权最短路。书上的习题通常会给出一个带权图让你手工模拟Dijkstra算法求出从某源点到其他各点的最短距离和路径。手工模拟标准流程初始化设置源点s的距离为0其他点为无穷大。所有顶点未标记。迭代在未标记顶点中选取当前距离最小的顶点u将其标记。松弛检查u的所有邻接点v。如果dist[u] w(u,v) dist[v]则更新dist[v] dist[u] w(u,v)并记录path[v] u。重复步骤2-3直到所有顶点被标记。一个关键提醒Dijkstra算法之所以要求权重非负是因为它基于一个贪心假设一旦一个顶点被标记其最短距离就确定了。如果存在负权边这个假设就不成立因为后续通过负权边可能找到更短的路径。书中习题一般不会出现负权但你必须心里有这根弦。习题常见拓展要求你不仅求出距离还要回溯出最短路径。这需要在算法过程中维护一个predecessor前驱数组。例如在更新dist[v]时同时设置prev[v] u。算法结束后从终点t开始不断查找prev[t],prev[prev[t]]... 直到回溯到源点s逆序即为路径。MATLAB实现要点如果你被要求编写Dijkstra的MATLAB代码核心是高效地实现“选取未标记顶点中距离最小者”。对于小规模图直接遍历查找即可代码直观。对于稍大规模的图可以引入优先队列的思想进行优化。但课本习题级别的图简单实现足矣。重点是你的代码要清晰地体现上述四个步骤特别是“标记”和“松弛”的过程。3.2 Floyd算法的矩阵演绎与路径重建Floyd算法是求解所有顶点对之间最短路的经典算法其思想是动态规划。手工计算时通常采用矩阵迭代的方法非常锻炼耐心和细心。手工计算步骤初始化距离矩阵D和路径矩阵R。D^(0)为图的邻接矩阵无边为Inf自身为0。R^(0)中若i≠j且D(i,j)Inf则R(i,j)i否则为0。进行n轮迭代n为顶点数。第k轮迭代时对于每一对(i, j)检查是否D(i,k) D(k,j) D(i,j)。如果成立则更新D(i,j) D(i,k) D(k,j)并更新R(i,j) R(k,j)。注意R(k,j)记录的是从k到j的路径上j的前驱。这个更新规则是路径重建的精华。迭代完成后D即为所有点对的最短距离矩阵。路径重建方法要找出从i到j的最短路径查看R(i,j)。假设R(i,j)k这意味着路径上到达j之前的一个顶点是k。然后我们再去查找R(i,k)如此递归直到回溯到i。最终路径需要将这个过程逆序输出。Floyd算法习题的坑迭代顺序最外层的循环变量k中介点必须作为第一层循环这是动态规划“阶段”的体现。手工计算时我们就是一列一列、一行一行地固定k去更新整个矩阵。无穷大(Inf)的处理在比较D(i,k) D(k,j) D(i,j)时如果D(i,k)或D(k,j)是Inf它们的和也是Inf不会小于任何有限值因此无需更新。编程时要注意Inf的运算规则。路径矩阵R的初始化与更新这是很多同学忽略的地方。正确的路径记录是还原具体路径的唯一方法。仅仅算出最短距离是不够的。个人经验手工演算一个4x4或5x5的Floyd矩阵对于理解动态规划“逐步允许更多顶点作为中转”的思想至关重要。你会发现当k遍历所有顶点后相当于考虑了所有可能的路径组合。这个算法虽然时间复杂度是O(n^3)但对于顶点数不多几百以内的稠密图或者需要一次性求出所有点对距离的场景它代码极其简洁是很好的选择。4. 网络流、匹配与着色问题的建模转换这一部分的习题开始具有更强的建模色彩往往需要你先将一个实际问题抽象成图论模型网络流、二分图匹配、着色等然后再求解。4.1 最大流问题与最小割最大流问题通常涉及“运输能力”、“数据传输量”等。习题可能会给你一个网络让你用Ford-Fulkerson方法或更具体的Edmonds-Karp算法即BFS寻找增广路求最大流。手工求解最大流增广路法流程初始流量为0。在残量网络中寻找一条从源点s到汇点t的增广路径路径上每条边的剩余容量0。找到该路径上的最小剩余容量瓶颈容量将其加到总流量上。沿着增广路径更新每条边的剩余容量正向边减少反向边增加。反向边的增加是为后续“反悔”提供可能这是算法正确的关键。重复步骤2-4直到找不到增广路径为止。最小割的求解根据最大流最小割定理最大流的值等于最小割的容量。在算法结束后在最后的残量网络中从源点s出发沿着剩余容量0的边能到达的所有顶点构成集合S剩下的顶点构成集合T。从S指向T的原始边的容量之和即为最小割的容量。建模关键如何定义“顶点”和“边”源点和汇点是什么边的容量如何确定例如一个“多个工厂向多个仓库送货”的问题工厂和仓库都可以作为顶点但中间可能还需要引入“中转点”。边的容量就是运输路线的最大运力。这类习题锻炼的正是这种抽象能力。4.2 二分图匹配与匈牙利算法二分图匹配问题广泛存在于任务分配、人员调度中。匈牙利算法是求解最大匹配的经典方法。匈牙利算法手工操作针对二分图左部顶点初始匹配为空。从左部一个未匹配点u开始尝试为其寻找匹配。寻找过程是一个DFS/BFS的“交替路径”搜索从u出发走未匹配边到右部再走匹配边回左部再走未匹配边到右部……直到找到一个右部的未匹配点v。找到这样一条路径后进行“增广”将路径上的所有边状态取反未匹配变匹配匹配变未匹配。这样匹配数就增加了1。重复步骤2-3直到左部所有点都尝试过且无法找到新的增广路径。算法核心与难点理解“交替路径”和“增广”是掌握匈牙利算法的关键。在手工计算时最好在图上用两种颜色或线型实线/虚线清晰标出当前的匹配边和非匹配边。为每个左部点寻找增广路时要系统地尝试其所有邻接点并记录哪些右部点已经被本次搜索访问过避免重复和死循环。从问题到二分图如何判断一个问题是否是二分图匹配关键在于“两类对象”和“一对一的关系”。例如“工作”和“工人”、“课程”和“教室”、“求婚者”和“被求婚者”。如果问题中一个工人只能做一项工作一项工作只能由一个工人完成这就构成了匹配。建模时将一类对象作为左部顶点另一类作为右部顶点如果两者之间存在可能的关系就连一条边。4.3 图的着色与排课表问题图的着色特别是顶点着色对应着著名的排课表、寄存器分配等问题。其目标是使用最少的颜色给顶点着色使得相邻顶点颜色不同。贪心着色算法将顶点按某种顺序排列如度数从大到小。取第一种颜色尝试给第一个顶点着色。对于后续每个顶点检查其所有邻接点已使用的颜色选择编号最小的、未被邻接点使用的颜色为其着色。如果现有颜色都不满足则引入一种新颜色。习题常见类型求色数通常需要你给出一个着色方案并论证为什么不能用更少的颜色。论证往往需要用到图的结构特性比如找到图中的一个团完全子图其大小就是色数的一个下界。建模为着色问题例如有若干门课程一些课程不能在同一时间上课因为有共同的学生问最少需要多少个时间段。这里每门课是一个顶点如果两门课冲突就在它们之间连一条边。所需的最少时间段数就是图的色数。经验之谈贪心算法不一定能得到最优解最少颜色数但通常能得到一个不错的近似解。对于习题中的小图可以尝试手工穷举或者基于观察来寻找最优着色。一个有用的技巧是先给度数最高的顶点及其邻居着色这样更容易发现颜色的冲突和节省颜色的机会。5. 综合应用题从现实问题到图论模型的构建这是第四章习题中最具挑战性也最有价值的部分。它不再提供现成的图而是描述一个实际场景需要你自主地定义顶点、边、权重构建出一个图论模型并选择合适的算法求解。5.1 问题一乡村公路升级规划问题描述简化某地区有n个村庄现有一些土路连接它们。政府希望投资将部分土路升级为水泥路使得任意两个村庄之间都有一条水泥路连通可以间接连通并且希望总投资最小。已知升级每条土路所需的费用。模型构建与求解顶点每个村庄。边现有的每一条土路。边权升级该土路所需的费用。问题转化在给定的图中选择一个边集使得图连通确保任意两村可达且边集的权重之和最小。同时这个边集必须是无环的如果有环可以去掉环上最贵的一条边仍然连通且总价更小。模型识别这正是一个经典的最小生成树MST问题。算法选择由于是加权无向图直接使用Prim或Kruskal算法求解即可。结果就是需要升级的那些土路集合以及总费用。思考延伸如果问题变成“在预算有限的情况下如何升级道路使得连通村庄尽可能多”这就变成了一个带约束的优化问题可能需要对MST算法进行改进或使用其他启发式方法。但原题是标准的MST应用。5.2 问题二紧急物资配送问题描述简化灾区有多个救援点一个中央仓库。需要从仓库向每个救援点配送一批紧急物资。不同道路的运输时间不同且每条道路在同一时间只能允许一辆车通行不考虑车辆速度差异。希望找到一种配送方案使得最后一个救援点收到物资的时间尽可能早。模型构建与求解顶点中央仓库和各个救援点。边连接它们的所有道路。边权运输时间。问题转化这不再是求仓库到各点的最短路之和最小而是要求仓库到所有救援点的最短路中最长的那一条即最大距离最小化。因为最后一辆车到达的时间取决于距离仓库最远的那个救援点的距离。模型识别这是一个最小化最大距离问题也称为“中心点”问题的一种形式。但在这个特定场景下单源最小化最远距离它等价于求从仓库出发到所有救援点的最短路然后取其中的最大值。我们需要的是这个最大值最小但仓库位置是固定的所以我们需要计算的就是从固定仓库出发的最短路中的最大值。关键点辨析注意这里不是“图的中心”使得到所有顶点最大距离最小的顶点。因为仓库位置固定。所以算法很直接步骤1以中央仓库为源点运行一次Dijkstra算法所有边权为正求出仓库到每个救援点的最短时间。步骤2在所有求出的最短时间中找出最大值。这个最大值就是完成所有配送所需的最短时间假设有足够多的车辆同时从仓库出发走各自的最短路径。结果解读这个最大值对应的路径就是制约整体配送时间的“关键路径”。为了进一步缩短总时间可能需要考虑增派资源改善这条关键路径或者在建模时引入更多的现实约束如车辆数有限。5.3 问题三项目任务调度与关键路径问题描述简化一个项目由多个任务组成。某些任务必须在其他任务完成后才能开始。每个任务有预计耗时。问完成整个项目至少需要多少时间哪些任务的延迟会直接影响总工期模型构建与求解顶点有两种建模方式。方式A顶点表示任务需要引入“虚任务”和边来表示依赖关系比较复杂。方式B顶点表示事件更常用。每个事件代表一个或多个任务的开始或结束。我们通常增加一个“开始”事件和一个“结束”事件。边表示任务。边从该任务的开始事件指向结束事件。边权任务的耗时。问题转化我们需要找到从“开始”事件到“结束”事件的最长路径。因为在有向无环图DAG根据任务依赖关系构建的图一定是DAG中只有所有前置路径上的任务都完成了后续任务才能开始所以总工期是由最长的路径决定的。模型识别这是一个在有向无环图DAG上求最长路径的问题即关键路径法CPM。算法求解首先对图的顶点进行拓扑排序。设earliest[v]为事件v的最早发生时间。初始化earliest[start]0。按照拓扑顺序遍历每个顶点u对于其每条出边(u, v, w)执行earliest[v] max(earliest[v], earliest[u] w)。最终earliest[end]就是项目的最短总工期。求关键路径与关键任务反向计算latest[v]事件v的最晚发生时间不影响总工期。对于一条边(u, v, w)表示的任务其总浮动时间为latest[v] - earliest[u] - w。总浮动时间为0的任务就是关键任务它们组成的从start到end的路径就是关键路径。注意事项建模时要确保依赖关系被正确表示为有向边。对于“任务A和B都完成后C才能开始”这样的情况需要引入事件节点来清晰表达。通过这三个综合例题我们可以看到将实际问题转化为图论模型最关键的一步是识别问题的本质特征是连通性问题、最优化问题、分配问题还是排序问题然后根据特征定义合适的图元素顶点、边、权最后调用相应的图论算法。司老师书中的这些习题正是为了训练我们这种“建模思维”而设置的。