1、2022年6月2日7时04分全国数学建模竞赛培训 这是一场艰苦的战役。需要不怕苦和不怕累的精神，要有坚忍不拔的毅力。2022年6月2日7时04分v可能面临酷暑、内容多、强度大的困难。2022年6月2日7时04分数学建模暑期培训纪律v不允许缺课，迟到和早退的现象发生。v每一个队每一次培训或讲评，必须是三人到齐。v教练会对每一次活动考勤，并与相关学院联系，对缺课学生予以相应处罚。2022年6月2日7时04分图论算法v参考教材：v数学建模与数学实验（赵静、但琦编）v数学建模导论（陈理荣编）v图论及其算法（殷剑宏、吴开亚编）v集合论与图论（耿素云编）2022年6月2日7时04分图论算法.最短路问题最短
2、路问题.中国邮递员问题和问题中国邮递员问题和问题.匹配匹配2022年6月2日7时04分图论算法（）最短路问题图论算法（）最短路问题1图图 论论 的的 基基 本本 概概 念念2最最 短短 路路 问问 题题 及及 其其 算算 法法3最最 短短 路路 的的 应应 用用4建模案例：最优截断切割问题建模案例：最优截断切割问题5实例应用实例应用2022年6月2日7时04分图图 论论 的的 基基 本本 概概 念念一、一、 图图 的的 概概 念念1图的定义图的定义2顶点的次数顶点的次数 3子图子图二、二、 图图 的的 矩矩 阵阵 表表 示示1 关联矩阵关联矩阵2 邻接矩阵邻接矩阵返回返回2022年6月2日7时
3、04分定义定义有序三元组G=(V,E, )称为一个图图,如果：图的定义图的定义2022年6月2日7时04分定义定义定义定义规定用记号和分别表示图的顶点数和边数.2022年6月2日7时04分2022年6月2日7时04分完全图 返回返回2022年6月2日7时04分顶点的次数（度数）顶点的次数（度数）4()4dv5)(3)(2)(444vdvdvd2022年6月2日7时04分例例 在一次聚会中，认识奇数个人的人数一定是偶数.返回返回2022年6月2日7时04分子图子图返回返回2022年6月2日7时04分关联矩阵关联矩阵注：假设图为简单图返回返回2022年6月2日7时04分邻接矩阵邻接矩阵注：假设图为
4、简单图2022年6月2日7时04分返回返回2022年6月2日7时04分最短路问题及其算法最短路问题及其算法一、一、 基本概念基本概念二、固定起点的最短路二、固定起点的最短路三、每对顶点之间的最短路三、每对顶点之间的最短路返回返回2022年6月2日7时04分基本概念基本概念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路径4521141vevevPvv2022年6月2日7时04分定义定义（）任意两点均有路径的图称为连通图连通图（）起点与终点重合的路径称为圈圈（）连通而无圈的图称为树树返回返回2022年6月2日7时04分固定起点的最短路
5、固定起点的最短路- -DijkstraDijkstra算法算法最短路是一条路径，且最短路的任一段也是最短路 假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路2022年6月2日7时04分Dijkstra算法算法思想vDijkstra算法算法:这是荷兰计算机科学教授Edsger W.Dijkstra(1930-)在1959年发现的一个算法.他在1972年获得计算机协会授予的图灵奖,这是计算机科学中最具声望的奖项. vDijkstra算法算法是求出一个连通加权简单图中从结点a到结点z的最短路.边i,j的权
6、(i,j)0,且结点x的标号为L(x),结束时,L(z)是从x到z的最短路的长度.2022年6月2日7时04分2022年6月2日7时04分算法步骤：算法步骤：（2）更新l v( )、z v( )： vSVS,若l v( )l uW u v( )( , ) 则令l v( )=l uW u v( )( , ),z v( )= u2022年6月2日7时04分 TO MATLAB(road1)2022年6月2日7时04分2022年6月2日7时04分 1 2 34 5 6 7 8返回返回uuuuuuuu2022年6月2日7时04分每对顶点之间的最短路每对顶点之间的最短路- -Floyd算法算法1求距离矩
7、阵的方法求距离矩阵的方法2求路径矩阵的方法求路径矩阵的方法3查找最短路路径的方法查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤返回返回2022年6月2日7时04分算法的基本思想算法的基本思想返回返回2022年6月2日7时04分算法原理算法原理 求距离矩阵的方法求距离矩阵的方法返回返回2022年6月2日7时04分算法原理算法原理 求路径矩阵的方法求路径矩阵的方法)()0()0(ijrR, jrij)0(在建立距离矩阵的同时可建立路径矩阵R 即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径)(D
8、)(R返回返回)(Rv2022年6月2日7时04分i j算法原理算法原理 查找最短路路径的方法查找最短路路径的方法若1)(prij，则点 p1是点 i 到点 j 的最短路的中间点.pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21, 12返回返回2022年6月2日7时04分算法步骤算法步骤Floyd 算法：算法：求任意两点间的最短路(3) 若 k=，停止否则 kk+1，转（） 2022年6月2日7时04分例例 求下图中加权图的任意两点间的距离与路径 TOMATLAB(road2(floyd)5333434331543243332344441,064696024
9、3420256420793570RD所以从 v5到 v1的最短路径为：1435.返回返回2022年6月2日7时04分一、一、 可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、 选选 址址 问问 题题1 中心问题中心问题2 重心问题重心问题返回返回2022年6月2日7时04分可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题 例例 1 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少.
10、 已知该种设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213 使用不同时间设备所需维修费为：使用年限0112233445维修费56811182022年6月2日7时04分2022年6月2日7时04分（3）问题转化为顶点Xb1到Xrk6( )的最短路问题.五年的最优购置费为 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )为顶点Xb1到Xrk6( )的最短路的权.2022年6月2日7时04分返回返回2022年6月2日7时04分 选址问题选址问题- -中心问题中心问题则kv就是要求的建立消防站的地点此点称为图的中心点中心
11、点 TO MATLAB(road3(floyd)2022年6月2日7时04分05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故应将消防站设在v3处. 返回返回2022年6月2日7时04分 选址问题选址问题- -重心问题重心问题返回返回2022年6月2日7时04分图论算法（）图论算法（）中国邮递员问题和中国邮递员问题和问题问
12、题2022年6月2日7时04分邮路问题及邮路问题及问题问题一、中国邮递员问题一、中国邮递员问题二、推销员问题二、推销员问题三、建模案例：最佳灾情巡视路线三、建模案例：最佳灾情巡视路线（一）（一） 欧拉图欧拉图（二）（二） 中国邮递员问题中国邮递员问题（一）哈密尔顿图（一）哈密尔顿图（二）推销员问题（二）推销员问题2022年6月2日7时04分 7 3 1 2 3 4 1 2 4 5 5 6 6 7 8 9割边G的边 是割边的充要条件是 不含在G的圈中 割边的定义割边的定义：设G连通， E(G),若从G中删除边 后，图G- 不连通，则称边 为图G的割边eeeeeevvvvvvveeeeeeeee2
13、022年6月2日7时04分 e3 v1 v2 v3 v4e1e2e4 e5e6欧拉图欧拉图 e3 v1 v2 v3 v4 e1e 2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v12022年6月2日7时04分e3 v1 v2 v3v4e1e2e4 e5e3 v1 v2 v3v 4 e1 e2e4 e5e6欧拉图 非欧拉图返回返回2022年6月2日7时04分中国邮递员问题中国邮递员问题- -定义定义2022年6月2日7时04分中国邮递员问题中国邮递员问题- -算法
14、算法 Fleury算法基本思想算法基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.2022年6月2日7时04分 v7e3 v1v2 v3v4e1 e2e4 e5 v5 e6e6 e 7 e8 e9e102022年6月2日7时04分 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次 解决这类问题的一般方法一般方法是：在一些点对之间在一些点对之间引入重复边（重复边与它平行的边具有相同的引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的权），使原图成为欧拉
15、图，但希望所有添加的重复边的权的总和为最小重复边的权的总和为最小2022年6月2日7时04分v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e92022年6月2日7时04分2022年6月2日7时04分算法步骤：算法步骤：（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对2022年6月2日7时04分例例求右图所示投递区的一条最佳邮递路线1图中有 v4、v7、v8、v9四个奇次顶点用 Floyd 算法求出它们之间的最短路径和距离：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvv
16、dvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv返回返回2022年6月2日7时04分哈密尔顿图哈密尔顿图返回返回2022年6月2日7时04分推销员问题推销员问题- -定义定义 流动推销员需要访问某地区的所有城镇城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题推销员问题 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点每个顶点至少一次的最短闭通路问题2022年6月2日7时04分定义定义在加权图G=(V,E)中，（）权最小的哈密尔顿圈称为最佳最佳H圈圈(Hamilt
17、on圈圈)（）经过每个顶点至少一次的权最小的闭通路闭通路称为最佳推销员回路最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长42022年6月2日7时04分2022年6月2日7时04分推销员问题近似算法：推销员问题近似算法：二边逐次修正法二边逐次修正法：2022年6月2日7时04分例例对以下完备图，用二边逐次修正法求较优H圈2022年6月2日7时04分返回返回2022年6月2日7时04分图论算法（）匹配图论算法（）匹配 匹配问题是运筹学的重要问题之一,也是图论研究的重点内容,它提供了解决“人员分配问题”和“最
18、优分配问题”一种新的思想.定义定义1.设G=是无环图,ME(G),M,若M中任意两条边都不相邻,则称MM是图是图G G的一个匹配的一个匹配.若对图G的任何匹配M ,均有M0)正则二分图,则G有完美匹配.由定理3可知,G有饱和V1的匹配M,再据V1=V2和推论1即知M是完美匹配.推论推论3. 设G是二部划分(V1,V2)的简单二分图，且V1=V2=n，若(G)n/2，则G有完美匹配.2022年6月2日7时04分定理定理4. G有完美匹配O(G-S)S,SV(G),其中O(G-S)是G-S的奇数阶连通分支数目例1.有有n n张纸牌张纸牌, ,每张纸牌的正反两面都写上每张纸牌的正反两面都写上1,2,
19、n1,2,n的某一的某一个数个数, ,证明证明: :如果每个数字恰好出现两次如果每个数字恰好出现两次, ,则这些纸牌一定则这些纸牌一定可以这样摊开可以这样摊开, ,使朝上的面中使朝上的面中1,2,n1,2,n都出现都出现. .证明证明:作一个二分图G=,其中V1=1,2,n，V2=y1,y2,yn表示这n张纸牌.i与yi之间连接的边数等于数i在纸牌yj中出现的次数,这样得到的图G是一个2-正则二分图,因此图G中有完美匹配,设为M=1yi1,2yi2,nyin 则只要把纸牌yi1中的1朝上,yi2中的2朝上,yin的n朝上,这样摊开,这样摊开的纸牌就能使上面中1,2,n都出现.2022年6月2日
20、7时04分例例2.某工厂生产由6种不同颜色的纱布织成的双色布,由该厂所生产的双色布中,每一种颜色至少和其他三种颜色搭配.证明可以挑选出三种不同的双色布,它们含有所有的6种颜色.证明证明:构造图G=,其中V=v1,v2,v3,v4,v5,v6表示6种颜色,工厂生产出一种颜色vi与vj搭配而成的双色布边vi,vjE(G).由题意知,G为简单图,且每个结点的度数至少为3,下证 G中含有一个完美匹配. 今设v1,v2E(G),由于d(v3) 3,所以存在一个不同于v1和v2的顶点vi(4i6),使v3,viE(G),不妨设vi=4,即v3,v4E(G).2022年6月2日7时04分 如果边v5,v6E
21、(G),由于d(v5)3,v1,v2,v3,v4中至少有3个顶点与v5相邻,即v5与边v1,v2,v3,v4中的每一边的某一个端点相邻,不妨设v1,v5E(G)和v3,v5E(G). 对于顶点v6,同样与v1,v2,v3,v4中至少3个顶点相邻,即在v2和v4中至少有一个顶点与v6相邻.如果v2,v6E(G),则边v1,v5,v3,v4,v2,v6是G的一个完美匹配;如果v4,v6E(G),则v1,v2,v3,v5,v4,v6是G的一个完美匹配. 综上所述,G总存在完美匹配,完美匹配中的三条边所对应的三种双色布即为所求.2022年6月2日7时04分最大匹配的生成算法-匈牙利算法定义定义1. 根
22、在x的M交错子图:设M是图G的匹配,x是G中非M饱和点.G中由起点为x的M交错路所能连接的顶点集所导出的G的导出子图称为根在称为根在x的的M交错子图交错子图.定理定理1. 设M是具有二部划分(V1,V2)的二分图G的匹配,xV1是非M饱和点,H是G中根在x的M交错子图的顶点集S=HV1,T=HV2,则:(1)TNG(S);(2)下述三条等价:(a)G中不存在以x为端点的M可增广路;(b)x是H中唯一的非M饱和点;(c) T=NG(S),且T=S-1.(不证)2022年6月2日7时04分匈牙利算法匈牙利算法基本思想基本思想:设G是具有二部划分(V1,V2)的二分图,从图G的任意匹配M开始.若M饱
23、和V1,则M是G的匹配.若M不能饱和V1,则在V1中选择一个非M饱和点x,若G中存在以x为起点的M可增广路P,则M=MP就是比M更大的匹配,利用M代替M,并重复这个过程.若G中不存在以x为起点的M可增广路,则令H是根在x的M交错子图的顶点集,并令S=HV1,T=HV2, 由定理1,T=NG(S),且G中不存在以x为起点的M可增广路,此时称x为检验过的非M饱和点.对V1中其它未检验过的非M饱和点重复该过程,直到V1中的所有非M饱和点全部检验过为止.当整个过程结束时,由于G中不存在M可增广路,从而M为G的最大匹配.2022年6月2日7时04分匈牙利算法步骤匈牙利算法步骤:设设G是具有二部划分是具有
24、二部划分(V1,V2)的二分图的二分图.(1)任给初始匹配任给初始匹配M;(2)若若M饱和饱和V1则结束则结束.否则转否则转(3);(3)在在V1中找一非中找一非M饱和点饱和点x,令令S=x,T=;(4)若若N(S)=T,则停止则停止,否则任选一点否则任选一点y N(S)-T;(5)若若y为为M饱和点转饱和点转(6),否则作求一条从否则作求一条从x到到y的的M可增广路可增广路P,置置M=M P,转转(2)；(6)由于由于y是是M饱和点饱和点,故故M中有一边中有一边y,u,置置S=S u,T=T y,转转(4).2022年6月2日7时04分例1.如图G所示,V1=x1,x2,x3,x4,x5,
25、V2=y1,y2,y3,y4,y5，试求图G的最大匹配.x1, x2 x3 x4 x5y1 y2 y3 y4 y5图图ax1 x2 x3 x4 x5y1 y2 y3 y4 y5图图b2022年6月2日7时04分解:任取初始匹配M=x2y2,x3y3,x5y5,如图(a)中虚线所示.解题过程如下表:MxSTN(S)y N(S)-Ty,u MPx2y2,x3y3,x5y5x1x1y2,y3y2饱和饱和y2,x2x1,x2 y2y1,y2,y3,y4,y5y1非饱非饱和和(x1y2x2y1)x1y2,x2y1,x3y3 x5y5x4x4y2,x3y2饱和饱和y2,x1x4,x1 y2y2,y3y3饱
26、和饱和y3,x3x4,x1,x3y2,y3 y2,y3N(S)=T,停止停止2022年6月2日7时04分因此,M=x1y2,x2y1,x3y3,x5y5即为图G的最大匹配,如图(b)虚线所示.2022年6月2日7时04分 最优匹配最优匹配定义定义1. 最优匹配最优匹配:在加权图中求一个总权最大的完在加权图中求一个总权最大的完美匹配美匹配, ,这种匹配这种匹配称为称为最优匹配最优匹配.定义定义2.已知G是具有二部划分(V1,V2)的完全加权二分图,映射L:V(G)R,满足对G的每条边e=x,y,均有L(x)+L(y)(x,y),其中(x,y)表示边x,y的权,则称则称L为为G的可行顶标的可行顶标
27、. 令令EL=x,y x,y E(G),L(x)+L(y)= (x,y),GL为以为以EL为为边集的边集的G的生成子图的生成子图,则称则称GL为为L等子图等子图.说明说明:可行顶标总可行顶标总是存在的是存在的,例如例如: 212max( , )( )0,y VL xx yVL yyV2022年6月2日7时04分定理定理1. 设设L L是是G G的可行顶标的可行顶标. .若若L L等子图等子图G GL L有完美匹配有完美匹配M,M,则则MM是是G G的最优匹配的最优匹配. . 基于定理基于定理1的在一个加权二分图的在一个加权二分图(Km,n, )中求最优匹配的有中求最优匹配的有效算法效算法Kuh
28、n-munkres算法算法:(1)(1)从任意可行顶标从任意可行顶标( (如平凡标号如平凡标号)L)L开始开始, ,确定确定L L等子图等子图G GL L, ,并且并且在在G GL L中选取匹配中选取匹配M.M.若若MM饱和饱和V V1 1, ,则则MM是完美匹配是完美匹配, ,也即也即MM是最是最优匹配优匹配, ,算法终止算法终止, ,否则转入否则转入(2)(2)步步. .(2)(2)匈牙利算法终止于匈牙利算法终止于S S V V1 1,T ,T V V2 2且使且使N NGLGL(S)=T,(S)=T,计算计算a aL L, ,确定新确定新的可行顶标的可行顶标L,L,并以并以LL替代替代L, L,以以G GLL替代替代G GL L转入转入(1)(1)步步. .2022年6月2日7时04分例例1.已知完全二分图已知完全二分图k5,5,其中其中V1=x1,x2,x3,x4,x5,V2=y1,y2,y3,y4,y5,且且k5,5的权矩阵为的权矩阵为A,求求k5,5的最的最优匹配优匹配.3554122022244100110012133A
