冯国灿图与网络建模.ppt

图与网络建模及案例分析 中山大学 数学与计算科学学院 冯国灿 July,2013 中山大学 教练研讨会,提 要,图与网络知识点 相关问题与经典算法 案例分析 其他,提 要,图与网络知识点 相关问题与经典算法 案例分析 其他,1 图与网络知识点 著名的七桥问题,瑞士数学家欧拉在1736年发表了一篇题为“依据几何位置的解决方法”的论文，有效地解决了 “七桥问题”，这是有史以来的第一篇图论论文，欧拉被公认为图论的创始人。18世纪的哥尼斯堡城（今俄罗斯加里宁格勒)中普莱格尔河上游七座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样的游戏：一个游者怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点。没有人想出这种走法，又无法说明走法不存在，这就是著名的“七桥”难题。欧拉将这个问题归结图论的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为： 从任一点出发一笔画出七条线再回到起点 欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。,图与网络是运筹学（Operations Research）中的一个经典和重要的分支。许多经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域的问题 图的优化问题 最小支撑树 最短路径问题 一笔画问题，中国邮递员问题 最大流量问题，最小费用最大流问题 TSP问题,问题(哈密顿环球旅行问题):(哈密顿回路） 十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？,赋权图的最小费用的哈密顿回路,TSP问题,问题(四色问题): 对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了. 1972年起，黑肯与阿佩尔改进了希奇的方法，1976年，他们认为问题已经压缩到可以用计算机证明的地步了。于是从1月份起，他们就在伊利诺伊大学的IBM360机上分1482种情况检查，历时1200个小时，作了100亿个判断，最终证明了四色定理。,问题(关键路径问题): 某工程任务： 包括多道工序，这些工序相互约束,只有在某些工序完成之后, 一个工序才能开始. 即它们之间存在完成的先后次序关系,一般认为这些关系是预知的, 而且也能够预计完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目, 影响工程进度的要害工序是哪几个？,/doc/6391438.html,图论的基本概念,图的定义： 一个有序二元组(V, E ) 称为一个图, 记为G = (V, E ), 其中 V 称为G的顶点集, V, 其元素称为顶点 E 称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边. 如果V = v1, v2, , vn是有限非空点集, 则称G为有限图或n阶图.,无向图：E的每一条边都是无向边。 有向图：E的每一条边都是有向边。 混合图：,记 V = v1, v2, , vn, |V | = n ; E = e1, e2, , em(ek=vivj ) , |E | = m. 称点vi , vj为边vivj的端点. 在有向图中, 称点vi , vj分别为边vivj的始点和终点.,有边联结的两个点称为相邻的点, 有一个公共端点的边称为相邻边. 边和它的端点称为互相关联. 常用d(v)表示图G中与顶点v关联的边的数目, d(v)称为顶点v的度数. 用N(v)表示图G中所有与顶点v相邻的顶点的集合.,d(v1)= d(v3)= d(v4)=4, d(v2)=2.,一些定义,度数,顶点个数是有限的; 任意一条边有且只有两个不同的点与它相互关联; 若是无向图, 则任意两个顶点最多只有一条边与之相联结; 若是有向图, 则任意两个顶点最多只有两条边与之相联结. 当两个顶点有两条边与之相联结时，这两条边的方向相反. 如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.,有限简单图,赋权图：若将图G的每一条边e都对应一个实数F (e), 则称F (e)为该边的权, 并称图G为赋权图(网络), 记为G = (V, E , F ). 圈：设G = (V, E)是一个图, v0, v1, , vkV, 且1ik, vi-1viE, 则称v0 v1 vk是G的一条通路. 如果通路中没有相同的边, 则称此通路为道路. 始点和终点相同的道路称为圈或回路. 如果通路中既没有相同的边, 又没有相同的顶点, 则称此通路为路径, 简称路. 连通图： 任意两点均有通路的图称为连通图. 树：连通而无圈的图称为树, 常用T表示树.,一摆渡人欲将一只狼,一头羊,一篮菜从河西 河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能独处.给出渡河方法. 用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24 =16 种状态.在河东岸的状态类似记作. 状态 (0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态 (1,0,0,1), (1,1,0,0), (1,0,0,0)也是不允许的. 以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图. 根据此图便可找到渡河方法.,趣味小例,(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0) (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1),(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0) (1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1) 河西=(人,狼,羊,菜) 河东=(人,狼,羊,菜),将10个顶点分别记为A1, A2, , A10 ,则渡河问题化为在该图中求一条从A1到A10的路. 从图中易得到两条路： A1 A6 A3 A7 A2 A8 A5 A10; A1 A6 A3 A9 A4 A8 A5 A10.,图的矩阵表示, 邻接矩阵 邻接矩阵表示了点与点之间的邻接关系.一个n阶图G的邻接矩阵A = (aij )nn , 其中,例：,有向图,无向图, 权矩阵 一个n阶赋权图G = (V, E, F)的权矩阵A = (aij ) nn , 其中,有限简单图基本上可用权矩阵来表示.,无向图G的权矩阵A是一个对称矩阵.,为什么图与网络？有用实际问题与图关系的建立,无向图 联系（社交网络），道路， 航线，朋友，网络，邻接（地图，图像的像素）, 有向图 航班，亲缘（父子，师徒），状态转移，战胜， 只要有关联（能转化成关联）的就可以表示成图。,A,B,利用邻域的关系，建立Gaussian 图模型，进行图像的纹理分析,提 要,图与网络知识点 相关问题与经典算法 案例分析 其他,相关问题,支撑树，最小支撑树 最短路径问题 完全子图 最大团问题 （NPC) Hamilton 回路 TSP 问题 （ NPC) 中国邮递员问题 最大流问题 ，最小费用最大流问题,最小支撑树 Prim算法 设G=(V,E)是连通带权图，V=1,2,n。 基本思想： 首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。 在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 算法复杂性： O(n),实例：,Kruskal算法 基本思想: 将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。 复杂性： (|e|log|e|) |e| 边数,实例：,给定赋权的有向图 D=(V,E) V=vs,v2, .vt, A=e, w(e)=wij=e(vi,vj); 找vs - vt的最短路。 1. 开始 i=0, let S0=vt, P(vt)=0, (vt)=0; 对于每一顶点vvt, 令 T(v)=+. (v)=M;, let k=s. if Si=V, stop,. For viSi,d(vt,v)=P(v), else goto 2 2 考察边（vk,vj） E, 且 的点vj. If T(vj) P(vk)+wkj. Let T(vj)= P(vk)+wkj, (vj)=k, Else goto 3. 3. Let T(vji)=min (T(vj) for all If T(vji) +, then P(vji)=T(vji),Si+1= Si+vj K=ji, i=i+1, goto 1. Else stop. 算法复杂性 O(n2),最短路径算法 Dijkstra,28,最短路径(单源）实例,Dijkstra算法的迭代过程：,无向图最短路径 Floyd算法 Floyd 算法：、一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德命名。 状态转移方程如下： disti,j:=mindisti,k+distk,j,disti,j 算法： 1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。 时间复杂度为O(n);,平面上由曲线段构成的一个图形能不能一笔画成，使得在每条线段上都不重复？ 邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线?此问题由中国数学家管梅谷于1960年首先研究并给出算法。 数学家欧拉找到一笔画的规律是： 凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。 凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。 其他情况的图都不能一笔画出。（有偶数个奇点除以二便可算出此图需几笔画成。）,一笔画问题 中国邮递员问题,边的覆盖，顶点的覆盖,分析： 双向连通，即给定无向图G。 如果G不连通，则无解。 如果G是欧拉图，则显然欧拉回路就是最优路线。 如果G连通，但不是欧拉图，说明图中有奇点3。奇点都是成对出现的。 最简单情况，即2个奇点，设（u，v）。我们可以在G中对（u，v）求最短路径R，构造出新图G = G R。此时G就是欧拉图。 接下的问题是求一个k个奇点的配对方案，使得k/2个路径总长度最小。 这个就是无向完全图最小权匹配问题。有一种Edmonds算法，时间复杂度O（N3）。4 也可转换为二分图，用松弛优化的KM算法，时间复杂度也是O（N3）。 完整的算法流程如下： 1 如果G是连通图，转2，否则返回无解并结束； 2 检查G中的奇点，构成图H的顶点集； 3 求出G中每对奇点之间的最短路径长度，作为图H对应顶点间的边权； 4 对H进行最小权匹配； 5 把最小权匹配里的每一条匹配边代表的路径，加入到图G中得到图G； 6 在G中求欧拉回路，即所求的最优路线。,Euler 图：通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。,TSP 问题,旅行商问题，即TSP问题（Travelling Salesman Problem） 假设旅行商人要拜访n个城市，每个城市只能拜访一次，最后要回到原来出发的城市。 目标: 经历路径的路程为所有路径之中的最小值。 TSP问题:组合优化问题。该问题可以被证明具有NPC计算复杂性。任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。,解法,TSP 问题的解空间 - 排列树. n 点的TSP 问题 (n-1)!/2 解法 动态规划 分支定界法 近似算法 LKH 算法 遗传算法(genetic algorithm) 神经网络(neural network),Dynamic programing,基本要素：最优子结构 重叠子问题 D=(dij) nxn , dij : 城市 vi 与 vj之间的距离 从vi出发 计算复杂性 n+n(n-1)2n 例子:,36,网络最大流问题,（1） 网络 G是一个简单有向图，G=(V,E)，V=1，2，n。 在V中指定一个顶点s，称为源和另一个顶点t，称为汇。有向图G的每一条边(v,w)E，对应有一个值cap(v,w)0，称为边的容量。这样的有向图G称作一个网络。 （2） 网络流 网络上的流是定义在网络的边集合E上的一个非负函数flow=flow(v,w)，并称flow(v,w)为边(v,w)上的流量。,例：,算法： 标号法(Ford, Fulkerson),（3） 可行流 满足下述条件的流flow称为可行流： (3.1)容量约束：对每一条边(v,w)E，0flow(v,w)cap(v,w)。 (3.2)平衡约束： 对于中间顶点：流出量=流入量。 即对每个vV(vs,t)有：顶点v的流出量顶点v的流入量=0，即 对于源s：s的流出量s的流入量=源的净输出量f，即 对于汇t：t的流入量t的流出量的=汇的净输入量f，即 式中f 称为这个可行流的流量，即源的净输出量(或汇的净输入量)。 可行流总是存在的。 例如，让所有边的流量flow(v,w)=0，就得到一个其流量f=0的可行流(称为0流)。,38,（4） 边流 对于网络G的一个给定的可行流flow，将网络中满足flow(v,w)=cap(v,w)的边称为饱和边；flow(v,w)0的边称为非零流边。当边(v,w)既不是一条零流边也不是一条饱和边时，称为弱流边。 （5） 最大流 最大流问题即求网络G的一个可行流flow，使其流量f达到最大。即flow满足： 0flow(v,w)cap(v,w)，(v,w)E；且 （6） 流的费用 在实际应用中，与网络流有关的问题，不仅涉及流量，而且还有费用的因素。此时网络的每一条边(v,w)除了给定容量cap(v,w)外，还定义了一个单位流量费用cost(v,w)。对于网络中一个给定的流flow，其费用定义为：,39,增广链 U=(v1,v2,v3,v4,v5,v6) U+= (v1,v2),(v2,v3),(v3,v4),(v5,v6) U-=(v5,v4),40,（7） 残流网络 对于给定的一个流网络G及其上的一个流flow，网络G关于流flow的残流网络G*与G有相同的顶点集V，而网络G中的每一条边对应于G*中的1条边或2条边。 设(v,w)是G的一条边。 当flow(v,w)0时，（w,v）是G*中的一条边，该边的容量为cap*(w,v)=flow(v,w)； 当flow(v,w)cap(v,w)时，(v,w)是G*中的一条边，该边的容量为 cap*(v,w)=cap(v,w)-flow(v,w)。 按照残流网络的定义，当原网络G中的边(v,w)是一条零流边时，残流网络G*中有唯一的一条边(v,w)与之对应，且该边的容量为cap(v,w)。 当原网络G中的边(v,w)是一条饱和边时，残流网络G*中有唯一的一条边(w,v)与之对应，且该边的容量为cap(v,w)。 当原网络G中的边(v,w)是一条弱流边时，残流网络G*中有2条边(v,w)和(w,v)与之对应，这2条边的容量分别为cap(v,w) -flow(v,w)和flow(v,w)。 残流网络是设计与网络流有关算法的重要工具。,41,增广路算法,1 算法基本思想 设P是网络G中联结源s和汇t的一条路。定义路的方向是从s到t。 将路P上的边分成2类： 一类边的方向与路的方向一致，称为向前边。向前边的全体记为P+。 另一类边的方向与路的方向相反，称为向后边。向后边的全体记为P-。 设flow是一个可行流，P是从s到t的一条路，若P满足下列条件： （1）在P的所有向前边(v,w)上，flow(v,w)0，即P-中的每一条边都是非零流边。 则称P为关于可行流flow的一条可增广路。 可增广路是残流网络中一条容量大于0的路。 将具有上述特征的路P称为可增广路是因为可以通过修正路P上所有边流量flow(v,w)将当前可行流改进成一个流值更大的可行流。,42,增流的具体做法是： （1）不属于可增广路P的边(v,w)上的流量保持不变； （2）可增广路P上的所有边(v,w)上的流量按下述规则变化： 在向前边(v,w)上，flow(v,w)+d； 在向后边(v,w)上，flow(v,w)-d。 按下面的公式修改当前的流。 其中d称为可增广量，可按下述原则确定：d取得尽量大，又要使变化后的流仍为可行流。 按照这个原则，d既不能超过每条向前边(v,w)的cap(v,w)-flow(v,w)，也不能超过每条向后边(v,w)的flow(v,w)。 因此d应该等于向前边上的cap(v,w)-flow(v,w)与向后边上的flow(v,w)的最小值。也就是残流网络中P的最大容量。 增广路定理：设flow是网络G的一个可行流，如果不存在从s到t关于flow的可增广路P，则flow是G的一个最大流。,43,Ford, Forkerson 标号法,提 要,图与网络知识点 相关问题与经典算法 案例分析 其他,CUMCM 2000 B题 钢管订购和运输 要铺设一条的输送天然气的主管道, 如图一所示(见下页)。经筛选后可以生产这种主管道钢管的钢厂有。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。 为方便计，1km主管道钢管称为1单位钢管。 一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为个单位，钢管出厂销价1单位钢管为万元，如下表： 1单位钢管的铁路运价如下表： 1000km以上每增加1至100km运价增加5万元。 公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。 钢管可由铁路、公路运往铺设地点（不只是运到点，而是管道全线）。 （1）请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。 （2）请就（1）的模型分析：哪个钢厂钢管的销价的变化对购运计划和总费用影响最大，哪个钢厂钢管的产量的上限的变化对购运计划和总费用的影响最大，并给出相应的数字结果。 （3）如果要铺设的管道不是一条线，而是一个树形图，铁路、公路和管道构成网络，请就这种更一般的情形给出一种解决办法，并对图二按（1）的要求给出模型和结果。,运筹学背景,运输问题 m个产地 Ai （i=1,2,m) = n个销地 Bj(j=1,2,n),求解： 最小元素法，伏格尔法(Vogel) 不平衡问题,ai,bj,cij,xij,问题分析,S1 钢厂,S2 钢厂,输油管,公路,问题分析,S1 钢厂,S2 钢厂,输油管,公路,A1,Am,A2,离散化,问题分析,S1 钢厂,S2 钢厂,输油管,公路,A1,Am,Si 到Aj的花费Cij,Aj,最短路径问题 （Floyd , Dijkstra ),“工程数学”,点评:,连续需求离散化 （单位公里需求点） 建立带约束的运输问题模型 快速算法 （0-1规划 +运输问题）,2011年B题 交巡警服务平台的设置与调度,题目： “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。 试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：,（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。 对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。,（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。 如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。,附图1：A区的交通网络与平台设置的示意图,附图2：全市六区交通网络与平台设置的示意图,数据,cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls,说明： （1）图中实线表示市区道路；红色线表示连接两个区之间的道路； （2）实圆点“”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交； （3）星号“*”表示出入城区的路口节点； （4）圆圈“”表示现有交巡警服务平台的设置点； （5）圆圈加星号“* ”表示在出入城区的路口处设置了交巡警服务平台； （6）附图2中的不同颜色表示不同的区。,2011高教社杯全国大学生数学建模竞赛 B题评阅要点,说明本要点仅供参考，各赛区评阅组应根据对题目的理解及学生的解答，自主地进行评阅。 针对这个题目，评阅时请注意“数学模型、求解方法、结果与分析”这三个方面。 数学模型：尽量用数学语言、符号和公式表述，优化模型要给出明确的决策变量、目标函数和约束条件，表述准确全面。 求解方法：尽量用数学语言对算法的思路、步骤、数据的处理过程、所使用的软件给出明确的描述。 结果与分析：要有明确的数值结果，表达简明、清晰。,第一部分：,（1）要求明确给出分配各个交巡警服务平台具体管辖范围的数学模型和具体的管辖范围（一般指路口，也可考虑相关道路）。合理性主要体现在两个方面：所有平台最长出警时间尽可能短，且它们的工作量（每天的出警次数）尽量均衡，优秀论文中应该给出这两个量化指标。 参考结果：最大出警时间大于3分钟的有6个路口，最长出警时间约为5.7分钟；同时应有工作量均衡性的度量指标。 （2）要求给出决定对13个路口实施封锁的数学模型，通过求解模型，具体给出13个目标路口各由哪一个平台实施封锁，以及对每个路口的封锁时间和完成封锁的最大时间。 参考结果：最优方案的最大的封锁时间约为8分钟。 （3）模型应该考虑增设平台后，使其减少最大出警时间与各平台间工作量的均衡性效果，要具体给出需增加新平台的个数和位置，且给出其定量依据。,第二部分：,（1）应该根据最大出警时间和工作量的均衡性这两个因素建立模型，求解给出最大出警时间和工作量均衡性的具体指标，分析现有平台设置方案的合理性。依据这些结果，对明显不合理的提出改进方案：如增加平台或移动平台，都必须要有具体的平台数量和位置，且阐述这样做的理由和定量依据。 （2）要求给出能封锁住嫌疑人的数学模型，并给出算法和具体结果。 能封锁住的基本约束条件是：“出事地点到将要封锁的路口所需时间加3分钟大于等于指派平台到封锁路口的所需时间”。在这个约束条件之下给出最优封锁方案。,分析：,3 分钟覆盖的范围的计算（Floyd算法） 任意两结点之间的距离。,A,B,美国 MCM 90B 扫雪问题,高速公路,马路,入口,数学问题： 如不考虑装载，问题是两辆车走完全部马路，使重复的马路尽可能少。 分组的中国邮递员问题：,73,算法思想： 先用最大流算法算出最大流，然后根据边费用，检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少？ 只要有这个可能，就进行这样的调整。调整后，得到一个新的最大流。 然后，在这个新流的基础上继续检查，调整。这样迭代下去，直至无调整可能，便得到最小费用最大流,最小费用最大流问题,1991MCM B题 通讯网络的极小生成树,美国 2012 ICM Problem Modeling for Crime Busting,Figure 1: Network of messages from EZ Case,Requirements: Requirement 1: So far, it is known that Jean, Alex, Elsie, Paul, Ulf, Yao, and Harvey are conspirators. Also, it is known that Darlene, Tran, Jia, Ellin, Gard, Chris, Paige, and Este are not conspirators. The three known suspicious message topics are 7, 11, and 13. There is more detail about the topics in file Topics.xls. Build a model and algorithm to prioritize the 83 nodes by likelihood of being part of the conspiracy and explain your model and metrics. Jerome, Delores, and Gretchen are th