1. 从实际问题到图论模型为什么我们需要它如果你参加过数学建模比赛或者处理过一些看似复杂的调度、路径、网络问题大概率会碰到一种情况数据给出来是一堆点和线关系错综复杂。比如要规划物流中心到各个配送站的最短路径分析社交网络中信息传播的关键人物甚至是解决那个经典的“七桥问题”。这些问题的背后都有一个共同的数学骨架——图论。我不是在讲那种需要大量抽象数学证明的纯理论图论那是数学家们的领域。我们搞建模、做工程的人关心的是如何把一个具体的、杂乱的实际问题抽象成一个清晰的“图”然后用成熟的算法去解决它最后把数学结果翻译回现实世界的解决方案。这个过程Python是我们最得力的助手。它不像C那样要处理繁琐的指针和内存也不像MATLAB在某些算法库上可能受限尤其是图论相关的。Python的networkx、scipy等库让图论的建模和计算变得异常直观。很多人学图论一上来就扎进Dijkstra、Floyd的算法步骤里背了半天代码遇到实际问题还是无从下手。问题出在第一步抽象。你都没把问题正确地“画”成图后面算法再精妙也是白搭。所以这篇内容我们不急着跑代码先彻底搞懂“图”这个模型它到底能刻画现实世界中的哪些关系节点和边可以携带哪些信息理解了这些你才能看到无论是2024年数学建模国赛的交通流问题还是亚太杯的网络优化题本质上都是换了一层皮的图论问题。2. 图的数学定义与Python表示不止是点和线一提到图你可能立刻想到网络拓扑图或者思维导图。但在数学建模里图G是一个更精确的二元组G (V, E)。V是顶点Vertex或节点Node的集合E是边Edge的集合。边表示节点之间的关系每条边连接两个节点。这个简单的定义能衍生出丰富的形态对应不同的实际问题无向图 vs 有向图边是否有方向。城市间的公路不考虑单行道是无向的而微博的关注关系我关注你你不一定关注我就是有向的。加权图 vs 无权图边或节点是否带有权重。道路长度、运输成本、通信带宽就是边的权重节点的权重可能代表一个城市的物资储量。连通图 vs 非连通图是否所有节点都通过路径相连。一个全国的交通网络图可能是连通的但加上某个孤立的岛屿机场图就不连通了。在Python中我们如何表示这些图虽然你可以用字典或列表自己实现邻接表但对于建模而言直接使用成熟的库是最高效的。networkx是事实上的标准。import networkx as nx # 创建一个空的无向图 G_undirected nx.Graph() # 创建一个空的有向图 G_directed nx.DiGraph() # 添加节点可以一次加一个也可以加列表 G_undirected.add_node(1) # 添加单个节点 G_undirected.add_nodes_from([2, 3, 4]) # 添加多个节点 # 添加边同时也就添加了关联的节点 G_undirected.add_edge(1, 2) # 添加一条边 (1, 2) G_undirected.add_edges_from([(1, 3), (2, 3), (3, 4)]) # 添加多条边 # 创建带权重的边 G_undirected.add_edge(1, 4, weight7.5) # 或者 G_undirected.add_weighted_edges_from([(2, 4, 3.0), (1, 3, 2.5)]) # 查看图的基本信息 print(f节点: {list(G_undirected.nodes())}) print(f边: {list(G_undirected.edges())}) print(f节点1的邻居: {list(G_undirected.neighbors(1))}) print(f边(1,4)的权重: {G_undirected[1][4][weight]})注意nx.Graph()创建的是无向图边(1,2)和(2,1)是等价的。而nx.DiGraph()创建的是有向图add_edge(1,2)只表示从1到2的边。这里有一个非常关键的建模思维当你决定用Graph还是DiGraph时就已经在对实际问题做了一个本质假设。比如在“谣言传播”模型中如果认为A传给B后B也可能传给A无向这适用于封闭社区内闲聊如果认为信息只从权威媒体流向个体个体不能回流有向这就更适合新闻广播模型。选择哪种图取决于你对关系“对称性”的判断。3. 最短路径问题Dijkstra算法与Floyd算法的深度抉择最短路径问题是图论最经典的应用没有之一。从快递路线规划到网络数据包路由无处不在。你可能听说过Dijkstra和Floyd这两个名字但什么时候该用哪个很多人是模糊的。3.1 Dijkstra算法单源最优解的探索者Dijkstra算法的核心是解决单源最短路径问题给定一个起点求它到图中所有其他节点的最短路径和距离。它采用贪心策略逐步扩张一个“已确定最短距离的节点集合”。它的工作原理很像一场“波”的扩散初始化起点距离为0其他节点距离为无穷大。所有节点未访问。从所有未访问节点中选出当前距离起点最短的节点u标记为已访问。这个距离此时就是它的最终最短距离。检查节点u的所有邻居v。如果通过u到达v的距离比v当前记录的距离更短就更新v的距离。重复步骤2和3直到所有节点都被访问。为什么它是贪心因为它每一步都“目光短浅”地选择当前最近的点并认为这个局部最优就是全局最优的一部分。对于所有权重都为非负数的图这个假设是成立的。用networkx实现Dijkstra简单得不可思议import networkx as nx # 创建一个带权无向图 G nx.Graph() G.add_weighted_edges_from([ (0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2), (3, 5, 6), (4, 5, 3) ]) # 计算从节点0到所有节点的最短路径长度 lengths nx.single_source_dijkstra_path_length(G, source0) print(f从节点0出发的最短距离: {lengths}) # 计算从节点0到节点5的具体路径 path nx.single_source_dijkstra_path(G, source0, target5) print(f从节点0到节点5的最短路径: {path})Dijkstra的局限性它不能处理负权边。因为一旦出现负权边之前被标记为“已访问”即已确定最短路径的节点有可能通过一条包含负权边的路径变得更短这就破坏了贪心策略的基础。在建模时如果你的权重代表成本、距离总为正数Dijkstra是安全且高效的。但如果权重代表利润可能为负或者像某些金融网络中存在“套利”性质的负权回路Dijkstra就会失效。3.2 Floyd-Warshall算法全局关系的洞察者Floyd算法解决的是所有节点对之间的最短路径问题。它通过动态规划的思想巧妙地利用一个三维但通常压缩为二维的递推关系。它的核心思想是假设节点编号从1到n。我们逐步考虑是否允许使用前k个节点作为中转站。初始状态k0不允许中转两点间距离就是边的权重无边则为无穷大。当k增加到1时我们允许通过节点1中转。对于任意i和j比较“直接从i到j”和“从i到1再从1到j”的距离取更小的那个更新。以此类推当kn时我们允许使用所有节点中转此时得到的矩阵就是所有点对之间的最短距离。Floyd算法的代码极其简洁是动态规划的典范import numpy as np def floyd_warshall(graph_matrix): graph_matrix: n x n 的邻接矩阵graph_matrix[i][j]表示从i到j的边权无边为inf自身为0。 返回 dist_matrix其中 dist_matrix[i][j] 为i到j的最短距离。 n len(graph_matrix) dist graph_matrix.copy() # 初始化距离矩阵 for k in range(n): # 中转节点 for i in range(n): # 起始节点 for j in range(n): # 终止节点 # 如果通过k中转能使路径更短 if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist # 示例使用和之前类似的图结构用邻接矩阵表示 # 节点 0,1,2,3,4,5 INF float(inf) graph [ [0, 4, 2, INF, INF, INF], [4, 0, 1, 5, INF, INF], [2, 1, 0, 8, 10, INF], [INF, 5, 8, 0, 2, 6], [INF, INF, 10, 2, 0, 3], [INF, INF, INF, 6, 3, 0] ] result floyd_warshall(graph) print(所有节点对之间的最短距离矩阵:) print(np.array(result))Floyd算法的特点与代价优点代码简单不易出错能正确处理负权边只要图中没有负权回路能一次性计算出所有点对的关系这在需要频繁查询任意两点间距离的场景下预处理后查询是O(1)的。缺点时间复杂度是 O(n³)空间复杂度 O(n²)。当节点数n很大时比如上万它的计算成本会变得非常高。在数学建模中如果节点数超过500就要慎重考虑是否真的需要所有点对的信息。3.3 实战选择Dijkstra vs Floyd怎么选记住这个原则场景驱动如果你只关心从一个或少数几个起点出发的最短路径比如物流中心的配送对每个起点跑一次Dijkstra。networkx的single_source_dijkstra时间复杂度约为 O(m log n)使用优先队列其中m是边数n是节点数对于稀疏图非常高效。全局需求驱动如果你的问题本质就需要所有点对的关系比如计算网络的“中心性”指标或者需要反复查询任意两点距离并且图规模不大n在几百以内那么用Floyd一次算完更省事。负权边这是决定性的。存在负权边直接排除Dijkstra。对于有负权边但无负权回路的图可以使用Bellman-Ford算法单源或Floyd算法全源。在2024年数学建模国赛C题物流配送中配送中心是固定的需要计算到各个需求点的最短路径这明显是单源问题且道路长度非负Dijkstra是更合适的选择。如果你错误地用了Floyd虽然也能得到答案但浪费了计算资源在更大规模的仿真中可能就会超时。4. 网络中心性识别关键节点与脆弱环节最短路径告诉我们怎么走最快而中心性Centrality则告诉我们谁最重要。在社交网络里谁是影响力最大的关键人物在交通网络里哪个枢纽瘫痪会导致整个系统效率暴跌在论文引用网络里哪篇是奠基性的核心文献这些问题都需要中心性指标来量化。4.1 度中心性最简单的连接数度中心性就是数一个节点有多少个邻居。在有向图中分为入度指向该节点的边和出度从该节点指出的边。适用场景快速识别“社交达人”或“交通枢纽”。例如在微博关注网络中入度高的就是大V。局限性它只考虑了直接连接忽略了网络的整体结构。一个连接了很多小角色的节点未必比一个连接了几个关键枢纽的节点更重要。# 计算度中心性 degree_cent nx.degree_centrality(G) print(度中心性:, degree_cent)4.2 接近中心性信息传播的便捷度接近中心性衡量一个节点到网络中所有其他节点的平均最短距离的倒数。一个节点到其他节点越“近”平均路径越短它的接近中心性就越高。核心思想我不需要有很多直接朋友但我能通过很少的中间人联系到任何人那么我在信息传播上就很有优势。适用场景谣言传播的发起者、公司内部非正式消息的枢纽。它反映了节点不受他人控制的能力因为信息到达它很快。# 计算接近中心性要求图是连通图否则需要对每个连通分量单独计算 closeness_cent nx.closeness_centrality(G) print(接近中心性:, closeness_cent)4.3 中介中心性掌控流通的“守门人”中介中心性衡量一个节点出现在其他节点对最短路径上的频率。如果一个节点像一座桥连接了网络中不同的社群那么它的中介中心性就会很高。核心思想我是重要的交通要道或信息瓶颈。想从A区到B区很多人不得不经过我。适用场景识别交通网络中的关键桥梁、通信网络中的核心路由器、合作网络中连接不同学科的研究者。这个指标非常强大能发现那些连接不同社群的“结构洞”节点。# 计算中介中心性计算量较大对大图可考虑采样近似算法 betweenness_cent nx.betweenness_centrality(G) print(中介中心性:, betweenness_cent)4.4 特征向量中心性连接质量胜过数量特征向量中心性认为一个节点的重要性不仅取决于它邻居的数量更取决于它邻居的重要性。被重要的节点连接你自己也更重要。这有点像网页排名的PageRank算法的思想。核心思想与重要人物为伍你也会变得重要。适用场景学术引用网络一篇被诺贝尔奖得主引用的论文价值陡增、社交媒体影响力评估被大V转发。# 计算特征向量中心性 eigenvector_cent nx.eigenvector_centrality(G) print(特征向量中心性:, eigenvector_cent)建模中的应用心得 在数学建模中中心性指标很少单独使用。通常需要结合具体问题综合评估比如在“城市应急资源布局”问题中你可能需要同时考虑度中心性连接性、接近中心性快速到达性和中介中心性控制性给不同指标赋予权重综合打分选出最优选址。动态分析网络是变化的。比如在“舆情控制”模型中你可以计算不同时间切片网络的中介中心性找出那些在谣言传播中期突然崛起的关键“桥梁”节点针对性地进行干预。对比与验证算出的高中心性节点一定要回到原问题中去解释。如果发现一个中介中心性很高的节点在实际地图上却是一个偏僻的小路口那就要检查你的图模型边权设置、连通性假设是否合理。我曾在一次比赛中用中介中心性分析电网关键线路。单纯看度数一些大型变电站度数很高。但结合了中介中心性后我们发现了一条连接两个主要负荷区的、看似普通的输电线路它的中介值异常高。模拟这条线路故障整个系统的备用路径迂回严重导致大面积电压下降。这个发现帮助我们提出了更有针对性的加固方案而不是盲目投资于那些度数高但冗余充足的枢纽站。5. 最小生成树用最经济的连接覆盖所有节点想象一下你要在几个新建的小区之间铺设宽带光缆希望所有小区都能联网且总光缆长度最短。你不能让线路形成环因为环意味着冗余和浪费。你需要找出一套连接所有小区的、总长度最小的“树”状网络。这就是最小生成树问题。5.1 问题定义与算法思想给定一个连通的无向带权图最小生成树是它的一个子图这个子图是一棵树无环且连通包含了原图的所有顶点并且其所有边的权重之和最小。两大经典算法Prim算法和Kruskal算法。Prim算法“加点法”从一个根节点开始像“生长”一棵树一样每次选择一条连接“树内节点”和“树外节点”的权重最小的边并将该边和对应的树外节点加入树中。它非常类似于Dijkstra算法但贪心的目标不同Dijkstra贪心的是到源点的距离Prim贪心的是到整棵树的距离。Kruskal算法“加边法”将所有边按权重从小到大排序。然后按顺序检查每条边如果加入这条边不会在当前的生成森林中形成环就加入它直到加入了n-1条边n为节点数。判断是否成环需要用到并查集这种高效的数据结构。5.2 Python实现与对比networkx同样提供了现成的接口# 使用Prim算法从节点0开始生长 mst_prim nx.minimum_spanning_tree(G, algorithmprim) print(Prim算法得到的最小生成树边:, list(mst_prim.edges(dataTrue))) # 使用Kruskal算法 mst_kruskal nx.minimum_spanning_tree(G, algorithmkruskal) print(Kruskal算法得到的最小生成树边:, list(mst_kruskal.edges(dataTrue))) # 对于无向连通图两种算法结果总权重相同但边的构成可能因权重相等而不同。5.3 建模场景延伸最小生成树的应用远不止铺电缆通信网络设计基站、路由器之间的低成本连接。交通规划在保证所有村镇通达的前提下建设总里程最短的公路网初期规划。聚类分析在图像分割或数据聚类中可以将每个数据点视为节点点间距离作为边权先构建一个完全图然后找出其最小生成树。移除树中最长的几条边剩下的连通分量就形成了自然的聚类。这被称为最小生成树聚类。电路设计连接多个元件的最小导线长度。一个重要的陷阱最小生成树追求的是全局权重和最小它不保证任意两点间的路径是最短的。在生成树中两点间的路径是唯一的可能比原图中的最短路径长很多。比如你用最小生成树规划了村村通公路从A村到B村可能就得绕远路。如果你的应用场景对任意两点间的通行效率有要求比如快递那么最小生成树可能不是最佳选择你需要考虑的是“斯坦纳树”或其它更复杂的模型。6. 最大流与最小割网络传输的能力与瓶颈现在考虑一个不同的问题有一个输油管道网络每条管道有最大流量限制。从炼油厂源点到储油基地汇点这个网络每小时最多能输送多少油哪些管道一旦堵塞或变窄会直接限制整个系统的输送能力这是最大流问题。而找出那些关键的限制性管道集合就是最小割问题。6.1 核心概念增广路径与Ford-Fulkerson方法最大流算法的核心思想是不断寻找增广路径。增广路径是从源点到汇点的一条路径并且这条路径上的每一条边都有剩余的输送能力即容量减去当前流量大于0。找到一条增广路径我们就可以沿着它增加一定的流量直到网络中不存在任何增广路径为止此时就得到了最大流。最经典的实现是Edmonds-Karp算法它是Ford-Fulkerson方法的一种规定用BFS来寻找增广路径保证了多项式时间复杂度。6.2 最小割定理最大流的值等于最小割的容量这是图论中最优美的定理之一。一个图的“割”是把节点分成两个集合S和T其中源点在S汇点在T。割的容量是所有从S指向T的边的容量之和。最小割就是容量最小的那个割。定理告诉我们网络的最大传输能力等于其最脆弱环节的容量之和。找到最小割就找到了系统的关键瓶颈。在建模中这比单纯知道最大流量是多少更有价值因为它指明了加固或投资的关键位置。6.3 Python求解与实战解读networkx使用maximum_flow函数计算最大流和最小割。# 创建一个有向图作为流量网络 G_flow nx.DiGraph() # 添加边并设置容量属性 ‘capacity G_flow.add_edge(s, a, capacity3.0) G_flow.add_edge(s, b, capacity2.0) G_flow.add_edge(a, b, capacity2.0) G_flow.add_edge(a, t, capacity2.0) G_flow.add_edge(b, t, capacity3.0) # 计算从源点s到汇点t的最大流 flow_value, flow_dict nx.maximum_flow(G_flow, s, t) print(f最大流值: {flow_value}) print(每条边上的流量分配:) for u, neighbors in flow_dict.items(): for v, flow in neighbors.items(): if flow 0: print(f ({u} - {v}): {flow}) # 计算最小割 cut_value, partition nx.minimum_cut(G_flow, s, t) reachable, non_reachable partition print(f\n最小割容量: {cut_value}) print(f包含源点的集合S: {reachable}) print(f包含汇点的集合T: {non_reachable}) # 最小割的边就是所有从S指向T的边 min_cut_edges [(u, v) for u in reachable for v in non_reachable if G_flow.has_edge(u, v)] print(f最小割边集: {min_cut_edges})6.4 从最大流到多商品流与匹配问题最大流模型可以扩展多商品流网络中有多种不同的“流”需要传输比如石油、天然气共用管道它们可能有不同的源汇和优先级。这更复杂通常需要线性规划来求解。二分图最大匹配可以转化为最大流问题。例如求职者左部和职位右部构成二分图连接表示胜任关系。添加一个超级源点连接所有求职者容量1一个超级汇点连接所有职位容量1原图中的边容量设为1。那么最大流的值就是最多能匹配的岗位数。这在任务分配、人员调度中非常有用。在一次关于“云计算数据中心任务调度”的模拟中我们将计算节点和待处理任务建模为二分图利用最大流算法快速求出了在满足资源约束下的最大并行任务数并通过对偶变量分析了哪些计算资源是瓶颈类似于最小割分析为扩容决策提供了量化依据。7. 社区发现从复杂网络中挖掘内在结构面对一个庞大的社交网络或论文合作网络我们很自然地想知道里面是不是存在一些“小团体”这就是社区发现或图聚类要解决的问题。好的社区划分意味着社区内部的连接非常紧密而社区之间的连接相对稀疏。7.1 模块度衡量社区划分好坏的标准模块度ModularityQ是一个广泛使用的指标范围在[-0.5, 1]之间。值越大说明社区结构越明显。 其思想是比较实际网络中社区内部的边数与在一个随机网络中保持每个节点度数不变期望的社区内部边数。如果实际远大于随机期望说明社区划分得好。7.2 Louvain算法高效与效果兼备Louvain算法是一种基于模块度优化的启发式算法因其速度快、效果好在实际中应用极广。它分两步迭代进行局部优化将每个节点初始化为一个独立的社区。然后遍历每个节点尝试将其移动到邻居节点所在的社区计算模块度的增益。如果移动能增加模块度就执行移动。反复进行直到没有节点可以移动使模块度增加。网络聚合将第一步中形成的每个社区缩聚为一个新的“超级节点”。社区内部的边权重累加成为新节点的自环权重社区之间的边权重累加成为新节点之间的边权重。得到一个新的、更小的网络。在新的网络上重复步骤1和2直到模块度不再提升。# 安装 python-louvain 库: pip install python-louvain import community as community_louvain import matplotlib.pyplot as plt # 假设G是我们之前创建的图 # 使用Louvain算法进行社区发现 partition community_louvain.best_partition(G_undirected) # 返回一个节点-社区ID的字典 print(节点社区划分:, partition) # 计算划分的模块度 mod community_louvain.modularity(partition, G_undirected) print(f模块度 Q {mod:.4f}) # 可视化 (可选) pos nx.spring_layout(G_undirected) cmap plt.cm.get_cmap(viridis, max(partition.values()) 1) nx.draw_networkx_nodes(G_undirected, pos, partition.keys(), node_size200, cmapcmap, node_colorlist(partition.values())) nx.draw_networkx_edges(G_undirected, pos, alpha0.5) nx.draw_networkx_labels(G_undirected, pos) plt.title(fCommunity Detection (Modularity {mod:.3f})) plt.axis(off) plt.show()7.3 建模应用与注意事项社交网络分析识别兴趣小组、舆论阵营。生物信息学在蛋白质相互作用网络中发现功能相似的蛋白质复合物。推荐系统将用户-商品二分图进行社区划分同一社区内的用户可能兴趣相似。注意事项分辨率极限模块度优化存在分辨率极限问题可能无法识别出规模远小于整个网络的小社区。对于多尺度社区结构需要采用其他方法。算法随机性Louvain算法有随机性多次运行可能得到略有不同的划分。对于重要分析建议多次运行取稳定结果或共识划分。有向图和带权图Louvain算法及其模块度定义通常针对无向无权图。对于有向图或带权图需要使用相应的变体并谨慎解释结果。python-louvain库默认支持带权图。在分析一个学术合作网络时我们使用Louvain算法自动识别出了几个大的研究社群如“机器学习理论”、“计算机视觉”、“自然语言处理”并且发现了一些处于两个社群交界处的学者他们往往是跨学科研究的推动者。这个发现帮助我们更精准地绘制了该领域的研究版图。8. 实战案例城市公交网络优化建模全流程让我们用一个综合性的简化案例串联起前面讲到的多个知识点。假设你面对的问题是“为某城市新区规划公交线路要求覆盖所有小区并最小化居民总出行时间假设出行需求均匀”。8.1 问题抽象与图模型构建定义节点将每个小区、商业中心、交通枢纽抽象为图的一个节点。定义边如果两个节点之间有可能修建直达公交线路则在它们之间连一条边。定义边权权重可以是一个综合成本包含地理距离直接使用地图测距。预计行驶时间根据道路等级、红绿灯估算。建设成本如果考虑线路铺设成本。需求强度如果两节点间预测的客流量很大可以适当降低边权负权重需谨慎鼓励算法选择这条边。但更常见的做法是将需求作为另一个目标进行多目标优化。在本例中我们简化使用“行驶时间”作为边权。这就得到了一个带权无向图G_bus。8.2 初步规划基于最小生成树我们的第一个目标是“用最少的线路连接所有小区”。这直接对应最小生成树问题。使用Kruskal算法求出最小生成树MST。这给出了一个基础骨架网络保证了所有节点连通且总行驶时间如果只考虑空车运行成本最小。但正如前面提到的这个网络任意两点间的通行可能需要绕远。8.3 优化通行效率引入中心性分析与最短路径居民出行是随机的我们需要优化整体网络的通行效率。计算接近中心性找出网络中到其他节点平均时间最短的“中心”节点。这些点是设置大型换乘站或公交总站的理想位置。计算中介中心性找出网络中承载最多最短路径的“桥梁”路段。这些路段压力最大应考虑开设大站快车或增加班次。评估现状在MST网络上计算所有节点对之间的平均最短路径时间可以调用nx.all_pairs_dijkstra_path_length但注意MST是树路径唯一可直接计算。迭代加边当前的MST网络平均通行时间可能很长。我们需要在关键位置添加额外的公交线路即在原图G_bus中选一些不在MST中的边加入。加哪条边策略一降低平均距离遍历所有不在MST中的边(u, v)模拟将其加入MST形成新图G_temp重新计算G_temp中所有节点对的平均最短路径时间。选择能使平均时间下降最多的那条边加入。这是一个贪婪策略计算量较大O(m * n²)对于小规模网络可行。策略二连接高需求节点对如果我们有OD矩阵起点-终点需求矩阵优先添加连接高需求节点对的边。策略三连接中心与边缘优先添加连接高接近中心性节点和低接近中心性节点的边提升边缘地区的可达性。我们不断迭代“评估-加边”过程直到达到预算约束最多加k条边或平均通行时间满足阈值。8.4 线路设计与流量分配有了最终的物理网络节点和边的集合下一步是设计具体的公交线路即路径。这通常是一个复杂的优化问题但可以简化生成候选线路在最终网络上枚举所有连接主要枢纽高接近中心性节点和重要功能区商业中心、交通枢纽的、长度合理的简单路径。分配需求假设居民会选择最短路径出行。利用所有节点对之间的最短路径结果将OD需求分配到对应的路径上累加得到每条边上的乘客流量。评估与调整检查是否有边流量超负荷超过公交车运力。如果有考虑在该边上增加平行线路即增加班次。调整线路走向分流部分流量。这可能需要回到上一步重新优化网络。8.5 模型输出与可视化最终你的模型应该输出推荐的公交网络拓扑图哪些边被选中。每条公交线路的具体走向和停靠站。每条边的预测流量和所需发车频率。关键指标网络总建设/运营成本、居民平均出行时间、网络覆盖率等。使用networkx和matplotlib可以方便地进行可视化将节点大小映射为中心性边粗细映射为流量用颜色区分不同社区或线路让结果一目了然。这个案例融合了图构建、最小生成树、最短路径、中心性分析、甚至简单的流量分配概念。在实际数学建模竞赛中你可能只需要完成其中的几个关键步骤但清晰的图论建模思维是整个工作的基石。记住从混乱的现实数据中抽象出清晰的图结构是成功的第一步也是最考验功力的一步。 图论建模实战：从最短路径到社区发现，用Python解决复杂网络问题
1. 从实际问题到图论模型为什么我们需要它如果你参加过数学建模比赛或者处理过一些看似复杂的调度、路径、网络问题大概率会碰到一种情况数据给出来是一堆点和线关系错综复杂。比如要规划物流中心到各个配送站的最短路径分析社交网络中信息传播的关键人物甚至是解决那个经典的“七桥问题”。这些问题的背后都有一个共同的数学骨架——图论。我不是在讲那种需要大量抽象数学证明的纯理论图论那是数学家们的领域。我们搞建模、做工程的人关心的是如何把一个具体的、杂乱的实际问题抽象成一个清晰的“图”然后用成熟的算法去解决它最后把数学结果翻译回现实世界的解决方案。这个过程Python是我们最得力的助手。它不像C那样要处理繁琐的指针和内存也不像MATLAB在某些算法库上可能受限尤其是图论相关的。Python的networkx、scipy等库让图论的建模和计算变得异常直观。很多人学图论一上来就扎进Dijkstra、Floyd的算法步骤里背了半天代码遇到实际问题还是无从下手。问题出在第一步抽象。你都没把问题正确地“画”成图后面算法再精妙也是白搭。所以这篇内容我们不急着跑代码先彻底搞懂“图”这个模型它到底能刻画现实世界中的哪些关系节点和边可以携带哪些信息理解了这些你才能看到无论是2024年数学建模国赛的交通流问题还是亚太杯的网络优化题本质上都是换了一层皮的图论问题。2. 图的数学定义与Python表示不止是点和线一提到图你可能立刻想到网络拓扑图或者思维导图。但在数学建模里图G是一个更精确的二元组G (V, E)。V是顶点Vertex或节点Node的集合E是边Edge的集合。边表示节点之间的关系每条边连接两个节点。这个简单的定义能衍生出丰富的形态对应不同的实际问题无向图 vs 有向图边是否有方向。城市间的公路不考虑单行道是无向的而微博的关注关系我关注你你不一定关注我就是有向的。加权图 vs 无权图边或节点是否带有权重。道路长度、运输成本、通信带宽就是边的权重节点的权重可能代表一个城市的物资储量。连通图 vs 非连通图是否所有节点都通过路径相连。一个全国的交通网络图可能是连通的但加上某个孤立的岛屿机场图就不连通了。在Python中我们如何表示这些图虽然你可以用字典或列表自己实现邻接表但对于建模而言直接使用成熟的库是最高效的。networkx是事实上的标准。import networkx as nx # 创建一个空的无向图 G_undirected nx.Graph() # 创建一个空的有向图 G_directed nx.DiGraph() # 添加节点可以一次加一个也可以加列表 G_undirected.add_node(1) # 添加单个节点 G_undirected.add_nodes_from([2, 3, 4]) # 添加多个节点 # 添加边同时也就添加了关联的节点 G_undirected.add_edge(1, 2) # 添加一条边 (1, 2) G_undirected.add_edges_from([(1, 3), (2, 3), (3, 4)]) # 添加多条边 # 创建带权重的边 G_undirected.add_edge(1, 4, weight7.5) # 或者 G_undirected.add_weighted_edges_from([(2, 4, 3.0), (1, 3, 2.5)]) # 查看图的基本信息 print(f节点: {list(G_undirected.nodes())}) print(f边: {list(G_undirected.edges())}) print(f节点1的邻居: {list(G_undirected.neighbors(1))}) print(f边(1,4)的权重: {G_undirected[1][4][weight]})注意nx.Graph()创建的是无向图边(1,2)和(2,1)是等价的。而nx.DiGraph()创建的是有向图add_edge(1,2)只表示从1到2的边。这里有一个非常关键的建模思维当你决定用Graph还是DiGraph时就已经在对实际问题做了一个本质假设。比如在“谣言传播”模型中如果认为A传给B后B也可能传给A无向这适用于封闭社区内闲聊如果认为信息只从权威媒体流向个体个体不能回流有向这就更适合新闻广播模型。选择哪种图取决于你对关系“对称性”的判断。3. 最短路径问题Dijkstra算法与Floyd算法的深度抉择最短路径问题是图论最经典的应用没有之一。从快递路线规划到网络数据包路由无处不在。你可能听说过Dijkstra和Floyd这两个名字但什么时候该用哪个很多人是模糊的。3.1 Dijkstra算法单源最优解的探索者Dijkstra算法的核心是解决单源最短路径问题给定一个起点求它到图中所有其他节点的最短路径和距离。它采用贪心策略逐步扩张一个“已确定最短距离的节点集合”。它的工作原理很像一场“波”的扩散初始化起点距离为0其他节点距离为无穷大。所有节点未访问。从所有未访问节点中选出当前距离起点最短的节点u标记为已访问。这个距离此时就是它的最终最短距离。检查节点u的所有邻居v。如果通过u到达v的距离比v当前记录的距离更短就更新v的距离。重复步骤2和3直到所有节点都被访问。为什么它是贪心因为它每一步都“目光短浅”地选择当前最近的点并认为这个局部最优就是全局最优的一部分。对于所有权重都为非负数的图这个假设是成立的。用networkx实现Dijkstra简单得不可思议import networkx as nx # 创建一个带权无向图 G nx.Graph() G.add_weighted_edges_from([ (0, 1, 4), (0, 2, 2), (1, 2, 1), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2), (3, 5, 6), (4, 5, 3) ]) # 计算从节点0到所有节点的最短路径长度 lengths nx.single_source_dijkstra_path_length(G, source0) print(f从节点0出发的最短距离: {lengths}) # 计算从节点0到节点5的具体路径 path nx.single_source_dijkstra_path(G, source0, target5) print(f从节点0到节点5的最短路径: {path})Dijkstra的局限性它不能处理负权边。因为一旦出现负权边之前被标记为“已访问”即已确定最短路径的节点有可能通过一条包含负权边的路径变得更短这就破坏了贪心策略的基础。在建模时如果你的权重代表成本、距离总为正数Dijkstra是安全且高效的。但如果权重代表利润可能为负或者像某些金融网络中存在“套利”性质的负权回路Dijkstra就会失效。3.2 Floyd-Warshall算法全局关系的洞察者Floyd算法解决的是所有节点对之间的最短路径问题。它通过动态规划的思想巧妙地利用一个三维但通常压缩为二维的递推关系。它的核心思想是假设节点编号从1到n。我们逐步考虑是否允许使用前k个节点作为中转站。初始状态k0不允许中转两点间距离就是边的权重无边则为无穷大。当k增加到1时我们允许通过节点1中转。对于任意i和j比较“直接从i到j”和“从i到1再从1到j”的距离取更小的那个更新。以此类推当kn时我们允许使用所有节点中转此时得到的矩阵就是所有点对之间的最短距离。Floyd算法的代码极其简洁是动态规划的典范import numpy as np def floyd_warshall(graph_matrix): graph_matrix: n x n 的邻接矩阵graph_matrix[i][j]表示从i到j的边权无边为inf自身为0。 返回 dist_matrix其中 dist_matrix[i][j] 为i到j的最短距离。 n len(graph_matrix) dist graph_matrix.copy() # 初始化距离矩阵 for k in range(n): # 中转节点 for i in range(n): # 起始节点 for j in range(n): # 终止节点 # 如果通过k中转能使路径更短 if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] return dist # 示例使用和之前类似的图结构用邻接矩阵表示 # 节点 0,1,2,3,4,5 INF float(inf) graph [ [0, 4, 2, INF, INF, INF], [4, 0, 1, 5, INF, INF], [2, 1, 0, 8, 10, INF], [INF, 5, 8, 0, 2, 6], [INF, INF, 10, 2, 0, 3], [INF, INF, INF, 6, 3, 0] ] result floyd_warshall(graph) print(所有节点对之间的最短距离矩阵:) print(np.array(result))Floyd算法的特点与代价优点代码简单不易出错能正确处理负权边只要图中没有负权回路能一次性计算出所有点对的关系这在需要频繁查询任意两点间距离的场景下预处理后查询是O(1)的。缺点时间复杂度是 O(n³)空间复杂度 O(n²)。当节点数n很大时比如上万它的计算成本会变得非常高。在数学建模中如果节点数超过500就要慎重考虑是否真的需要所有点对的信息。3.3 实战选择Dijkstra vs Floyd怎么选记住这个原则场景驱动如果你只关心从一个或少数几个起点出发的最短路径比如物流中心的配送对每个起点跑一次Dijkstra。networkx的single_source_dijkstra时间复杂度约为 O(m log n)使用优先队列其中m是边数n是节点数对于稀疏图非常高效。全局需求驱动如果你的问题本质就需要所有点对的关系比如计算网络的“中心性”指标或者需要反复查询任意两点距离并且图规模不大n在几百以内那么用Floyd一次算完更省事。负权边这是决定性的。存在负权边直接排除Dijkstra。对于有负权边但无负权回路的图可以使用Bellman-Ford算法单源或Floyd算法全源。在2024年数学建模国赛C题物流配送中配送中心是固定的需要计算到各个需求点的最短路径这明显是单源问题且道路长度非负Dijkstra是更合适的选择。如果你错误地用了Floyd虽然也能得到答案但浪费了计算资源在更大规模的仿真中可能就会超时。4. 网络中心性识别关键节点与脆弱环节最短路径告诉我们怎么走最快而中心性Centrality则告诉我们谁最重要。在社交网络里谁是影响力最大的关键人物在交通网络里哪个枢纽瘫痪会导致整个系统效率暴跌在论文引用网络里哪篇是奠基性的核心文献这些问题都需要中心性指标来量化。4.1 度中心性最简单的连接数度中心性就是数一个节点有多少个邻居。在有向图中分为入度指向该节点的边和出度从该节点指出的边。适用场景快速识别“社交达人”或“交通枢纽”。例如在微博关注网络中入度高的就是大V。局限性它只考虑了直接连接忽略了网络的整体结构。一个连接了很多小角色的节点未必比一个连接了几个关键枢纽的节点更重要。# 计算度中心性 degree_cent nx.degree_centrality(G) print(度中心性:, degree_cent)4.2 接近中心性信息传播的便捷度接近中心性衡量一个节点到网络中所有其他节点的平均最短距离的倒数。一个节点到其他节点越“近”平均路径越短它的接近中心性就越高。核心思想我不需要有很多直接朋友但我能通过很少的中间人联系到任何人那么我在信息传播上就很有优势。适用场景谣言传播的发起者、公司内部非正式消息的枢纽。它反映了节点不受他人控制的能力因为信息到达它很快。# 计算接近中心性要求图是连通图否则需要对每个连通分量单独计算 closeness_cent nx.closeness_centrality(G) print(接近中心性:, closeness_cent)4.3 中介中心性掌控流通的“守门人”中介中心性衡量一个节点出现在其他节点对最短路径上的频率。如果一个节点像一座桥连接了网络中不同的社群那么它的中介中心性就会很高。核心思想我是重要的交通要道或信息瓶颈。想从A区到B区很多人不得不经过我。适用场景识别交通网络中的关键桥梁、通信网络中的核心路由器、合作网络中连接不同学科的研究者。这个指标非常强大能发现那些连接不同社群的“结构洞”节点。# 计算中介中心性计算量较大对大图可考虑采样近似算法 betweenness_cent nx.betweenness_centrality(G) print(中介中心性:, betweenness_cent)4.4 特征向量中心性连接质量胜过数量特征向量中心性认为一个节点的重要性不仅取决于它邻居的数量更取决于它邻居的重要性。被重要的节点连接你自己也更重要。这有点像网页排名的PageRank算法的思想。核心思想与重要人物为伍你也会变得重要。适用场景学术引用网络一篇被诺贝尔奖得主引用的论文价值陡增、社交媒体影响力评估被大V转发。# 计算特征向量中心性 eigenvector_cent nx.eigenvector_centrality(G) print(特征向量中心性:, eigenvector_cent)建模中的应用心得 在数学建模中中心性指标很少单独使用。通常需要结合具体问题综合评估比如在“城市应急资源布局”问题中你可能需要同时考虑度中心性连接性、接近中心性快速到达性和中介中心性控制性给不同指标赋予权重综合打分选出最优选址。动态分析网络是变化的。比如在“舆情控制”模型中你可以计算不同时间切片网络的中介中心性找出那些在谣言传播中期突然崛起的关键“桥梁”节点针对性地进行干预。对比与验证算出的高中心性节点一定要回到原问题中去解释。如果发现一个中介中心性很高的节点在实际地图上却是一个偏僻的小路口那就要检查你的图模型边权设置、连通性假设是否合理。我曾在一次比赛中用中介中心性分析电网关键线路。单纯看度数一些大型变电站度数很高。但结合了中介中心性后我们发现了一条连接两个主要负荷区的、看似普通的输电线路它的中介值异常高。模拟这条线路故障整个系统的备用路径迂回严重导致大面积电压下降。这个发现帮助我们提出了更有针对性的加固方案而不是盲目投资于那些度数高但冗余充足的枢纽站。5. 最小生成树用最经济的连接覆盖所有节点想象一下你要在几个新建的小区之间铺设宽带光缆希望所有小区都能联网且总光缆长度最短。你不能让线路形成环因为环意味着冗余和浪费。你需要找出一套连接所有小区的、总长度最小的“树”状网络。这就是最小生成树问题。5.1 问题定义与算法思想给定一个连通的无向带权图最小生成树是它的一个子图这个子图是一棵树无环且连通包含了原图的所有顶点并且其所有边的权重之和最小。两大经典算法Prim算法和Kruskal算法。Prim算法“加点法”从一个根节点开始像“生长”一棵树一样每次选择一条连接“树内节点”和“树外节点”的权重最小的边并将该边和对应的树外节点加入树中。它非常类似于Dijkstra算法但贪心的目标不同Dijkstra贪心的是到源点的距离Prim贪心的是到整棵树的距离。Kruskal算法“加边法”将所有边按权重从小到大排序。然后按顺序检查每条边如果加入这条边不会在当前的生成森林中形成环就加入它直到加入了n-1条边n为节点数。判断是否成环需要用到并查集这种高效的数据结构。5.2 Python实现与对比networkx同样提供了现成的接口# 使用Prim算法从节点0开始生长 mst_prim nx.minimum_spanning_tree(G, algorithmprim) print(Prim算法得到的最小生成树边:, list(mst_prim.edges(dataTrue))) # 使用Kruskal算法 mst_kruskal nx.minimum_spanning_tree(G, algorithmkruskal) print(Kruskal算法得到的最小生成树边:, list(mst_kruskal.edges(dataTrue))) # 对于无向连通图两种算法结果总权重相同但边的构成可能因权重相等而不同。5.3 建模场景延伸最小生成树的应用远不止铺电缆通信网络设计基站、路由器之间的低成本连接。交通规划在保证所有村镇通达的前提下建设总里程最短的公路网初期规划。聚类分析在图像分割或数据聚类中可以将每个数据点视为节点点间距离作为边权先构建一个完全图然后找出其最小生成树。移除树中最长的几条边剩下的连通分量就形成了自然的聚类。这被称为最小生成树聚类。电路设计连接多个元件的最小导线长度。一个重要的陷阱最小生成树追求的是全局权重和最小它不保证任意两点间的路径是最短的。在生成树中两点间的路径是唯一的可能比原图中的最短路径长很多。比如你用最小生成树规划了村村通公路从A村到B村可能就得绕远路。如果你的应用场景对任意两点间的通行效率有要求比如快递那么最小生成树可能不是最佳选择你需要考虑的是“斯坦纳树”或其它更复杂的模型。6. 最大流与最小割网络传输的能力与瓶颈现在考虑一个不同的问题有一个输油管道网络每条管道有最大流量限制。从炼油厂源点到储油基地汇点这个网络每小时最多能输送多少油哪些管道一旦堵塞或变窄会直接限制整个系统的输送能力这是最大流问题。而找出那些关键的限制性管道集合就是最小割问题。6.1 核心概念增广路径与Ford-Fulkerson方法最大流算法的核心思想是不断寻找增广路径。增广路径是从源点到汇点的一条路径并且这条路径上的每一条边都有剩余的输送能力即容量减去当前流量大于0。找到一条增广路径我们就可以沿着它增加一定的流量直到网络中不存在任何增广路径为止此时就得到了最大流。最经典的实现是Edmonds-Karp算法它是Ford-Fulkerson方法的一种规定用BFS来寻找增广路径保证了多项式时间复杂度。6.2 最小割定理最大流的值等于最小割的容量这是图论中最优美的定理之一。一个图的“割”是把节点分成两个集合S和T其中源点在S汇点在T。割的容量是所有从S指向T的边的容量之和。最小割就是容量最小的那个割。定理告诉我们网络的最大传输能力等于其最脆弱环节的容量之和。找到最小割就找到了系统的关键瓶颈。在建模中这比单纯知道最大流量是多少更有价值因为它指明了加固或投资的关键位置。6.3 Python求解与实战解读networkx使用maximum_flow函数计算最大流和最小割。# 创建一个有向图作为流量网络 G_flow nx.DiGraph() # 添加边并设置容量属性 ‘capacity G_flow.add_edge(s, a, capacity3.0) G_flow.add_edge(s, b, capacity2.0) G_flow.add_edge(a, b, capacity2.0) G_flow.add_edge(a, t, capacity2.0) G_flow.add_edge(b, t, capacity3.0) # 计算从源点s到汇点t的最大流 flow_value, flow_dict nx.maximum_flow(G_flow, s, t) print(f最大流值: {flow_value}) print(每条边上的流量分配:) for u, neighbors in flow_dict.items(): for v, flow in neighbors.items(): if flow 0: print(f ({u} - {v}): {flow}) # 计算最小割 cut_value, partition nx.minimum_cut(G_flow, s, t) reachable, non_reachable partition print(f\n最小割容量: {cut_value}) print(f包含源点的集合S: {reachable}) print(f包含汇点的集合T: {non_reachable}) # 最小割的边就是所有从S指向T的边 min_cut_edges [(u, v) for u in reachable for v in non_reachable if G_flow.has_edge(u, v)] print(f最小割边集: {min_cut_edges})6.4 从最大流到多商品流与匹配问题最大流模型可以扩展多商品流网络中有多种不同的“流”需要传输比如石油、天然气共用管道它们可能有不同的源汇和优先级。这更复杂通常需要线性规划来求解。二分图最大匹配可以转化为最大流问题。例如求职者左部和职位右部构成二分图连接表示胜任关系。添加一个超级源点连接所有求职者容量1一个超级汇点连接所有职位容量1原图中的边容量设为1。那么最大流的值就是最多能匹配的岗位数。这在任务分配、人员调度中非常有用。在一次关于“云计算数据中心任务调度”的模拟中我们将计算节点和待处理任务建模为二分图利用最大流算法快速求出了在满足资源约束下的最大并行任务数并通过对偶变量分析了哪些计算资源是瓶颈类似于最小割分析为扩容决策提供了量化依据。7. 社区发现从复杂网络中挖掘内在结构面对一个庞大的社交网络或论文合作网络我们很自然地想知道里面是不是存在一些“小团体”这就是社区发现或图聚类要解决的问题。好的社区划分意味着社区内部的连接非常紧密而社区之间的连接相对稀疏。7.1 模块度衡量社区划分好坏的标准模块度ModularityQ是一个广泛使用的指标范围在[-0.5, 1]之间。值越大说明社区结构越明显。 其思想是比较实际网络中社区内部的边数与在一个随机网络中保持每个节点度数不变期望的社区内部边数。如果实际远大于随机期望说明社区划分得好。7.2 Louvain算法高效与效果兼备Louvain算法是一种基于模块度优化的启发式算法因其速度快、效果好在实际中应用极广。它分两步迭代进行局部优化将每个节点初始化为一个独立的社区。然后遍历每个节点尝试将其移动到邻居节点所在的社区计算模块度的增益。如果移动能增加模块度就执行移动。反复进行直到没有节点可以移动使模块度增加。网络聚合将第一步中形成的每个社区缩聚为一个新的“超级节点”。社区内部的边权重累加成为新节点的自环权重社区之间的边权重累加成为新节点之间的边权重。得到一个新的、更小的网络。在新的网络上重复步骤1和2直到模块度不再提升。# 安装 python-louvain 库: pip install python-louvain import community as community_louvain import matplotlib.pyplot as plt # 假设G是我们之前创建的图 # 使用Louvain算法进行社区发现 partition community_louvain.best_partition(G_undirected) # 返回一个节点-社区ID的字典 print(节点社区划分:, partition) # 计算划分的模块度 mod community_louvain.modularity(partition, G_undirected) print(f模块度 Q {mod:.4f}) # 可视化 (可选) pos nx.spring_layout(G_undirected) cmap plt.cm.get_cmap(viridis, max(partition.values()) 1) nx.draw_networkx_nodes(G_undirected, pos, partition.keys(), node_size200, cmapcmap, node_colorlist(partition.values())) nx.draw_networkx_edges(G_undirected, pos, alpha0.5) nx.draw_networkx_labels(G_undirected, pos) plt.title(fCommunity Detection (Modularity {mod:.3f})) plt.axis(off) plt.show()7.3 建模应用与注意事项社交网络分析识别兴趣小组、舆论阵营。生物信息学在蛋白质相互作用网络中发现功能相似的蛋白质复合物。推荐系统将用户-商品二分图进行社区划分同一社区内的用户可能兴趣相似。注意事项分辨率极限模块度优化存在分辨率极限问题可能无法识别出规模远小于整个网络的小社区。对于多尺度社区结构需要采用其他方法。算法随机性Louvain算法有随机性多次运行可能得到略有不同的划分。对于重要分析建议多次运行取稳定结果或共识划分。有向图和带权图Louvain算法及其模块度定义通常针对无向无权图。对于有向图或带权图需要使用相应的变体并谨慎解释结果。python-louvain库默认支持带权图。在分析一个学术合作网络时我们使用Louvain算法自动识别出了几个大的研究社群如“机器学习理论”、“计算机视觉”、“自然语言处理”并且发现了一些处于两个社群交界处的学者他们往往是跨学科研究的推动者。这个发现帮助我们更精准地绘制了该领域的研究版图。8. 实战案例城市公交网络优化建模全流程让我们用一个综合性的简化案例串联起前面讲到的多个知识点。假设你面对的问题是“为某城市新区规划公交线路要求覆盖所有小区并最小化居民总出行时间假设出行需求均匀”。8.1 问题抽象与图模型构建定义节点将每个小区、商业中心、交通枢纽抽象为图的一个节点。定义边如果两个节点之间有可能修建直达公交线路则在它们之间连一条边。定义边权权重可以是一个综合成本包含地理距离直接使用地图测距。预计行驶时间根据道路等级、红绿灯估算。建设成本如果考虑线路铺设成本。需求强度如果两节点间预测的客流量很大可以适当降低边权负权重需谨慎鼓励算法选择这条边。但更常见的做法是将需求作为另一个目标进行多目标优化。在本例中我们简化使用“行驶时间”作为边权。这就得到了一个带权无向图G_bus。8.2 初步规划基于最小生成树我们的第一个目标是“用最少的线路连接所有小区”。这直接对应最小生成树问题。使用Kruskal算法求出最小生成树MST。这给出了一个基础骨架网络保证了所有节点连通且总行驶时间如果只考虑空车运行成本最小。但正如前面提到的这个网络任意两点间的通行可能需要绕远。8.3 优化通行效率引入中心性分析与最短路径居民出行是随机的我们需要优化整体网络的通行效率。计算接近中心性找出网络中到其他节点平均时间最短的“中心”节点。这些点是设置大型换乘站或公交总站的理想位置。计算中介中心性找出网络中承载最多最短路径的“桥梁”路段。这些路段压力最大应考虑开设大站快车或增加班次。评估现状在MST网络上计算所有节点对之间的平均最短路径时间可以调用nx.all_pairs_dijkstra_path_length但注意MST是树路径唯一可直接计算。迭代加边当前的MST网络平均通行时间可能很长。我们需要在关键位置添加额外的公交线路即在原图G_bus中选一些不在MST中的边加入。加哪条边策略一降低平均距离遍历所有不在MST中的边(u, v)模拟将其加入MST形成新图G_temp重新计算G_temp中所有节点对的平均最短路径时间。选择能使平均时间下降最多的那条边加入。这是一个贪婪策略计算量较大O(m * n²)对于小规模网络可行。策略二连接高需求节点对如果我们有OD矩阵起点-终点需求矩阵优先添加连接高需求节点对的边。策略三连接中心与边缘优先添加连接高接近中心性节点和低接近中心性节点的边提升边缘地区的可达性。我们不断迭代“评估-加边”过程直到达到预算约束最多加k条边或平均通行时间满足阈值。8.4 线路设计与流量分配有了最终的物理网络节点和边的集合下一步是设计具体的公交线路即路径。这通常是一个复杂的优化问题但可以简化生成候选线路在最终网络上枚举所有连接主要枢纽高接近中心性节点和重要功能区商业中心、交通枢纽的、长度合理的简单路径。分配需求假设居民会选择最短路径出行。利用所有节点对之间的最短路径结果将OD需求分配到对应的路径上累加得到每条边上的乘客流量。评估与调整检查是否有边流量超负荷超过公交车运力。如果有考虑在该边上增加平行线路即增加班次。调整线路走向分流部分流量。这可能需要回到上一步重新优化网络。8.5 模型输出与可视化最终你的模型应该输出推荐的公交网络拓扑图哪些边被选中。每条公交线路的具体走向和停靠站。每条边的预测流量和所需发车频率。关键指标网络总建设/运营成本、居民平均出行时间、网络覆盖率等。使用networkx和matplotlib可以方便地进行可视化将节点大小映射为中心性边粗细映射为流量用颜色区分不同社区或线路让结果一目了然。这个案例融合了图构建、最小生成树、最短路径、中心性分析、甚至简单的流量分配概念。在实际数学建模竞赛中你可能只需要完成其中的几个关键步骤但清晰的图论建模思维是整个工作的基石。记住从混乱的现实数据中抽象出清晰的图结构是成功的第一步也是最考验功力的一步。