1. 项目概述当数学建模遇上图论如果你参加过数学建模竞赛或者在工作中处理过需要量化分析复杂关系的问题那你大概率已经和图论打过交道只是可能没意识到。图论这个听起来有点抽象的数学分支早已不是数学家的专属玩具。从我们每天使用的社交网络好友推荐、导航软件的最优路径规划到物流公司的配送网络优化、通信网络的可靠性设计甚至是在生物信息学中分析蛋白质相互作用网络图论的身影无处不在。它本质上是一种用“点”和“边”来描述事物及其间关系的语言这种强大的抽象能力让它成为解决数学建模中一类核心问题——关系与结构问题——的利器。很多初次接触数学建模的同学看到“图论”二字可能会发怵觉得它高深莫测。但我想说恰恰相反图论是数学建模工具箱里最“接地气”、最“可视化”的武器之一。你不需要成为图论专家才能用它解决问题。关键在于你是否能识别出你手头的问题本质上是一个“图”问题你的研究对象是否可以看作“节点”它们之间的联系是否可以抽象为“边”一旦完成了这个思维转换剩下的事情就变得有章可循了。无论是国赛、美赛还是亚太杯历年赛题中大量涉及网络流、路径规划、聚类分析、影响力传播等问题其内核都是图论模型。掌握图论就等于掌握了一把解开复杂关系谜题的万能钥匙。这篇文章我就结合自己多年带赛和解决实际问题的经验拆解图论在数学建模中的核心应用从模型识别到算法实现再到论文写作给你一套可以直接“抄作业”的实战指南。2. 核心思路如何将现实问题“翻译”成图模型在动用任何算法之前最核心也最考验功力的步骤是建模即把一团乱麻的现实问题抽象成一个清晰的图结构。这一步做对了问题就解决了一半。2.1 识别问题的图论本质不是所有问题都适合用图论但有几类特征非常明显的问题你看到就应该条件反射地想到图论。第一类路径与连通性问题。这是最经典的应用。题目中如果出现了“最短”、“最快”、“最少成本”、“能否到达”、“是否连通”等关键词几乎可以确定是图论问题。例如2019年国赛C题“机场的出租车问题”虽然背景是出租车调度但核心之一就是如何为出租车规划返回市区或等待区的“最优路径”以减少空驶。这里的“地点”航站楼、蓄车池、市区热点就是节点“道路”及其通行时间或成本就是边问题转化为在有向加权图中寻找最短路径或最优循环。第二类网络流与分配问题。当问题涉及“流量”、“容量”、“输送”、“最大/最小运量”时通常可以构建网络流模型。比如2021年国赛C题“生产企业原材料的订购与运输”原材料从供应商到中转仓库再到工厂的运输网络就是一个典型的流网络。供应商和工厂是节点运输线路是边每条边有运输成本权重和运力上限容量目标是在满足工厂需求的前提下最小化总成本或最大化运输效率。第三类聚类与社区发现问题。问题要求你对一组对象进行分群而分群的依据是对象之间的“相似性”或“关联强度”。这时你可以将每个对象视为节点对象之间的相似度作为边的权重相似度越高权重越大然后利用图划分算法来找寻社区。例如分析社交网络中用户的兴趣群落或者在城市规划中根据交通流量划分功能区。第四类排序与影响力问题。如果问题需要你评估节点的重要性、排名或者研究某种属性如信息、疾病在网络中的传播过程。经典的PageRank算法就是用来给网页排序的其思想同样可以用于评价学术论文的影响力、社交网络中的关键人物识别2022年国赛C题“古代玻璃制品的成分分析与鉴别”中虽然主要用化学计量学但若涉及文物贸易网络分析也会用到此思想。注意一个复杂的赛题往往包含多个子问题可能同时涉及以上多种类型。例如一个资源调度问题可能先要用聚类分析对需求点分区第三类然后在每个分区内进行路径优化第一类最后整体考虑资源流动的平衡第二类。关键在于拆解。2.2 定义图的要素点、边、权一旦确定用图论就要精确定义图的三个基本要素节点你到底要把什么定义为“点”是物理地点城市、仓库、实体人物、车辆、事件任务开始还是抽象状态库存水平定义必须清晰、无歧义且涵盖问题所有相关实体。边节点之间是否存在关系是什么关系是双向的还是单向的例如在城市道路网络中单行道就是有向边双行道可以抽象为两条反向的有向边或无向边。权重边或节点上是否需要附加数值这代表了关系的“强度”或“成本”。常见权重包括距离、时间、成本、容量、概率、相似度等。权重的设定直接决定了你后续优化目标函数。一个实操心得在论文中务必用一小节或一个清晰的段落来形式化定义你的图模型。你可以这样写“定义图 G(V, E, W)其中 V {v1, v2, ..., vn} 表示……的集合E ⊆ V × V 表示……关系若存在从 vi 到 vj 的……则 (vi, vj) ∈ E。权重函数 W: E → R 为每条边赋予一个权值代表……。” 这种形式化的描述能极大提升论文的专业性。2.3 选择图的类型别用大炮打蚊子图有多种类型选择适合问题特性的图能简化模型和计算。无向图 vs 有向图关系是否可逆朋友关系通常是无向的如果A是B的朋友B也是A的朋友而微博的关注关系是有向的A关注BB未必关注A。加权图 vs 无权图是否需要量化关系的强弱在最短路径问题中距离或时间就是权重在单纯的连通性问题中可能只需要无权图。简单图 vs 多重图两个节点间是否允许有多条边比如两个城市之间可能有铁路、公路两种连接方式需要分别考虑这时就用多重图。子图、连通图、完全图等这些概念用于描述图的特定结构。例如在聚类时我们可能寻找一个“稠密子图”内部连接紧密。对于大多数数学建模问题加权有向图是最常用也最强大的模型因为它能同时表达关系的方向性和强度。在编程实现时如使用Python的networkx库通常也以有向加权图为基础无向图可以看作特殊的有向图。3. 核心算法工具箱与选型指南模型建好了接下来就是选择算法来求解。图论算法浩如烟海但在数学建模的有限时间内掌握几个最核心、最通用的算法足以应对80%的问题。下面这个表格整理了四大类常见问题及其对应的核心算法你可以把它当作速查表。问题类型核心目标推荐算法适用场景与说明最短路径问题找到两点间总权重最小的路径Dijkstra算法最常用适用于边权均为非负的图。求解单源最短路径速度快且稳定。Bellman-Ford算法允许边权为负并能检测图中是否存在负权回路。比Dijkstra慢非必要不使用。Floyd-Warshall算法求解所有节点对之间的最短路径。代码简洁但时间复杂度O(n³)节点数多时慎用。A*搜索算法在Dijkstra基础上加入启发式函数用于已知终点且能估算剩余代价的场景如地图导航。最小生成树问题连接所有节点使总边权最小且无环Prim算法从一点开始“生长”树适合稠密图边多。通常用优先队列实现效率高。Kruskal算法按边权从小到大排序并选择适合稀疏图边少。实现简单需用并查集判断是否成环。网络流问题在容量限制下最大化从源点到汇点的流量Ford-Fulkerson方法方法框架核心是寻找增广路径。Edmonds-Karp算法Ford-Fulkerson的具体实现用BFS找增广路保证多项式时间复杂度。最推荐。Dinic算法更高效的算法通过构建分层图和多路增广在实际应用中比Edmonds-Karp更快。节点重要性/排名评估网络中节点的影响力或中心性度中心性最简单计算节点的连接数。适用于直接影响力明显的场景。接近中心性节点到网络中所有其他节点最短距离之和的倒数。反映节点不受他人控制的程度。中介中心性节点出现在任意两点最短路径上的次数。反映节点的“桥梁”或“枢纽”作用。PageRank算法考虑链接质量的迭代算法。不仅看有多少连接还看连接来自哪些重要的节点。算法选型实战建议最短路径选Dijkstra除非有负权边或需要所有点对距离否则无脑选Dijkstra。在Python中networkx的single_source_dijkstra_path_length和single_source_dijkstra_path函数开箱即用。最小生成树看密度对于完全图或接近完全的图比如所有城市两两之间都有直接道路成本数据用Prim如果边是通过某种规则生成的数量远小于完全图用Kruskal。网络流首选Edmonds-Karp概念清晰易于实现和解释能满足大多数建模需求。如果数据规模极大且追求性能再考虑学习Dinic。中心性指标结合使用不要只用一个中心性指标。比如在分析社交网络关键人物时可以同时计算度中心性人脉广、中介中心性控制信息流、特征向量中心性认识的人是否也是重要人物综合判断。networkx提供了所有这些指标的计算函数。一个踩过的坑我曾指导一个队伍处理车辆路径问题他们想当然地用了Floyd算法求所有点对距离因为代码好写。但他们的节点数客户点仓库有200个Floyd算法在普通笔记本上跑了近一分钟严重拖累后续迭代优化。其实他们只需要计算从仓库到各客户点以及客户点之间的部分距离改用多次Dijkstra算法总耗时不到0.1秒。记住算法复杂度不是纸面数字要在你的数据规模上实际感受。4. 从理论到论文全流程实战拆解我们以一个简化版的“共享单车调度优化”问题为例串联从问题理解到论文成文的完整过程。假设赛题要求在已知城市各站点当前车辆数、预测未来需求、以及调度卡车运力和行驶时间的情况下规划调度卡车的路径使得总空驶成本最低且尽快满足各站点需求。4.1 第一步模型构建与抽象定义节点我们将共享单车站点、调度中心仓库定义为节点。每个站点节点有一个属性当前车辆数与期望车辆数的差值正数为盈余负数为缺车。定义边如果调度卡车可以在两个站点或站点与中心之间直接行驶则存在一条边。这是一个完全图吗不一定可能有些道路不通需要根据实际城市道路数据生成。定义权重每条边的权重是调度卡车在该路径上行驶的时间或距离即空驶成本。同时每条边隐含了一个容量属性即一辆卡车一次能运输的自行车数量上限。问题转化这个问题本质是一个带容量约束的车辆路径问题并且结合了网络流的思想将车辆从盈余点“流”向缺乏点。我们可以将其建模为一个以调度中心为根需要服务多个需求/供给节点的特殊图。目标是在图上找到一条或多条路径覆盖所有需要服务的节点或满足其流量需求且路径总权重最小。4.2 第二步算法设计与实现Python示例我们不会追求最优解那是NP-Hard问题而是采用启发式算法寻找高质量可行解。这里展示一个基于“节约算法”的启发式思路。import networkx as nx import numpy as np from typing import List, Tuple def build_graph(node_demands: List[int], distance_matrix: np.ndarray) - nx.DiGraph: 构建调度问题的基础图。 node_demands: 列表正数表示供给量负数表示需求量0表示调度中心。 distance_matrix: 距离矩阵distance_matrix[i][j]表示从节点i到j的成本。 G nx.DiGraph() num_nodes len(node_demands) for i in range(num_nodes): G.add_node(i, demandnode_demands[i]) # 为节点添加需求属性 for i in range(num_nodes): for j in range(num_nodes): if i ! j: G.add_edge(i, j, weightdistance_matrix[i][j], travel_timedistance_matrix[i][j]) return G def clarke_wright_savings(G: nx.DiGraph, truck_capacity: int, depot_idx: int 0) - List[List[int]]: 克拉克-赖特节约算法Clarke-Wright Savings的简化实现。 返回一个由路径列表组成的调度方案。 # 初始化每个需求点单独与仓库构成一条路线 [0, i, 0] routes [[depot_idx, i, depot_idx] for i in range(G.number_of_nodes()) if i ! depot_idx] # 计算节约值 S(i,j) d(0,i) d(0,j) - d(i,j) savings [] for i in range(1, G.number_of_nodes()): for j in range(i1, G.number_of_nodes()): s G[depot_idx][i][weight] G[depot_idx][j][weight] - G[i][j][weight] savings.append((s, i, j)) # 按节约值从大到小排序 savings.sort(reverseTrue, keylambda x: x[0]) # 合并路径 for s, i, j in savings: # 找到包含i和j的路径起点和终点必须是仓库 route_i, route_j None, None pos_i, pos_j -1, -1 for idx, route in enumerate(routes): if i in route[1:-1]: # i在路径内部非端点 route_i, pos_i route, route.index(i) if j in route[1:-1]: route_j, pos_j route, route.index(j) # 如果i和j在不同路径且都在各自路径的端点紧邻仓库则考虑合并 if route_i and route_j and route_i ! route_j: # 检查合并后的路径是否满足容量约束此处简化假设需求可累加 # 以及合并的可行性i是route_i的最后一个客户点j是route_j的第一个客户点或反之 if route_i[-2] i and route_j[1] j: # 合并路径去掉route_i的最后一个仓库和route_j的第一个仓库连接 new_route route_i[:-1] route_j[1:] # 容量检查应在此进行此处省略... # 如果通过检查则替换旧路径 routes.remove(route_i) routes.remove(route_j) routes.append(new_route) return routes # 假设有5个节点0是仓库1、2供给3、4需求 demands [0, 5, 3, -4, -4] # 供给为正需求为负 # 随机生成一个距离矩阵对称 dist_matrix np.array([ [0, 2, 3, 4, 5], [2, 0, 2, 3, 4], [3, 2, 0, 2, 3], [4, 3, 2, 0, 2], [5, 4, 3, 2, 0] ]) G build_graph(demands, dist_matrix) truck_cap 6 solution_routes clarke_wright_savings(G, truck_cap) print(生成的调度路径, solution_routes)提示上述代码是一个高度简化的教学示例。真实比赛中你需要处理更复杂的约束如时间窗、多车型、动态需求等。节约算法是经典启发式方法其思想易于理解并在论文中阐述可以作为你求解复杂VRP问题的起点。实际应用时你可能需要结合局部搜索如2-opt对生成的路径进行进一步优化。4.3 第三步结果可视化与论文呈现图论最大的优势之一就是结果直观易于可视化。一定要在论文中充分利用这一点。网络结构图在模型假设部分画出示意图。可以用networkx.draw或更专业的Gephi软件绘制清晰展示节点和边。优化结果对比图将优化前的随机调度路径和优化后的路径在同一张地图背景上画出用不同颜色和线型区分直观展示优化效果路径缩短、交叉减少。指标变化曲线如果你的算法是迭代改进的如模拟退火、遗传算法绘制出目标函数值总成本随迭代次数下降的曲线证明算法的收敛性。表格汇总将不同方案如不同算法、不同参数的关键结果总里程、用车数量、完成时间、计算耗时汇总成表进行对比分析。在论文中描述算法时不要只贴代码。应该用“伪代码”或清晰的步骤描述配合流程图。例如“本文采用的改进节约算法步骤如下 步骤1初始化构建所有从仓库到单个客户点的初始路径。 步骤2计算任意两个客户点i和j的节约值s(i,j) c(0,i) c(0,j) - c(i,j)。 步骤3将节约值按降序排列。 步骤4按序考察每一对(i,j)若满足容量约束且合并可行则合并两条路径。 步骤5输出合并后的最终路径集合。”然后再在附录中提供完整的可运行源代码。5. 常见“坑点”与进阶技巧在实际比赛和项目中有些细节处理不好就会前功尽弃。5.1 数据预处理中的陷阱缺失值与异常值现实数据中节点间的距离或关系数据可能有缺失。直接删除还是插补如果两个城市之间没有直连道路数据你是认为距离为无穷大不可达还是用其他城市间接估算这需要根据问题背景合理假设并在论文中说明。规模不一致边的权重可能包含时间、成本、距离等多个维度量纲和数量级不同。在进行多目标优化或综合评估前必须进行标准化或归一化处理。例如用(x - min) / (max - min)将所有权重映射到[0,1]区间。图的稠密化对于节点很多但边相对稀疏的图如某些社交网络直接使用邻接矩阵存储会浪费大量内存和计算资源。此时应使用邻接表来存储图。networkx库内部即采用邻接表可以放心处理大规模稀疏图。5.2 算法实现与优化技巧Dijkstra算法的优先级队列自己实现Dijkstra时一定要用优先队列Python的heapq否则时间复杂度会退化。networkx的实现已经优化过了。避免重复计算在迭代算法中如果需要频繁查询两点间最短路径不要每次都调用Dijkstra。可以预先用Floyd算法计算好所有点对最短路径并存储起来用空间换时间。但要权衡Floyd的O(n³)预处理时间是否值得。启发式算法的“调参”像遗传算法、模拟退火这类元启发式算法参数种群大小、变异率、退火速率等对结果影响很大。不要拍脑袋设定应该设计一个简单的正交实验在小规模问题上测试不同参数组合的效果选择表现最好的一组用于最终求解。5.3 模型扩展与创新思路当基本模型无法完美解决问题时考虑以下扩展方向这往往是论文的加分点动态图模型传统图论假设网络结构是静态的。但在很多问题中网络是随时间变化的如交通流量早晚高峰、社交网络关系演变。你可以引入时间片将问题建模为一系列按时间顺序排列的静态图或者使用更复杂的时序图模型。多层网络模型现实中的实体可能同时属于多个网络。例如一个人既有朋友关系网社交层又有通勤轨迹网空间层。将多层网络结合起来分析能挖掘更深的信息。这在“拥堵传播”、“舆情分析”类题目中很有用。引入随机性/鲁棒性优化边的权重如旅行时间可能不是固定值而是一个随机变量服从某种分布。此时你的优化目标可能要从“最小化总成本”变为“最小化期望成本”或“最大化在给定时间内完成的概率”。这需要结合概率论和随机规划的知识。图神经网络初探对于模式识别、分类问题如论文中判断两幅网络结构是否相似可以了解下图神经网络。虽然数学建模比赛中直接从头实现GNN不现实但你可以将其作为一个先进的“黑箱”工具或对比基线体现你的视野。最后分享一个最重要的心得图论建模的精髓不在于使用了多么高深的算法而在于“抽象”的恰到好处。一个好的图模型应该像一幅简笔画用最简洁的点和线捕捉到问题最本质的结构关系。在论文中花足够的篇幅把你的建模思路、为什么这样定义点与边讲清楚这比罗列复杂的公式更能打动评委。当你拿到一个赛题感觉其中元素相互关联、错综复杂时不妨停下来想一想“这能不能画成一张图” 这个思维习惯会让你在数学建模的道路上走得更远。