数学建模里有一个很有意思的现象很多看起来八竿子打不着的问题最后都会落到同一个抽象框架上——图。物流配送要选最省时间的路线本质是最短路通信基站要选成本最低的布线方案本质是最小生成树抢险物资从仓库运到受灾点、路网还有容量上限本质是网络流一个团队里怎么给人派活才能完成尽可能多的任务本质是二分图匹配。这类题目在竞赛里反复出现考的核心往往不是某个天才创意而是你能不能把一个实际问题“翻译”成图然后选对算法、写对代码。这一章我们专门讲图与网络模型及方法。在Matlab里图的表示方式和求解函数都很成熟但我建议算法原理也要吃透。无论是全国大学生数学建模竞赛还是美赛近几年的题目里图论模型几乎成了必考板块很多时候不是让你直接调用shortestpath返回一个数字就完事而是要求说明建模过程、分析结果、做敏感性讨论。只懂函数不懂原理遇到需要改造模型的情况会非常难受。我接下来会从最核心的四个方向展开最短路、最小生成树、网络流、二分图匹配每一部分都给原理、给Matlab代码、给比赛中的使用经验。最后用一个完整的物资调运案例把这些算法串起来看看一套图论模型是怎么从题目文字一步步走到结果分析的。1. 从实际问题到邻接矩阵图论建模的第一步1.1 点、边、权把现实问题“翻译”成图建模的第一步从来不是写代码而是定义图的三要素。图在数学上很简单一组顶点节点和连接这些顶点的边。但现实中不会有任何一道题直接告诉你“节点是什么”这需要你自己判断。我总结过一套比较通用的翻译规则点有独立属性、需要被区分的实体。城市、仓库、设备、人员、工序、状态都可以是点。边实体之间的直接关系。道路、线路、依赖、匹配关系、转移可能性都是边。权这条边在问题里的量化属性。距离、时间、成本、容量、概率都可以作为权。举个最经典的例子快递配送问题里点是配送中心和客户地址边是道路连接权是路上花费的时间或距离换到通信布线问题点是机房和终端设备边是可铺设光缆的路段权是每段光缆的造价。同样是点和边因为实际含义不同后续调用的算法和解读结果的方式就完全不同。我做个表方便你理解实际场景点边权物流配送仓库、客户点可行道路里程/时间通信基站布线中心机房、基站可施工管段施工成本生产工序调度每道工序前后依赖关系工期/等待时间人员任务分配人员任务可胜任关系效率/收益这个翻译过程是整章的核心。我见过很多同学一上来就对着邻接矩阵发懵其实就是因为没把“点是什么、边是什么、权是什么”想清楚。想清楚了矩阵只是顺手的事。1.2 邻接矩阵与Matlab的图对象邻接矩阵是图论算法里最常用、也最直观的数据结构。假设图有n个节点就构造一个n乘n的矩阵WW(i,j)表示从节点i到节点j的边的权值。如果两个节点之间没有边就填inf无穷大W(i,i)一般填0表示自己到自己没有距离。无向图的邻接矩阵一定是对称的因为i到j和j到i是同一条路有向图则不一定对称可能需要分别填不同的值。这一点在建模的时候容易忽略尤其是涉及管线、管网这类方向敏感的问题时一定先确认题目说的是“双向可达”还是“单向输送”。在Matlab里有两种层面一是直接手写邻接矩阵配合自己实现的算法二是用graph和digraph对象直接调用内置求解函数。% 邻接矩阵表示4个节点1-2权值31-3权值82-4权值23-4权值5 W [0 3 8 inf; 3 0 inf 2; 8 inf 0 5; inf 2 5 0]; % 换成graph对象 g graph(W); % 可视化 plot(g, EdgeLabel, g.Edges.Weight);用邻接矩阵的好处是它和算法代码直接对应手写Dijkstra、Floyd时每一步操作都看得清清楚楚用graph对象的好处是一行就能调用shortestpath、minspantree、maxflow这些成熟函数。我一般建议先会用邻接矩阵手推算法再用graph对象做快速验证。比赛时间紧张的时候直接用内置函数能省下大量调试时间但论文里写算法原理时还是要基于邻接矩阵的那套流程来讲。2. 最短路问题Dijkstra与Floyd的完整实现2.1 先想清楚一个问题最短路在建模里到底解决什么最短路问题是图论里最基础的问题但很多同学会用错场景。最短路解决的永远是“带权图上的最优走法”而不是“能不能走通”。只要题目里出现“选择一条最优路线”“总成本最低的路径”“最短传输时间”这类表述就应该往最短路模型上想。我常用的判断办法是如果一条路径由多段组成每段有一个可相加的代价最终目标是找代价最小的一条那这就是最短路问题。注意“可相加”三个字有些题目的目标函数是“最大运量”“最小瓶颈”而不是“总代价最小”那就不是最短路可能是最小生成树或网络流。最短路在竞赛题里的另一个角色是作为子流程。比如要规划一辆车服务多个客户的路径任意两个客户之间应该走哪条路先求出全图最短路径把客户之间的最短距离作为新的“顶点间距离”再去考虑排序问题。这时候Floyd这类全源最短路算法就派上用场了。2.2 Dijkstra算法的贪心逻辑与代码Dijkstra处理的是单源最短路问题也就是从某个固定起点到其他所有点的最短路径。它的核心逻辑是贪心维护一个数组dist记录当前已知起点到各节点的最短距离每次从“尚未确定最短距离”的节点里挑一个距离最小的把它标记为已确定然后用这个节点去尝试更新它邻居的距离。这个过程叫“松弛”。为什么要每次挑距离最小的节点因为边的权都是非负的已经找到最短路径的节点不可能再被其他更远的节点优化。这是个很朴素的逻辑你现在手里有一条到A点距离10的路径其他任何没确定的节点至少离起点12那通过它们去绕到A距离只会大于等于12不可能比10小。function [dist, path] myDijkstra(W, s, t) % W: 邻接矩阵不连通为inf % s: 起点编号t: 终点编号 n size(W, 1); dist inf(1, n); visited false(1, n); prev zeros(1, n); dist(s) 0; for iter 1:n % 找未访问节点里距离最小的 unvisitedNodes find(~visited); if isempty(unvisitedNodes), break; end [dmin, idx] min(dist(unvisitedNodes)); u unvisitedNodes(idx); if dmin inf, break; end visited(u) true; if u t, break; end % 松弛操作 for v 1:n if ~visited(v) isfinite(W(u, v)) if dist(u) W(u, v) dist(v) dist(v) dist(u) W(u, v); prev(v) u; end end end end % 从终点回溯路径 path t; while path(1) ~ s path [prev(path(1)), path]; end end注意我这里面有一行容易被忽略但很重要的代码[dmin, idx] min(dist(unvisitedNodes))。如果不先把未访问节点筛出来直接min(dist)很可能会选中已经确定最短路的节点这样算法就会乱掉。很多手写Dijkstra出bug的同学最后都卡在这一步。用一个小例子验证一下4个节点W和前面一样起点1终点4。手算过程是初始dist(1)0选中1更新dist(2)3、dist(3)8未访问节点里dist最小的是2选中2更新dist(4)325此时dist(3)8未访问最小的是4dist5选中4结束。所以1到4的最短路是5路径1→2→4。这段逻辑在代码里走一遍输出完全一致。2.3 Floyd算法用动态规划的思路一劳永逸Floyd算法解决的是全源最短路问题也就是一次性求出任意两点之间的最短路径。它的思路非常优雅本质上是一个三维动态规划D(i,j)表示从i到j的当前最短距离然后尝试让每个节点k作为“中间节点”如果i→k→j比直接i→j更短就更新。function D myFloyd(W) n size(W, 1); D W; % 直接用邻接矩阵作为初始距离矩阵 for k 1:n for i 1:n for j 1:n if isfinite(D(i, k)) isfinite(D(k, j)) if D(i, k) D(k, j) D(i, j) D(i, j) D(i, k) D(k, j); end end end end end end这段代码只有十来行但包含了一个很容易踩的坑中间层循环的顺序。变量名里层是k不是i也不是j。如果写成最外层i、中间层j、内层k结果会完全错乱。原因在于“依次把每个节点作为中间节点”这个顺序本身不能被打乱因为第k轮迭代要利用前k-1轮的更新结果。Floyd和Dijkstra的选型可以从数据规模和图结构来判断维度DijkstraFloyd求解范围单源全源时间复杂度O(n^2)或O(m log n)O(n^3)适用图稀疏图、节点多节点少几百以内、稠密图负权边不适用能处理但不能有负权回路这里的负权边容易把初学者绕晕。Dijkstra在负权边存在时会失效因为“已确定最短路的节点不可能被更新”这个贪心假设被打破了——一个节点绕一圈负权边之后可能比当前记录的距离还小。Floyd可以处理负权边因为它的状态转移考虑到所有中间节点组合只要没有负权回路就能给出正确答案。所以在比赛里如果题目给出了奇怪的代价定义先检查有没有负值有负值就老实换Floyd。3. 最小生成树Kruskal与Prim的实际选择3.1 Kruskal算法把所有边排个序再逐个“收编”最小生成树要解决的问题是如何用最少的边权总和把所有节点连接成一个连通整体。最直观的场景是布线类问题——通信网络铺设光缆要把所有节点连起来每段光缆有造价怎么选才能总造价最低。Kruskal算法的思路特别适合手算和代码实现把所有边按权从小到大排序然后从权最小的边开始一条一条尝试加入生成树如果加入这条边后不会形成环就保留它如果会形成环就跳过。整个过程本质是贪心。“会不会形成环”这个判断用并查集实现最方便。并查集维护每个节点所在的集合如果一条边的两个端点已经在同一个集合里说明加入这条边会产生环路必须丢弃否则这条边可以加入同时把两个集合合并。function [T, totalW] myKruskal(W) n size(W, 1); edgeList []; for i 1:n for j i1:n if isfinite(W(i, j)) edgeList [edgeList; i, j, W(i, j)]; end end end % 按边权从小到大排序 [~, order] sort(edgeList(:, 3)); edgeList edgeList(order, :); parent 1:n; T zeros(0, 3); totalW 0; for k 1:size(edgeList, 1) u edgeList(k, 1); v edgeList(k, 2); w edgeList(k, 3); % 查找u和v的根 ru u; while parent(ru) ~ ru ru parent(ru); end rv v; while parent(rv) ~ rv rv parent(rv); end if ru ~ rv parent(ru) rv; T [T; u, v, w]; totalW totalW w; end end end这里有个工程细节邻接矩阵遍历边时我只用了j i1:n也就是只取矩阵上三角部分。如果拿来回遍历所有i,j每条无向边会被记录两次虽然不影响排序结果但会让代码运行时间翻倍而且可能因为重复边导致生成树出问题。这个习惯我在后面所有涉及无向图的代码里都保持了。3.2 什么时候选Prim什么时候选KruskalPrim算法的思路完全不同从任意一个节点开始维护一个“已经在树里”的集合每次从集合外找一个离集合最近的节点加入同时记录那条连接边。它是“加点法”Kruskal是“加边法”。Prim在稠密图上的表现更好因为它的瓶颈在于每次找最近节点复杂度O(n^2)和边数关系不大Kruskal的瓶颈在于对边排序复杂度O(m log m)更适合边数较少的稀疏图。竞赛里遇到几百上千个节点的图直接用内置函数是最稳的minspantree一行搞定但要在论文里说清楚你用的是哪种策略、为什么选它。另一个容易忽略的问题是最小生成树不一定唯一。当多条边权值相同时Kruskal选哪条、绕开哪条会影响最终生成树的形态但总权值是一样的。比赛做敏感性分析时如果发现“有多棵最优树”这不是bug而是模型固有特性论文里甚至可以作为讨论点展开。4. 网络流模型最大流算法与最小割思想4.1 流网络的三个基本约束网络流处理的是“有容量限制的网络上最多能输送多少流量”这一类问题。现实场景包括油气管网的最大输送能力、交通路网的最大通行车辆数、通信网络的最大带宽。要建立一个合法的流必须满足三个基本约束容量约束每条边上的流量不能超过该边的容量即0 ≤ f(u,v) ≤ c(u,v)。流量守恒除了源点和汇点其他中间节点流入的总流量等于流出的总流量。反对称性f(u,v) -f(v,u)表示从u流向v的量等于从v流向u的负值。第3条是很多初学同学不理解的地方。在代码里它会体现为当你沿正向边推送了流量反向边会增加一个容量等于当前流量的“虚边”。为什么要这么干因为算法允许“反悔”。前面做出的一次流量分配后来发现不是最优的就需要通过反向边把流量退回去再重新分配。这就像你规划了一条运输路线运到一半发现另一条路线更宽裕你不可能把已经发出的车撤回来但可以在账面上把流量调整过去。反向边就是那张“调整记账单”。4.2 增广路算法BFS版Edmonds-Karp求最大流的经典思路是不断找一条从源点s到汇点t的“增广路”这条路满足每条边的剩余容量都大于0然后在这条路上推送尽可能多的流量。重复这个过程直到找不到增广路当前总流量就是最大流。为什么找不到增广路就一定是最大流这就涉及最大流-最小割定理一个网络的最大流等于最小的割容量。割就是“把节点分成包含s的一边和包含t的一边割开两边的边集”割的容量是这些边的容量之和。只要还存在增广路就说明s到t还没有被“完全卡死”还能继续提高流量当增广路不存在时能到t的那一侧所有饱和边正好构成一个最小割。我用BFS来找增广路因为BFS能找到“边数最少”的增广路这保证了算法在O(VE^2)的复杂度内必然结束不会因为路径选择太差而出现极端情况。这就是经典的Edmonds-Karp算法。function [maxFlow, flow] myMaxFlow(cap, s, t) % cap: 容量矩阵不连通为0 % s: 源点t: 汇点 n size(cap, 1); flow zeros(n, n); while true pre -ones(1, n); visited false(1, n); visited(s) true; queue s; % BFS寻找增广路 while ~isempty(queue) ~visited(t) u queue(1); queue(1) []; for v 1:n if ~visited(v) cap(u, v) - flow(u, v) 1e-9 visited(v) true; pre(v) u; queue(end1) v; end end end if ~visited(t) break; % 找不到增广路 end % 计算这条增广路的瓶颈值 bottleneck inf; v t; while v ~ s u pre(v); bottleneck min(bottleneck, cap(u, v) - flow(u, v)); v u; end % 更新流量包括反向边 v t; while v ~ s u pre(v); flow(u, v) flow(u, v) bottleneck; flow(v, u) flow(v, u) - bottleneck; v u; end end maxFlow sum(flow(s, :)); end这段代码里那个1e-9是防止浮点误差。实际跑网络流时容量往往不是整数累加反向边多次后可能出现极小的残留值如果不设阈值BFS可能会在这些“本应为空”的边上反复跑导致死循环。比赛里如果发现流量模型跑不动或结果异常检查一下这里通常能解决问题。4.3 最大流-最小割定理与建模意义最大流-最小割定理不只是理论结论它在建模中的直接价值是求最大流的同时你能得到瓶颈信息。最小割边就是限制整个网络传输能力的“咽喉”在实际场景里对应着需要扩容的关键路段、关键管线。另外多源多汇问题可以很自然地转换。如果有多个仓库、多个需求点只需要加一个超级源点用容量无穷大的边连到所有仓库再加一个超级汇点让所有需求点用容量无穷大的边连到它。这样一转换就能直接用单源单汇的算法求解。这个转换我后面实战案例里会实际用到。5. 二分图匹配与匈牙利算法5.1 二分图匹配的典型场景二分图是图论里非常实用的一类特殊图所有顶点分成左右两组边只存在于左侧和右侧之间。最常见的场景是任务分配问题左侧是人员右侧是任务如果某个人能胜任某件任务就在两者之间连一条边问最多能同时安排多少个任务。类似的还有排班问题左侧是排班时段右侧是可值班人员能值班就连边目标是尽量覆盖所有时段还有教室分配问题左侧是班级右侧是可使用的教室。这类问题的共性是“一方到另一方的匹配关系”。二分图的一个关键性质是它不包含奇环长度为奇数的环这正是很多算法可以利用的前提。5.2 匈牙利算法的递归实现匈牙利算法用于求二分图最大匹配核心思路和网络流很像反复找增广路。这里增广路的含义是“一条从一个未匹配点出发、交替经过非匹配边和匹配边、最终到达另一个未匹配点的路径”。沿着增广路翻转匹配状态匹配数就能增加1。function matchCount myHungarian(adj) % adj: n1行n2列的逻辑矩阵adj(i,j)true表示左侧i可以匹配右侧j n1 size(adj, 1); n2 size(adj, 2); matchR -ones(1, n2); % 右侧每个节点匹配的左侧节点编号-1表示未匹配 matchCount 0; for u 1:n1 visited false(1, n2); if dfs(u) matchCount matchCount 1; end end function found dfs(x) for v 1:n2 if adj(x, v) ~visited(v) visited(v) true; if matchR(v) -1 || dfs(matchR(v)) matchR(v) x; found true; return; end end end found false; end end这段代码里的visited数组是关键它保证在一次尝试匹配中不会重复试探同一个右侧节点。每次从新的左侧节点u开始时visited都要重置为全false这个细节错了整个算法就废了。匈牙利算法的另一种理解方式是最大流把二分图左侧接超级源点右侧接超级汇点所有边容量设为1那么最大匹配数就等于最大流量。这种转化在实际比赛里很有用因为当你已经写好了一个最大流模板遇到匹配类题目时就可以直接套不需要再单独写匈牙利算法。但反过来遇到简单的二分图匹配手写匈牙利也就十几行代码效率更高。6. 综合实战多源多汇物资调运问题6.1 场景设定我把这一章的算法串起来走一个完整的建模流程。题目背景某应急中心需要向两个受灾点运输救援物资。路网抽象后得到5个核心节点节点1物资集散中心唯一的出发点节点2、节点3中转枢纽节点4、节点5两个受灾需求点每条道路有双向运输能力单位是“吨/天”具体容量如下路段容量1→2401→3252→3102→4302→5103→4203→515问题每天最多能从中心运出多少吨救援物资保证两个受灾点都能收到货。6.2 建图与代码求解这个案例有两个需求点属于多汇问题。按前面说的办法加一个超级汇点6让节点4和节点5分别连到6容量设为一个足够大的值比如999。这样问题就变成标准的单源单汇最大流问题。cap zeros(6, 6); cap(1,2) 40; cap(2,1) 40; cap(1,3) 25; cap(3,1) 25; cap(2,3) 10; cap(3,2) 10; cap(2,4) 30; cap(4,2) 30; cap(2,5) 10; cap(5,2) 10; cap(3,4) 20; cap(4,3) 20; cap(3,5) 15; cap(5,3) 15; cap(4,6) 999; cap(6,4) 999; cap(5,6) 999; cap(6,5) 999; [maxFlow, flow] myMaxFlow(cap, 1, 6); disp([最大运输能力: , num2str(maxFlow), 吨/天]);运行这段代码得到最大流65吨/天。我手动验证一下节点1总共只有两条出边容量分别是40和25合计65所以无论怎么走源头一天最多只能发出65吨这个数字就是理论上限。而算出来的流量分布恰好是1向2发满40吨1向3发满25吨节点2把30吨运往节点4、10吨运往节点5节点3把10吨转给节点2后剩余15吨运往节点5。最终节点4收到30吨节点5收到25吨两边加起来65吨。完美吻合。6.3 读懂结果与常见坑最大流算完别急着结束。你还要回答两个问题瓶颈在哪里如果要提高运力优先扩哪条路从最小割的角度看节点1的两个出边就是最明显的瓶颈容量相加恰好是65。如果想提高总运力优先扩1→2或1→3而不是去扩中转内部的路段。因为中转内部比如2→3哪怕扩到无限大源头进不来更多物资也没用。这就是最大流-最小割定理在结果解读上的实际价值。我在实践中还遇到过这样几个坑你都值得留意。第一容量矩阵不要只填上三角有向边要单独填无向边必须双向都填。上面代码里我所有边都写了两个方向因为救援路网默认双向可通行容量两侧相同。第二超级源点和超级汇点的容量一定要设得足够大但又不能大到影响其他计算。我习惯用999这种“明显大于其他所有容量之和”的数保证它不会成为新瓶颈。如果你手算的是几百上千的容量那超级边的容量要相应提高。第三最大流只告诉你“最多能运多少”它不负责告诉你“哪条路最便宜”。如果要同时考虑运输成本或时间就需要把问题升级为最小费用最大流在每条边上再加一个费用权值用SPFA或Bellman-Ford找“最便宜增广路”。这个方向属于网络流的进阶内容但建模比赛中出现频率不低值得在学会最大流之后再进一步。最后说一点经验图与网络模型这一章真正拉开差距的往往不是算法本身而是“翻译”能力。点怎么定义不重叠边怎么定义依据充分权怎么定义和题目指标挂钩这三步做好后面调用哪个算法都是水到渠成的事。我带比赛这些年见过太多把最小生成树当最短路用、把最大流当最短路径用的翻车案例问题都出在建模初期没有把三要素想清楚。我个人的习惯是拿到题目先画一张草稿图圈出实体连上关系标上数值然后对着这张图判断它属于哪类经典模型。这张图画对了代码半个小时就能写出来画错了后面调再久都是在错误方向上打转。希望这一章的几个案例能帮你建立起这种“先画图、再写码”的建模直觉。