1. 项目概述从实际问题到图论模型的桥梁当我们面对城市公交线路规划、通信网络光纤铺设、甚至是社交媒体上的好友推荐时表面上看是千差万别的领域问题但内核往往可以抽象成同一类数学模型——图与网络模型。上一部分我们探讨了图的基本概念和表示方法算是拿到了进入这个领域的“地图”。而这一部分我们将深入腹地聚焦于几个在数学建模竞赛和实际工程中出场率极高的核心问题最小生成树、着色问题和最大流问题。这些不是枯燥的理论而是解决“如何用最低成本连接所有村庄”、“如何安排考场避免冲突”、“如何最大化物流网络的运输效率”等实际问题的锋利工具。掌握它们意味着你能将一团乱麻的现实约束转化为清晰可解的数学命题。2. 核心算法原理与策略选择2.1 最小生成树寻找最优连接骨架最小生成树Minimum Spanning Tree, MST要解决的是在一个加权连通图中找出一棵包含所有顶点且所有边的权重之和最小的树。这棵树就是整个网络的“成本最优骨干网”。两个最经典的算法是Prim算法和Kruskal算法它们策略不同但殊途同归。Prim算法“加点法”的核心思想是从一个根节点开始像生长一棵树一样逐步扩张。它维护两个集合已加入生成树的顶点集合U和未加入的顶点集合V-U。每一步它都从连接U和V-U的所有边中挑选一条权重最小的边(u, v)其中u在U中v不在然后将顶点v和边(u, v)加入生成树。这个过程直到所有顶点都被包含进来为止。Prim算法非常适合于边比较稠密的图因为它需要频繁地查找和比较与当前树集相邻的边。它的时间复杂度为O(|V|²)使用优先队列如斐波那契堆优化后可达到O(|E| |V| log|V|)。实操心得在编程实现Prim算法时维护一个lowcost数组来记录各顶点到当前生成树的最小距离以及一个closest数组记录这个最小距离对应的树内顶点可以避免每次都扫描所有边是常见的优化手段。Kruskal算法“加边法”则采用了不同的思路它直接将所有边按权重从小到大排序然后按顺序检查每一条边。如果加入当前边不会与已选择的边构成环即边的两个端点不属于同一个连通分量那么就加入这条边否则就跳过。这个过程一直持续到已选择的边数达到|V| - 1为止。判断是否成环高效的数据结构是并查集。Kruskal算法在边数相对较少稀疏图时效率很高其时间复杂度主要花在排序上为O(|E| log|E|)。策略选择对比特性维度Prim算法Kruskal算法核心思想从点出发逐步扩张生成树从边出发按权值从小到大尝试加入数据结构优先队列、邻接矩阵/表并查集、边集数组需排序时间复杂度O(V适用场景边稠密图E建模联想类似于从一个中心点如数据中心开始建设网络类似于有现成的道路清单从中挑选最经济的来连接地区在实际建模中选择哪种算法往往取决于数据的存储形式。如果给你的数据是邻接矩阵Prim算法实现起来更直接如果给的是边列表Kruskal算法就更自然。2.2 着色问题冲突规避的艺术图着色问题特别是顶点着色研究的是如何用最少的颜色给图的每个顶点染色使得任何一条边两端的顶点颜色都不相同。这个“最少颜色数”称为图的色数。这听起来像是个游戏但其应用场景极其广泛安排考试时间同一学生参加的多门考试不能在同一时间考试是顶点冲突是边颜色是时间槽、分配寄存器变量是顶点同时活跃的变量冲突颜色是寄存器、分配无线电信道基站是顶点干扰是边颜色是频道等等。着色问题本身是NP-hard的这意味着没有已知的多项式时间算法能对所有图求出精确的色数。因此在实际建模中我们主要依赖启发式算法来寻找一个可接受的、但不一定是最优的解。贪心着色算法是最简单直接的策略顺序遍历所有顶点对当前顶点赋予其邻接顶点中未使用过的最小颜色编号。这个算法的结果严重依赖于顶点的遍历顺序。一个常见的改进是DSatur算法它不再按固定顺序而是在每一步都选择“饱和度”最高的顶点进行着色。一个顶点的饱和度定义为其邻接顶点中已使用的不同颜色数。DSatur算法通常能得到比简单贪心算法更好的结果。建模应用要点当你把一个问题抽象成着色模型时关键在于准确定义什么是“顶点”什么是“边”即冲突关系。例如在考试安排中如果两位老师要求他们监考的考场不能相邻这又增加了一层约束可能就需要建立更复杂的图模型如边着色或列表着色。着色问题在建模论文中不仅要给出着色方案更要通过理论分析如利用图的最大团大小给出色数的下界和算法结果对比来论证方案的优越性。2.3 最大流问题网络输送能力的极限最大流问题考虑的是一个有向的流量网络有一个源点s如水库一个汇点t如城市以及若干中间节点如中转站。每条边有容量限制表示该管道单位时间内能通过的最大流量。问题是如何安排每条边上的实际流量使得从s到t的总流量达到最大同时满足容量限制和流量守恒除源点和汇点外流入每个节点的流量等于流出量。Ford-Fulkerson方法是解决最大流问题的基础框架其核心是“增广路径”思想。算法不断寻找一条从源点到汇点的路径使得路径上的每条边都有剩余的容量即容量减去当前流量大于0。然后沿着这条路径尽可能多地增加流量。为了纠正之前可能做出的次优流量分配该方法引入了一个关键概念残余网络。在残余网络中对于原图中的每条边(u, v)如果当前流量f c容量则添加一条正向边(u, v)剩余容量为c - f同时添加一条反向边(v, u)容量为f。这条反向边代表了“可以回退流量”的能力。Edmonds-Karp算法是Ford-Fulkerson方法的一个具体实现它规定每次都用广度优先搜索BFS来寻找最短的增广路径以边数为度量。这个简单的规定带来了质的变化它将算法的时间复杂度限定在了O(|V| * |E|²)使其成为一个多项式时间算法并且在实际中通常表现良好。最大流最小割定理是这个领域最优美和重要的定理之一。它指出在一个流量网络中从源点到汇点的最大流量值等于将所有顶点分成包含源点和不包含源点两部分后所有从源点部分指向汇点部分的边的容量之和的最小值。这个最小值就称为“最小割”。这一定理不仅提供了最大流值的理论上限也为算法正确性提供了保证同时“割”的概念在分析网络脆弱性哪些管道最关键时非常有用。3. 建模实战从问题抽象到算法实现3.1 场景一乡村公路升级规划最小生成树应用假设某县有n个偏远村庄政府希望铺设光纤网络或升级公路使所有村庄都能连通。已知在任意两个村庄i和j之间直接铺设线路的成本为w(i, j)。目标是找到总成本最低的建设方案。第一步模型抽象。这是最小生成树的经典应用。每个村庄是图的一个顶点任意两村庄之间都有一条边边的权重就是建设成本w(i, j)。由于可以在任意两村间直接建设这是一个完全图。我们的目标是找出该完全图的一棵最小生成树。第二步算法选择与实现。村庄数量n可能成百上千边数约为n²量级属于稠密图。因此使用Prim算法更为合适。我们可以用邻接矩阵来存储成本数据。第三步实现细节与优化。朴素的Prim算法需要O(n²)的时间对于n1000的数据量完全可接受。关键步骤是初始化一个数组lowcost记录各点到当前生成树的最小距离。每次从lowcost中选出最小值对应的顶点加入树中并更新其他顶点的lowcost值。def prim_mst(n, cost_matrix): cost_matrix: n x n 的邻接矩阵cost_matrix[i][i]0, 无边用无穷大表示。 返回最小生成树的总权重。 INF float(inf) lowcost [INF] * n # 各顶点到当前MST的最小距离 closest [-1] * n # 对应最小距离的MST内顶点 visited [False] * n # 从顶点0开始 lowcost[0] 0 total_weight 0 for _ in range(n): # 寻找未访问顶点中lowcost最小的 u -1 min_val INF for i in range(n): if not visited[i] and lowcost[i] min_val: min_val lowcost[i] u i if u -1: # 图不连通 break visited[u] True total_weight min_val # 更新其他顶点到新MST的距离 for v in range(n): if not visited[v] and cost_matrix[u][v] lowcost[v]: lowcost[v] cost_matrix[u][v] closest[v] u return total_weight第四步结果解释与扩展。算法输出的总权重就是最低成本。closest数组记录了树的形状即每个村庄除第一个是通过连接到哪个村庄被纳入网络的。在实际报告中除了给出总成本还应输出具体的建设方案边列表。如果某些村庄之间由于地形原因无法直接建设成本视为无穷大只要图仍然是连通的算法依然有效。3.2 场景二期末考试考场安排着色问题应用某大学需在3天内安排所有课程的期末考试。已知每门课程的学生选课名单规定同一名学生不能在同一时间参加两门考试。要求找出一个所需考试时间段最少的安排方案。第一步模型抽象。每门课程作为一个顶点。如果两门课程有共同的学生选修则在它们之间连一条边表示这两门考试时间必须错开。这样我们就得到了一个冲突图。给顶点着色颜色代表考试时间段。问题转化为求该冲突图的顶点着色并希望使用颜色数时间段尽可能少。第二步算法选择与实现。由于求精确色数很难我们采用启发式算法。DSatur算法通常能取得不错的效果。我们需要维护每个顶点的饱和度、未着色邻居数等信息。第三步实现流程。初始化所有顶点未着色计算每个顶点的邻居集合。选择饱和度最高的未着色顶点。若饱和度相同则选择度邻居数最大的。给该顶点分配其邻居中未使用的最小颜色编号。更新所有未着色邻居的饱和度如果新颜色是邻居之前没见过的颜色则其饱和度1。重复步骤2-4直到所有顶点着色完毕。def dsatur_coloring(adj_list): adj_list: 图的邻接表表示顶点编号从0开始。 返回一个列表其中result[i]表示顶点i的颜色编号从0开始。 n len(adj_list) color [-1] * n saturation [0] * n # 饱和度邻接点中不同颜色的数量 uncolored set(range(n)) while uncolored: # 选择饱和度最高的未着色顶点平局时选度大的 max_sat -1 selected -1 for v in uncolored: if saturation[v] max_sat or (saturation[v] max_sat and len(adj_list[v]) len(adj_list[selected])): max_sat saturation[v] selected v # 找到selected的邻居中未使用的最小颜色 used_colors set(color[nei] for nei in adj_list[selected] if color[nei] ! -1) c 0 while c in used_colors: c 1 color[selected] c uncolored.remove(selected) # 更新未着色邻居的饱和度 for nei in adj_list[selected]: if color[nei] -1: # 检查c是否对nei来说是新的颜色 neighbor_colors set(color[nn] for nn in adj_list[nei] if color[nn] ! -1) if c not in neighbor_colors: saturation[nei] 1 return color第四步分析与优化。算法结束后max(color) 1就是所需的最少时间段数的一个上界。我们可以通过调整顶点选择策略如尝试不同的初始顶点顺序进行多次运行取最好的结果。在论文中可以计算冲突图的最大团大小作为所需时间段数的理论下界从而评估算法解的质量。3.3 场景三城市供水网络优化最大流应用某城市供水网络如图水源地为S水厂为T中间有多个泵站和管道每条管道有最大流量限制单位万吨/天。现需评估该网络的最大供水能力并找出制约供水能力的瓶颈管道。第一步模型抽象。将水源地、水厂、泵站抽象为顶点管道抽象为有向边管道容量作为边容量。这直接形成了一个标准的单源单汇流量网络。目标是求解从S到T的最大流。第二步算法选择与实现。采用实现相对简单且效率稳定的Edmonds-Karp算法BFS寻找增广路。第三步实现细节。关键在于构建和更新残余网络。我们可以用一个邻接表来存储边的容量和流量信息每条边对应一个正向边和一个反向边对象。from collections import deque class Edge: def __init__(self, to, cap, rev): self.to to # 边的终点 self.cap cap # 剩余容量 self.rev rev # 反向边在邻接表中的索引 def add_edge(graph, fr, to, cap): 添加一条从fr到to容量为cap的边及其反向边 graph[fr].append(Edge(to, cap, len(graph[to]))) graph[to].append(Edge(fr, 0, len(graph[fr]) - 1)) # 反向边初始容量为0 def edmonds_karp(graph, s, t): n len(graph) flow 0 INF 10**9 while True: # BFS寻找增广路 prevv [-1] * n # 前驱顶点 preve [-1] * n # 前驱边索引 q deque([s]) while q: v q.popleft() for i, e in enumerate(graph[v]): if e.cap 0 and prevv[e.to] -1 and e.to ! s: prevv[e.to] v preve[e.to] i if e.to t: break q.append(e.to) if prevv[t] ! -1: break if prevv[t] -1: # 没有增广路了 break # 计算本次增广的流量 d INF v t while v ! s: e graph[prevv[v]][preve[v]] d min(d, e.cap) v prevv[v] # 更新残余网络 v t while v ! s: e graph[prevv[v]][preve[v]] e.cap - d graph[v][e.rev].cap d # 反向边容量增加 v prevv[v] flow d return flow第四步结果解释与瓶颈分析。算法返回的flow即为最大供水能力。根据最大流最小割定理算法结束后在残余网络中从源点S出发能到达的顶点集合记为S_set不能到达的集合记为T_set。那么所有从S_set指向T_set的原始边就构成了一个“最小割”这些边的容量之和等于最大流。这些边就是网络的瓶颈它们的容量限制了总流量的提升。在报告中除了给出最大流量重点应分析这个最小割集指出哪些管道是扩容的关键为决策提供直接依据。4. 进阶技巧、常见陷阱与性能考量4.1 算法变体与扩展模型最小生成树的扩展次小生成树在建模中有时需要备用方案。次小生成树是权值和第二小的生成树。一个高效算法是先求出最小生成树T然后枚举不在T中的每条边(u, v)将其加入T会形成一个环去掉这个环中除(u, v)外权值最大的边得到一棵新树。所有新树中权值最小的就是次小生成树。这需要预处理树上任意两点间路径的最大边权可用倍增法LCA实现。度限制生成树例如在网络设计中一个路由器的端口数有限即生成树中某个顶点的度不能超过k。这是一个NP难问题常用遗传算法、模拟退火等元启发式算法求解。着色问题的扩展边着色给边着色使共用一个顶点的边颜色不同。这可以建模任务调度问题其中任务边需要资源顶点共享资源的任务不能同时进行。列表着色每个顶点有一个可用的颜色列表只能从列表中选择颜色。这增加了约束更贴近实际如某些课程只能在特定时间上。最大流问题的扩展多源多汇可以添加一个超级源点连接所有源点一个超级汇点连接所有汇点转化为单源单汇问题。顶点有容量可以将一个顶点v拆分成两个顶点v_in和v_out中间连一条容量等于该顶点容量的边所有进入v的边改为进入v_in所有从v出去的边改为从v_out出去。最小费用最大流每条边不仅有容量还有单位流量的费用。在求最大流的同时要求总费用最小。这需要在增广时总是寻找费用最小的增广路通常使用SPFA或Bellman-Ford算法。4.2 常见问题与调试技巧图不连通导致算法失败Prim和Kruskal算法都要求图是连通的。在数据处理后务必检查图的连通性用DFS/BFS。对于Kruskal如果最终选出的边数少于|V|-1则说明图不连通。负权边的影响最小生成树算法通常假设边权非负。如果存在负权边Prim和Kruskal算法依然有效因为它们基于贪心选择最小边。但如果有负权环则最小生成树定义可能变得复杂总权值可以无限小通常实际问题中不会出现。最大流算法陷入死循环或效率极低这是朴素Ford-Fulkerson方法使用DFS时可能遇到的问题如果容量是无理数或算法选择增广路不当可能无法终止。务必使用Edmonds-KarpBFS或Dinic等多项式时间算法。数据结构选择不当导致超时对于稀疏图|E| |V|²使用邻接表而非邻接矩阵。Kruskal算法中并查集的“路径压缩”和“按秩合并”优化至关重要。Prim算法在稠密图中用普通数组即可在稀疏图中应使用优先队列。着色结果不理想贪心类着色算法的结果依赖于顶点顺序。可以尝试多种顺序按度降序、按度升序、随机顺序等取最好的结果。对于DSatur算法在饱和度相同时选择策略如选度最大的也会影响结果可以微调。4.3 数学建模竞赛中的呈现要点在竞赛论文中不能只贴代码和结果需要完整呈现建模过程问题重述与分析用你自己的话清晰定义问题并指出其属于图论的哪一类问题。模型假设与符号说明明确列出你的假设如“所有管道流量方向可逆”并定义文中使用的所有数学符号。模型建立这是核心。详细阐述如何将实际问题抽象为图模型顶点是什么边是什么权重/容量如何定义目标函数是什么算法设计与求解说明你选择特定算法的理由如“由于该图是稠密图我们采用Prim算法”。给出算法的步骤描述或伪代码并分析其复杂度。如果是启发式算法说明其合理性。结果分析与检验可视化将生成的树、着色方案、流量分配用图形直观展示。敏感性分析改变某个参数如某条路的成本观察结果如何变化。模型检验用特例小规模数据手工验证用理论下界如着色数不小于最大团大小评估解的质量与其他算法结果对比。瓶颈与改进分析模型的局限性如未考虑某些现实因素并提出可能的改进方向。模型评价与推广总结模型的优缺点并讨论其可应用于其他哪些类似场景。记住图论模型的价值在于其强大的抽象能力。当你面对一个看似复杂的新问题时不妨思考它的核心元素和关系能否抽象成点和边权重代表什么目标是连接、染色还是输送一旦完成这个抽象你就拥有了一个强大的工具箱可以从中选取合适的算法来寻找答案。这个过程本身就是数学建模最迷人的地方。 图论建模实战：最小生成树、着色与最大流算法原理与应用
1. 项目概述从实际问题到图论模型的桥梁当我们面对城市公交线路规划、通信网络光纤铺设、甚至是社交媒体上的好友推荐时表面上看是千差万别的领域问题但内核往往可以抽象成同一类数学模型——图与网络模型。上一部分我们探讨了图的基本概念和表示方法算是拿到了进入这个领域的“地图”。而这一部分我们将深入腹地聚焦于几个在数学建模竞赛和实际工程中出场率极高的核心问题最小生成树、着色问题和最大流问题。这些不是枯燥的理论而是解决“如何用最低成本连接所有村庄”、“如何安排考场避免冲突”、“如何最大化物流网络的运输效率”等实际问题的锋利工具。掌握它们意味着你能将一团乱麻的现实约束转化为清晰可解的数学命题。2. 核心算法原理与策略选择2.1 最小生成树寻找最优连接骨架最小生成树Minimum Spanning Tree, MST要解决的是在一个加权连通图中找出一棵包含所有顶点且所有边的权重之和最小的树。这棵树就是整个网络的“成本最优骨干网”。两个最经典的算法是Prim算法和Kruskal算法它们策略不同但殊途同归。Prim算法“加点法”的核心思想是从一个根节点开始像生长一棵树一样逐步扩张。它维护两个集合已加入生成树的顶点集合U和未加入的顶点集合V-U。每一步它都从连接U和V-U的所有边中挑选一条权重最小的边(u, v)其中u在U中v不在然后将顶点v和边(u, v)加入生成树。这个过程直到所有顶点都被包含进来为止。Prim算法非常适合于边比较稠密的图因为它需要频繁地查找和比较与当前树集相邻的边。它的时间复杂度为O(|V|²)使用优先队列如斐波那契堆优化后可达到O(|E| |V| log|V|)。实操心得在编程实现Prim算法时维护一个lowcost数组来记录各顶点到当前生成树的最小距离以及一个closest数组记录这个最小距离对应的树内顶点可以避免每次都扫描所有边是常见的优化手段。Kruskal算法“加边法”则采用了不同的思路它直接将所有边按权重从小到大排序然后按顺序检查每一条边。如果加入当前边不会与已选择的边构成环即边的两个端点不属于同一个连通分量那么就加入这条边否则就跳过。这个过程一直持续到已选择的边数达到|V| - 1为止。判断是否成环高效的数据结构是并查集。Kruskal算法在边数相对较少稀疏图时效率很高其时间复杂度主要花在排序上为O(|E| log|E|)。策略选择对比特性维度Prim算法Kruskal算法核心思想从点出发逐步扩张生成树从边出发按权值从小到大尝试加入数据结构优先队列、邻接矩阵/表并查集、边集数组需排序时间复杂度O(V适用场景边稠密图E建模联想类似于从一个中心点如数据中心开始建设网络类似于有现成的道路清单从中挑选最经济的来连接地区在实际建模中选择哪种算法往往取决于数据的存储形式。如果给你的数据是邻接矩阵Prim算法实现起来更直接如果给的是边列表Kruskal算法就更自然。2.2 着色问题冲突规避的艺术图着色问题特别是顶点着色研究的是如何用最少的颜色给图的每个顶点染色使得任何一条边两端的顶点颜色都不相同。这个“最少颜色数”称为图的色数。这听起来像是个游戏但其应用场景极其广泛安排考试时间同一学生参加的多门考试不能在同一时间考试是顶点冲突是边颜色是时间槽、分配寄存器变量是顶点同时活跃的变量冲突颜色是寄存器、分配无线电信道基站是顶点干扰是边颜色是频道等等。着色问题本身是NP-hard的这意味着没有已知的多项式时间算法能对所有图求出精确的色数。因此在实际建模中我们主要依赖启发式算法来寻找一个可接受的、但不一定是最优的解。贪心着色算法是最简单直接的策略顺序遍历所有顶点对当前顶点赋予其邻接顶点中未使用过的最小颜色编号。这个算法的结果严重依赖于顶点的遍历顺序。一个常见的改进是DSatur算法它不再按固定顺序而是在每一步都选择“饱和度”最高的顶点进行着色。一个顶点的饱和度定义为其邻接顶点中已使用的不同颜色数。DSatur算法通常能得到比简单贪心算法更好的结果。建模应用要点当你把一个问题抽象成着色模型时关键在于准确定义什么是“顶点”什么是“边”即冲突关系。例如在考试安排中如果两位老师要求他们监考的考场不能相邻这又增加了一层约束可能就需要建立更复杂的图模型如边着色或列表着色。着色问题在建模论文中不仅要给出着色方案更要通过理论分析如利用图的最大团大小给出色数的下界和算法结果对比来论证方案的优越性。2.3 最大流问题网络输送能力的极限最大流问题考虑的是一个有向的流量网络有一个源点s如水库一个汇点t如城市以及若干中间节点如中转站。每条边有容量限制表示该管道单位时间内能通过的最大流量。问题是如何安排每条边上的实际流量使得从s到t的总流量达到最大同时满足容量限制和流量守恒除源点和汇点外流入每个节点的流量等于流出量。Ford-Fulkerson方法是解决最大流问题的基础框架其核心是“增广路径”思想。算法不断寻找一条从源点到汇点的路径使得路径上的每条边都有剩余的容量即容量减去当前流量大于0。然后沿着这条路径尽可能多地增加流量。为了纠正之前可能做出的次优流量分配该方法引入了一个关键概念残余网络。在残余网络中对于原图中的每条边(u, v)如果当前流量f c容量则添加一条正向边(u, v)剩余容量为c - f同时添加一条反向边(v, u)容量为f。这条反向边代表了“可以回退流量”的能力。Edmonds-Karp算法是Ford-Fulkerson方法的一个具体实现它规定每次都用广度优先搜索BFS来寻找最短的增广路径以边数为度量。这个简单的规定带来了质的变化它将算法的时间复杂度限定在了O(|V| * |E|²)使其成为一个多项式时间算法并且在实际中通常表现良好。最大流最小割定理是这个领域最优美和重要的定理之一。它指出在一个流量网络中从源点到汇点的最大流量值等于将所有顶点分成包含源点和不包含源点两部分后所有从源点部分指向汇点部分的边的容量之和的最小值。这个最小值就称为“最小割”。这一定理不仅提供了最大流值的理论上限也为算法正确性提供了保证同时“割”的概念在分析网络脆弱性哪些管道最关键时非常有用。3. 建模实战从问题抽象到算法实现3.1 场景一乡村公路升级规划最小生成树应用假设某县有n个偏远村庄政府希望铺设光纤网络或升级公路使所有村庄都能连通。已知在任意两个村庄i和j之间直接铺设线路的成本为w(i, j)。目标是找到总成本最低的建设方案。第一步模型抽象。这是最小生成树的经典应用。每个村庄是图的一个顶点任意两村庄之间都有一条边边的权重就是建设成本w(i, j)。由于可以在任意两村间直接建设这是一个完全图。我们的目标是找出该完全图的一棵最小生成树。第二步算法选择与实现。村庄数量n可能成百上千边数约为n²量级属于稠密图。因此使用Prim算法更为合适。我们可以用邻接矩阵来存储成本数据。第三步实现细节与优化。朴素的Prim算法需要O(n²)的时间对于n1000的数据量完全可接受。关键步骤是初始化一个数组lowcost记录各点到当前生成树的最小距离。每次从lowcost中选出最小值对应的顶点加入树中并更新其他顶点的lowcost值。def prim_mst(n, cost_matrix): cost_matrix: n x n 的邻接矩阵cost_matrix[i][i]0, 无边用无穷大表示。 返回最小生成树的总权重。 INF float(inf) lowcost [INF] * n # 各顶点到当前MST的最小距离 closest [-1] * n # 对应最小距离的MST内顶点 visited [False] * n # 从顶点0开始 lowcost[0] 0 total_weight 0 for _ in range(n): # 寻找未访问顶点中lowcost最小的 u -1 min_val INF for i in range(n): if not visited[i] and lowcost[i] min_val: min_val lowcost[i] u i if u -1: # 图不连通 break visited[u] True total_weight min_val # 更新其他顶点到新MST的距离 for v in range(n): if not visited[v] and cost_matrix[u][v] lowcost[v]: lowcost[v] cost_matrix[u][v] closest[v] u return total_weight第四步结果解释与扩展。算法输出的总权重就是最低成本。closest数组记录了树的形状即每个村庄除第一个是通过连接到哪个村庄被纳入网络的。在实际报告中除了给出总成本还应输出具体的建设方案边列表。如果某些村庄之间由于地形原因无法直接建设成本视为无穷大只要图仍然是连通的算法依然有效。3.2 场景二期末考试考场安排着色问题应用某大学需在3天内安排所有课程的期末考试。已知每门课程的学生选课名单规定同一名学生不能在同一时间参加两门考试。要求找出一个所需考试时间段最少的安排方案。第一步模型抽象。每门课程作为一个顶点。如果两门课程有共同的学生选修则在它们之间连一条边表示这两门考试时间必须错开。这样我们就得到了一个冲突图。给顶点着色颜色代表考试时间段。问题转化为求该冲突图的顶点着色并希望使用颜色数时间段尽可能少。第二步算法选择与实现。由于求精确色数很难我们采用启发式算法。DSatur算法通常能取得不错的效果。我们需要维护每个顶点的饱和度、未着色邻居数等信息。第三步实现流程。初始化所有顶点未着色计算每个顶点的邻居集合。选择饱和度最高的未着色顶点。若饱和度相同则选择度邻居数最大的。给该顶点分配其邻居中未使用的最小颜色编号。更新所有未着色邻居的饱和度如果新颜色是邻居之前没见过的颜色则其饱和度1。重复步骤2-4直到所有顶点着色完毕。def dsatur_coloring(adj_list): adj_list: 图的邻接表表示顶点编号从0开始。 返回一个列表其中result[i]表示顶点i的颜色编号从0开始。 n len(adj_list) color [-1] * n saturation [0] * n # 饱和度邻接点中不同颜色的数量 uncolored set(range(n)) while uncolored: # 选择饱和度最高的未着色顶点平局时选度大的 max_sat -1 selected -1 for v in uncolored: if saturation[v] max_sat or (saturation[v] max_sat and len(adj_list[v]) len(adj_list[selected])): max_sat saturation[v] selected v # 找到selected的邻居中未使用的最小颜色 used_colors set(color[nei] for nei in adj_list[selected] if color[nei] ! -1) c 0 while c in used_colors: c 1 color[selected] c uncolored.remove(selected) # 更新未着色邻居的饱和度 for nei in adj_list[selected]: if color[nei] -1: # 检查c是否对nei来说是新的颜色 neighbor_colors set(color[nn] for nn in adj_list[nei] if color[nn] ! -1) if c not in neighbor_colors: saturation[nei] 1 return color第四步分析与优化。算法结束后max(color) 1就是所需的最少时间段数的一个上界。我们可以通过调整顶点选择策略如尝试不同的初始顶点顺序进行多次运行取最好的结果。在论文中可以计算冲突图的最大团大小作为所需时间段数的理论下界从而评估算法解的质量。3.3 场景三城市供水网络优化最大流应用某城市供水网络如图水源地为S水厂为T中间有多个泵站和管道每条管道有最大流量限制单位万吨/天。现需评估该网络的最大供水能力并找出制约供水能力的瓶颈管道。第一步模型抽象。将水源地、水厂、泵站抽象为顶点管道抽象为有向边管道容量作为边容量。这直接形成了一个标准的单源单汇流量网络。目标是求解从S到T的最大流。第二步算法选择与实现。采用实现相对简单且效率稳定的Edmonds-Karp算法BFS寻找增广路。第三步实现细节。关键在于构建和更新残余网络。我们可以用一个邻接表来存储边的容量和流量信息每条边对应一个正向边和一个反向边对象。from collections import deque class Edge: def __init__(self, to, cap, rev): self.to to # 边的终点 self.cap cap # 剩余容量 self.rev rev # 反向边在邻接表中的索引 def add_edge(graph, fr, to, cap): 添加一条从fr到to容量为cap的边及其反向边 graph[fr].append(Edge(to, cap, len(graph[to]))) graph[to].append(Edge(fr, 0, len(graph[fr]) - 1)) # 反向边初始容量为0 def edmonds_karp(graph, s, t): n len(graph) flow 0 INF 10**9 while True: # BFS寻找增广路 prevv [-1] * n # 前驱顶点 preve [-1] * n # 前驱边索引 q deque([s]) while q: v q.popleft() for i, e in enumerate(graph[v]): if e.cap 0 and prevv[e.to] -1 and e.to ! s: prevv[e.to] v preve[e.to] i if e.to t: break q.append(e.to) if prevv[t] ! -1: break if prevv[t] -1: # 没有增广路了 break # 计算本次增广的流量 d INF v t while v ! s: e graph[prevv[v]][preve[v]] d min(d, e.cap) v prevv[v] # 更新残余网络 v t while v ! s: e graph[prevv[v]][preve[v]] e.cap - d graph[v][e.rev].cap d # 反向边容量增加 v prevv[v] flow d return flow第四步结果解释与瓶颈分析。算法返回的flow即为最大供水能力。根据最大流最小割定理算法结束后在残余网络中从源点S出发能到达的顶点集合记为S_set不能到达的集合记为T_set。那么所有从S_set指向T_set的原始边就构成了一个“最小割”这些边的容量之和等于最大流。这些边就是网络的瓶颈它们的容量限制了总流量的提升。在报告中除了给出最大流量重点应分析这个最小割集指出哪些管道是扩容的关键为决策提供直接依据。4. 进阶技巧、常见陷阱与性能考量4.1 算法变体与扩展模型最小生成树的扩展次小生成树在建模中有时需要备用方案。次小生成树是权值和第二小的生成树。一个高效算法是先求出最小生成树T然后枚举不在T中的每条边(u, v)将其加入T会形成一个环去掉这个环中除(u, v)外权值最大的边得到一棵新树。所有新树中权值最小的就是次小生成树。这需要预处理树上任意两点间路径的最大边权可用倍增法LCA实现。度限制生成树例如在网络设计中一个路由器的端口数有限即生成树中某个顶点的度不能超过k。这是一个NP难问题常用遗传算法、模拟退火等元启发式算法求解。着色问题的扩展边着色给边着色使共用一个顶点的边颜色不同。这可以建模任务调度问题其中任务边需要资源顶点共享资源的任务不能同时进行。列表着色每个顶点有一个可用的颜色列表只能从列表中选择颜色。这增加了约束更贴近实际如某些课程只能在特定时间上。最大流问题的扩展多源多汇可以添加一个超级源点连接所有源点一个超级汇点连接所有汇点转化为单源单汇问题。顶点有容量可以将一个顶点v拆分成两个顶点v_in和v_out中间连一条容量等于该顶点容量的边所有进入v的边改为进入v_in所有从v出去的边改为从v_out出去。最小费用最大流每条边不仅有容量还有单位流量的费用。在求最大流的同时要求总费用最小。这需要在增广时总是寻找费用最小的增广路通常使用SPFA或Bellman-Ford算法。4.2 常见问题与调试技巧图不连通导致算法失败Prim和Kruskal算法都要求图是连通的。在数据处理后务必检查图的连通性用DFS/BFS。对于Kruskal如果最终选出的边数少于|V|-1则说明图不连通。负权边的影响最小生成树算法通常假设边权非负。如果存在负权边Prim和Kruskal算法依然有效因为它们基于贪心选择最小边。但如果有负权环则最小生成树定义可能变得复杂总权值可以无限小通常实际问题中不会出现。最大流算法陷入死循环或效率极低这是朴素Ford-Fulkerson方法使用DFS时可能遇到的问题如果容量是无理数或算法选择增广路不当可能无法终止。务必使用Edmonds-KarpBFS或Dinic等多项式时间算法。数据结构选择不当导致超时对于稀疏图|E| |V|²使用邻接表而非邻接矩阵。Kruskal算法中并查集的“路径压缩”和“按秩合并”优化至关重要。Prim算法在稠密图中用普通数组即可在稀疏图中应使用优先队列。着色结果不理想贪心类着色算法的结果依赖于顶点顺序。可以尝试多种顺序按度降序、按度升序、随机顺序等取最好的结果。对于DSatur算法在饱和度相同时选择策略如选度最大的也会影响结果可以微调。4.3 数学建模竞赛中的呈现要点在竞赛论文中不能只贴代码和结果需要完整呈现建模过程问题重述与分析用你自己的话清晰定义问题并指出其属于图论的哪一类问题。模型假设与符号说明明确列出你的假设如“所有管道流量方向可逆”并定义文中使用的所有数学符号。模型建立这是核心。详细阐述如何将实际问题抽象为图模型顶点是什么边是什么权重/容量如何定义目标函数是什么算法设计与求解说明你选择特定算法的理由如“由于该图是稠密图我们采用Prim算法”。给出算法的步骤描述或伪代码并分析其复杂度。如果是启发式算法说明其合理性。结果分析与检验可视化将生成的树、着色方案、流量分配用图形直观展示。敏感性分析改变某个参数如某条路的成本观察结果如何变化。模型检验用特例小规模数据手工验证用理论下界如着色数不小于最大团大小评估解的质量与其他算法结果对比。瓶颈与改进分析模型的局限性如未考虑某些现实因素并提出可能的改进方向。模型评价与推广总结模型的优缺点并讨论其可应用于其他哪些类似场景。记住图论模型的价值在于其强大的抽象能力。当你面对一个看似复杂的新问题时不妨思考它的核心元素和关系能否抽象成点和边权重代表什么目标是连接、染色还是输送一旦完成这个抽象你就拥有了一个强大的工具箱可以从中选取合适的算法来寻找答案。这个过程本身就是数学建模最迷人的地方。