1. 从“七桥问题”到现代网络为什么图论是数学建模的“瑞士军刀”如果你参加过数学建模竞赛或者处理过任何涉及“关系”和“连接”的问题比如社交网络分析、交通路线规划、物流配送优化甚至是芯片电路设计那你大概率已经和“图论”打过交道了。它不像微积分那样直观也不像线性代数那样有整齐的矩阵但图论提供了一种描述“事物之间关系”的绝佳语言。简单来说图论研究的对象就是由“点”和“线”构成的“图”。点代表实体线代表实体之间的关系。这个看似简单的模型却能抽象出从互联网结构到蛋白质相互作用的无数复杂系统。在数学建模中图论常常扮演着“幕后军师”的角色。当问题描述中出现“网络”、“路径”、“连通”、“最短”、“最大流”、“聚类”这些关键词时图论的工具箱就该登场了。无论是国赛、美赛还是亚太杯从经典的“公交线路查询”2000年国赛B题到近年热门的“物流配送”、“网络舆情传播”、“芯片布局优化”图论模型都是解决这类问题的核心框架。它之所以强大是因为它将一个具体、杂乱的实际问题转化成了一个可以用严谨数学方法算法来分析和求解的抽象模型。掌握了图论就等于在数学建模的武器库里添上了一把多功能的“瑞士军刀”。2. 图的基石如何用数学语言描述你的问题在动手建模之前我们必须先把现实世界“翻译”成图论的语言。这一步至关重要它决定了后续所有分析的起点是否正确。2.1 图的定义与分类不只是点和线一个图G通常定义为二元组(V, E)其中V是顶点的集合E是边的集合。边e ∈ E连接两个顶点u, v ∈ V可以记作(u, v)或e uv。根据边的性质图可以分为几大类选择哪种类型直接对应着问题的不同假设无向图 vs. 有向图这是最基础的分类。无向图边没有方向。例如在描述城市间的公路网假设所有公路都是双向的、社交网络中的好友关系A是B的好友则B也是A的好友时我们使用无向图。边(u, v)和(v, u)是同一条边。有向图边有方向用箭头表示。例如在描述网页之间的超链接A网页链接到B网页但B不一定链接回A、交通流中的单行道、任务之间的依赖关系任务A完成后才能开始任务B时必须使用有向图。此时(u, v)和(v, u)是两条不同的边。无权图 vs. 带权图无权图我们只关心顶点之间“是否相连”。边没有附加的数值信息。带权图每条边有时甚至是每个顶点都被赋予一个权值。这个权值可以代表距离、时间、成本、流量容量、相关性强度等等。例如在寻找最短路径时地图就是一个带权图权值是道路长度或通行时间。简单图 vs. 多重图简单图任意两个顶点之间最多只有一条边且没有顶点连接到自身的边自环。大多数理论分析和经典算法都基于简单图。多重图允许两个顶点之间存在多条平行的边。这在建模某些交通网络两地间有多条不同班次的航线或电路网络时有用。建模心得很多新手在第一步就会出错。比如在建模“微博信息传播”时如果A转发B的微博信息是从B流向A这是一个有向的关系。如果你错误地建成了无向图就意味着信息可以双向等概率传播这显然与事实不符会导致后续的传播模型完全失效。所以花时间厘清关系的方向性和是否需要权重是建模成功的基石。2.2 图的存储计算机如何“认识”一张图当我们用编程实现图论算法时无论是用 MATLAB、Python 还是其他工具首先需要解决的是图的存储问题。主要有两种主流方法各有优劣邻接矩阵用一个n x n的矩阵A来表示一个具有n个顶点的图。如果顶点i和j之间有边则A[i][j] 1无权图或A[i][j] w权值。对于无向图矩阵是对称的。优点直观检查任意两个顶点是否相邻非常快O(1)时间复杂度。缺点占用空间大O(n²)对于顶点很多但边很稀疏的图如社交网络空间浪费严重。邻接表为每个顶点维护一个列表记录所有与它相邻的顶点及边的权值。优点空间效率高只存储存在的边空间复杂度为 O(|V||E|)。遍历某个顶点的所有邻居非常高效。缺点检查任意两个顶点是否相邻需要遍历其中一个顶点的邻接表速度较慢最坏 O(n)。选择建议在数学建模中如果图规模不大比如顶点数1000用邻接矩阵更容易编程和调试。如果图规模巨大且稀疏如数万个网页的链接关系邻接表是唯一的选择。Python 的networkx库、MATLAB 的graph和digraph对象都内部采用了高效的存储方式我们可以直接调用但理解其背后的原理有助于我们写出更高效的代码。3. 图论核心算法工具箱从寻路到规划将问题抽象成图之后接下来就是调用各种算法来“解图”。下面这几个算法是数学建模中最常被用到的“明星算法”。3.1 最短路径问题找到最优连接这是图论最经典的应用之一。给定一个带权图权值代表距离、成本或时间和起点、终点找到一条路径使得沿途的权值之和最小。Dijkstra算法解决非负权图的单源最短路径问题从一个起点到图中所有其他顶点的最短路径。核心思想一种贪心策略。维护一个“已确定最短距离”的顶点集合 S。每次从尚未确定的顶点中选择一个距离起点最近的顶点加入 S并利用这个新确定的顶点去更新它所有邻居的距离估计。为什么权值不能为负Dijkstra 算法的贪心假设是一旦一个顶点被加入 S其最短距离就确定了。如果存在负权边后来可能通过一条包含负权边的路径让这个距离变得更短从而破坏算法的正确性。建模应用城市导航道路长度非负、网络数据包路由延迟非负、项目关键路径分析任务时间非负。在 2024 年数学建模国赛 C 题关于物流配送的问题中配送中心到各个客户点的最短行车路径就可以用 Dijkstra 算法求解。Floyd-Warshall算法解决任意两点之间的最短路径问题。核心思想动态规划。定义dist[i][j][k]为从顶点 i 到 j且中间只经过编号不超过 k 的顶点的最短路径长度。通过三重循环逐步“允许”更多的顶点作为中转站。优缺点代码极其简洁三重 for 循环能一次性求出所有点对之间的最短距离。但时间复杂度是 O(n³)因此只适用于顶点规模不大n 500的稠密图。建模应用需要预先计算所有地点之间距离的全局规划问题。例如在多个配送中心协同调度时可能需要频繁查询任意两个客户点之间的最短距离用 Floyd 算法预处理出一个距离矩阵会非常方便。A搜索算法*在 Dijkstra 基础上加入了启发式函数用于在已知终点时加速搜索。核心思想不仅考虑从起点到当前顶点的实际代价g(n)还估计从当前顶点到终点的预计代价h(n)。每次优先扩展f(n) g(n) h(n)最小的顶点。h(n)是一个启发函数例如在网格地图中常用曼哈顿距离或欧几里得距离。关键启发函数h(n)必须满足可采纳性不能高估实际代价才能保证找到最优解。如果h(n) 0A* 就退化为 Dijkstra。建模应用游戏 AI 寻路、机器人路径规划、带有地理信息约束的路径搜索。当图非常大且我们对终点位置有先验知识时A* 比 Dijkstra 快得多。实操避坑使用 Dijkstra 算法时务必检查图中是否有负权边。一个常见的坑是当用“利润”或“收益”作为权值并想求“最大收益路径”时有人会简单地将权值取负然后套用 Dijkstra 求最短路径。这只有在所有收益都为负即原权值为正时才等价。如果原权值有正有负取负后会出现负权环Dijkstra 算法失效。此时应使用可以处理负权边的 Bellman-Ford 算法或将其转化为网络流问题。3.2 最小生成树用最经济的成本连接所有节点想象你要为几个村庄铺设电网或光纤要求所有村庄都能连通且总线路长度最短。这就是最小生成树的典型场景。Prim算法从一个顶点开始逐步“生长”出一棵树。核心思想维护两个集合已在树中的顶点集合 T和尚未在树中的顶点集合。每次从连接 T 与外部顶点的所有边中选择一条权值最小的边并将该边及其连接的外部顶点加入 T。实现通常使用优先队列最小堆来高效地选取最小边时间复杂度为 O(|E| log|V|)。Kruskal算法按边权从小到大尝试加入并避免形成环。核心思想将所有边按权值从小到大排序。依次考虑每条边如果这条边连接的两个顶点目前不在同一个连通分量中加入它不会形成环就选中这条边并将两个连通分量合并。直到选中了 n-1 条边为止。实现排序需要 O(|E| log|E|)而判断和合并连通分量需要使用并查集数据结构其单次操作平均时间复杂度接近常数。因此总复杂度主要由排序决定。算法选择对比特性Prim算法Kruskal算法适用图稠密图稀疏图时间复杂度O(V思想像“生长”一棵树像“拼接”一棵树实现关键优先队列并查集建模应用除了网络建设最小生成树还用于聚类分析通过断开树中权值最大的边来进行层次聚类、图像分割、以及一些近似算法中。在 2022 年数学建模国赛 C 题古代玻璃制品的成分分析中虽然主体是统计分析但若想分析不同类别文物化学成分的“关联网络”最小生成树可以帮助提炼出最核心的关联关系。3.3 网络流与最大流/最小割建模资源传输的极限当图中的边代表管道权值代表管道容量我们需要计算从源头源点到目的地汇点能传输的最大流量时就需要网络流模型。最大流问题给定一个有向的流量网络边有容量求从源点 s 到汇点 t 的最大流量。Ford-Fulkerson 方法核心框架是不断寻找增广路径从 s 到 t 的、剩余容量为正的路径并沿该路径推送尽可能多的流量直到找不到增广路径为止。Edmonds-Karp 算法是 Ford-Fulkerson 方法的一个具体实现规定每次用 BFS 寻找最短的增广路径。这保证了算法一定能在 O(|V| * |E|²) 时间内终止避免了某些情况下无限循环或效率极低的问题。Dinic 算法更高效的算法通过引入“分层图”和“阻塞流”的概念时间复杂度优化到 O(|V|² * |E|)在实际竞赛和工程中更为常用。最小割问题与最大流问题紧密相关。一个割是将顶点集 V 分成包含源点 s 的集合 S 和包含汇点 t 的集合 T。割的容量是所有从 S 指向 T 的边的容量之和。最大流最小割定理指出网络中从 s 到 t 的最大流量等于分隔 s 和 t 的最小割的容量。这个定理极其强大它意味着求最大流和求最小割是等价问题。算法在求出最大流的同时实际上也找到了一个最小割。建模应用交通规划道路网络的最大通行能力。数据传输通信网络的最大带宽。资源分配匹配问题如求职者与岗位。可以转化为一个最大流问题建立源点连接所有求职者、中间层求职者与岗位的匹配关系容量为1、汇点连接所有岗位。最大流量就是最大匹配数。图像分割将图像像素划分为前景和背景。可以构建一个流网络其中像素作为顶点与源点前景和汇点背景的边权代表属于前景/背景的概率像素之间的边权代表相似性。最小割就对应着能量最小的分割方案。个人体会网络流问题的难点往往不在于算法实现有很多现成库而在于如何将实际问题巧妙地转化为网络流模型。识别出问题中的“源”、“汇”、“容量”和“流量守恒”中间节点流入等于流出是建模的关键。一旦转化成功问题就变成了一个标准的、有成熟解法的问题。4. 图的深入性质与应用洞察复杂系统的结构除了解决具体的优化问题图论还提供了一系列工具来刻画图的整体结构特性这对于分析复杂系统至关重要。4.1 连通性与中心性谁是这个网络的关键连通分量无向图连通分量极大连通子图。可以用深度优先搜索DFS或广度优先搜索BFS轻松找出所有连通分量。这对于检查网络的整体连通性例如社交网络中是否存在孤立的群体非常有用。有向图强连通分量在有向图中如果一个子图内任意两个顶点都可以互相到达则该子图是一个强连通分量。求解强连通分量的经典算法是Kosaraju 算法或Tarjan 算法。这可以用于分析网页链接形成的社区一组互相紧密链接的网页或者循环依赖的模块。中心性度量用于量化图中顶点的重要性。度中心性一个顶点的邻居数。最简单直观在社交网络中度中心性高的人就是“交友广泛”的人。接近中心性一个顶点到图中所有其他顶点的最短路径距离之和的倒数。值越大说明该顶点在信息传播中越处于中心位置到其他顶点“越快”。中介中心性一个顶点出现在任意两个顶点最短路径上的次数。中介中心性高的人或节点是网络中的“桥梁”或“枢纽”控制着信息或资源的流动。例如在航空网络中某个机场的中介中心性高意味着它是许多航线不可或缺的中转站。特征向量中心性认为一个顶点的重要性取决于其邻居的重要性。这类似于网页排名的 PageRank 算法的思想。一个顶点即使邻居不多但如果它的邻居都是重要顶点那么它自己也重要。建模应用在“舆情传播”、“关键节点识别”类题目中如某些赛题中寻找影响舆论的关键人物中心性分析是核心步骤。你需要根据问题背景选择合适的中心性指标。例如如果想找出传播谣言最快的人应关注接近中心性如果想找出一旦被控制就能最大程度破坏网络连通性的人应关注中介中心性。4.2 图的匹配与着色解决分配与冲突问题匹配问题在图 G 中一个匹配是一个边的集合其中任意两条边都没有公共顶点。最大匹配是包含边数最多的匹配。二分图匹配如果图的顶点可以被分成两个不相交的集合如求职者和岗位且所有边都连接着分属不同集合的顶点则该图是二分图。二分图的最大匹配可以用匈牙利算法高效求解。建模应用任务分配、学员选课、广告投放广告与广告位匹配。在 2025 年研究生数学建模 D 题或类似调度问题中将任务和资源建模为二分图的两部分用匈牙利算法求最大匹配是一种经典的思路。图着色问题给图的每个顶点分配一种颜色使得任何一条边连接的两个顶点颜色不同。所需的最少颜色数称为图的色数。应用本质上是一个资源分配冲突避免问题。经典例子是课程表安排顶点是课程如果两门课有共同的学生就在它们之间连一条边。给顶点着色就是给课程安排时间每种颜色代表一个时间段要求有冲突的课程不同色。色数就是所需的最少时间段数。求解图着色是 NP 难问题对于一般图没有快速精确算法。实践中常使用贪心算法如 Welsh-Powell 算法求近似解或者使用回溯法、整数规划求小规模图的精确解。实操技巧对于匹配问题首先要判断你的图是否是二分图。一个简单的判定方法是使用 BFS 或 DFS 进行二着色从任意顶点开始将其染成红色将其所有邻居染成蓝色再将邻居的邻居染成红色……如果在染色过程中发现某个邻居的颜色与当前顶点相同则不是二分图。如果图不是二分图问题就变成了更复杂的“一般图匹配”需要使用开花树算法等难度大增。在建模时应尽量通过合理的抽象将问题转化为二分图匹配。5. 从模型到代码数学建模中的图论实战理论再漂亮最终也要落地为代码和论文。这部分分享一些将图论应用于数学建模竞赛的实战经验。5.1 工具链选择MATLAB vs. Python这是数学建模中最常见的两个选择。MATLAB优点内置了强大的图论工具箱。graph和digraph对象创建非常方便shortestpath(Dijkstra)、minspantree(Prim)、maxflow、centrality等函数一键调用对于快速原型验证和求解标准问题极其友好。绘图功能强大能轻松生成美观的网络图。缺点处理超大规模图时性能可能不如 Python 的一些库灵活。自定义复杂算法时语法不如 Python 简洁。适用场景国赛、美赛中问题规模适中追求快速出结果和漂亮可视化时MATLAB 是首选。Python优点生态丰富。networkx库提供了极其全面的图论算法实现和网络分析功能。scipy.sparse可以高效处理稀疏矩阵邻接矩阵。与numpy,pandas,matplotlib等库无缝集成进行数据预处理和后分析非常方便。对于需要自定义复杂算法或集成机器学习模型的情况Python 更灵活。缺点networkx纯 Python 实现对于超大规模图百万顶点以上的计算性能是瓶颈但通常数学建模竞赛的规模达不到这个级别。适用场景亚太杯等竞赛或者问题涉及复杂的数据预处理、需要与其他 AI/统计模型结合时Python 是更强大的选择。我的建议队伍里至少有一人熟练掌握其中一种工具链。对于新手队伍如果时间紧迫MATLAB 的上手速度更快。对于想追求更高灵活性和处理复杂问题的队伍Python 是更长远的选择。很多优秀的论文往往是混合使用比如用 Python 做数据清洗和复杂建模用 MATLAB 做某个特定算法的求解和绘图。5.2 建模流程与论文书写要点一个完整的图论建模流程通常包括问题抽象与图定义明确顶点是什么边是什么边是否有向、是否有权。这是最重要的一步要在论文中清晰阐述。模型选择与建立根据问题目标最短路径、最大流、最小连接、关键节点识别等选择对应的图论模型。论证为什么这个模型适合本问题。算法选择与求解说明选用什么算法Dijkstra, Floyd, Prim, Edmonds-Karp, 匈牙利算法等并简述算法步骤。如果算法有变种或参数如 A* 的启发函数需要说明设计理由。结果分析与可视化给出算法输出的结果如最短路径长度、最大流量值、最小生成树结构、关键节点列表等。务必进行可视化绘制出网络图用节点大小、颜色、边的粗细来直观展示权重、流量、中心性等结果。一张好的图胜过千言万语。模型检验与推广讨论模型的灵敏度比如某条边的权值变化对结果的影响、鲁棒性随机移除一些节点或边网络性能如何变化。思考模型还可以应用到哪些类似场景。论文避坑指南忌“黑箱”操作不要只写“我们使用了 networkx 库的 shortest_path 函数”而要写出你构建的图是什么调用的是什么算法如 Dijkstra甚至可以写出算法的伪代码或核心步骤。忌只有文字没有图图论模型天然适合可视化。在论文中放入清晰美观的网络结构图、最短路径示意图、流量分布图、中心性排名柱状图等能极大提升论文的可读性和说服力。忌模型单薄很多问题不能仅用一个图论模型解决。例如物流配送问题可能先要用图论求最短路径再用线性规划或启发式算法进行车辆路径规划。图论常常是复杂模型中的一个关键模块。要在论文中清晰阐述各个模块是如何衔接的。重视复杂度分析在“模型评价”部分分析你所采用算法的时间复杂度和空间复杂度说明其对问题规模的承受能力。这体现了你对模型深度的理解。5.3 一个综合案例社区快递点选址问题假设一个赛题要求为某个大学校园规划新的快递收发点目标是让学生从宿舍到快递点的平均距离最短且建设成本与点数有关不能太高。抽象将校园道路交叉口、宿舍楼入口、备选快递点位置抽象为顶点。将校园道路抽象为边权值为道路的实际长度或步行时间。宿舍楼顶点有“需求权重”学生人数。建模这是一个设施选址问题的变种。可以建立这样一个模型假设只能选 k 个点建快递点。对于每个宿舍楼其“不便利度”定义为该宿舍楼到最近快递点的最短距离乘以该楼的学生人数。目标最小化所有宿舍楼的“不便利度”之和。求解这是一个 NP-Hard 的组合优化问题。常用启发式算法求解如贪心算法每次选择一个能最大程度降低总不便利度的位置直到选满 k 个。模拟退火/遗传算法将 k 个点的选择作为一个解进行全局优化。在每一步中都需要调用Dijkstra 算法多次来计算每个宿舍楼到当前选址方案中最近点的距离。分析可以绘制出最终选址的网络图用不同颜色标记快递点和宿舍楼用线的粗细表示服务关系。分析当 k 变化时总不便利度的下降曲线为决策提供“性价比”参考。通过这个例子可以看到图论最短路径算法是整个求解过程中的一个核心计算子模块它与优化算法紧密结合共同解决了实际问题。图论的精妙之处在于它用极其简洁的数学结构捕捉了万物之间联系的骨架。在数学建模中它更像是一种思维模式当你看到“关系”、“网络”、“路径”、“分配”这些字眼时能立刻联想到点与线并能从丰富的算法工具箱里挑选出合适的工具。这种能力需要通过学习和实践一个个具体的模型和算法来积累。从看懂一篇优秀论文中的图模型开始到自己动手用代码实现一个最短路径算法再到完整地解决一个综合性的赛题每一步都在加深你对这种强大建模语言的理解。