数模培训资料课件

全国数学建模竞赛培训这是一场艰苦的战役。需要不怕苦和不怕累的精神，要有坚忍不拔的毅力。8/8/2023全国数学建模竞赛培训这是一场艰苦的战役。需要不怕苦和1可能面临酷暑、内容多、强度大的困难。8/8/2023可能面临酷暑、内容多、强度大的困难。7/29/20232数学建模暑期培训纪律不允许缺课，迟到和早退的现象发生。每一个队每一次培训或讲评，必须是三人到齐。教练会对每一次活动考勤，并与相关学院联系，对缺课学生予以相应处罚。8/8/2023数学建模暑期培训纪律不允许缺课，迟到和早退的现象发生。7/23图论算法参考教材：数学建模与数学实验（赵静、但琦编）数学建模导论（陈理荣编）图论及其算法（殷剑宏、吴开亚编）集合论与图论（耿素云编）8/8/2023图论算法参考教材：7/29/20234图论算法１.最短路问题２.中国邮递员问题和ＴＳＰ问题３.匹配8/8/2023图论算法１.最短路问题7/29/20235图论算法（１）－最短路问题1．图论的基本概念2．最短路问题及其算法3．最短路的应用4．建模案例：最优截断切割问题5．实例应用8/8/2023图论算法（１）－最短路问题1．图论的基本概念2．6图论的基本概念一、图的概念1．图的定义2．顶点的次数

3．子图二、图的矩阵表示1．关联矩阵2．邻接矩阵返回8/8/2023图论的基本概念一、图的概念1．图的定义27定义有序三元组G=(V,E,)称为一个图,如果：图的定义8/8/2023定义有序三元组G=(V,E,)称为一个图,如果：8定义定义8/8/2023定义定义7/29/202398/8/20237/29/202310返回8/8/2023返回7/29/202311顶点的次数（度数）8/8/2023顶点的次数（度数）7/29/202312例

在一次聚会中，认识奇数个人的人数一定是偶数.返回8/8/2023例在一次聚会中，认识奇数个人的人数一定是偶数.返回7/13子图返回8/8/2023子图返回7/29/202314关联矩阵注：假设图为简单图返回8/8/2023关联矩阵注：假设图为简单图返回7/29/202315邻接矩阵注：假设图为简单图8/8/2023邻接矩阵注：假设图为简单图7/29/202316返回8/8/2023返回7/29/202317最短路问题及其算法一、基本概念二、固定起点的最短路三、每对顶点之间的最短路返回8/8/2023最短路问题及其算法一、基本概念二、固定起点的最短路三、每对18基本概念8/8/2023基本概念7/29/202319返回8/8/2023返回7/29/202320固定起点的最短路-Dijkstra算法最短路是一条路径，且最短路的任一段也是最短路．假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树．因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．8/8/2023固定起点的最短路-Dijkstra算法最短路是一条路径，且最21Dijkstra算法思想Dijkstra算法:这是荷兰计算机科学教授EdsgerW.Dijkstra(1930-)在1959年发现的一个算法.他在1972年获得计算机协会授予的图灵奖,这是计算机科学中最具声望的奖项.Dijkstra算法是求出一个连通加权简单图中从结点a到结点z的最短路.边{i,j}的权(i,j)>0,且结点x的标号为L(x),结束时,L(z)是从x到z的最短路的长度.8/8/2023Dijkstra算法思想Dijkstra算法:这是荷兰计算机228/8/20237/29/202323算法步骤：8/8/2023算法步骤：7/29/202324

TOMATLAB(road1)8/8/2023TOMATLAB(road1)7/29/2023258/8/20237/29/202326

12

34

5

6

7

8返回8/8/202312345678返回7/227每对顶点之间的最短路-Floyd算法1．求距离矩阵的方法2．求路径矩阵的方法3．查找最短路路径的方法（一）算法的基本思想（三）算法步骤返回8/8/2023每对顶点之间的最短路-Floyd算法1．求距离矩阵的方法2．28算法的基本思想返回8/8/2023算法的基本思想返回7/29/202329算法原理——求距离矩阵的方法返回8/8/2023算法原理——求距离矩阵的方法返回7/29/202330算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．返回)(nR8/8/2023算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径31i

j算法原理——

查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：返回8/8/2023ij算法原理——查找最短路路径的方法pkp2p1p3q32算法步骤8/8/2023算法步骤7/29/202333

TOMATLAB(road2(floyd))返回

8/8/2023TOMATLAB(road2(floyd))返回7/34一、可化为最短路问题的多阶段决策问题二、选址问题1．中心问题2．重心问题返回8/8/2023一、可化为最短路问题的多阶段决策问题二、选址问题135可化为最短路问题的多阶段决策问题8/8/2023可化为最短路问题的多阶段决策问题7/29/2023368/8/20237/29/2023378/8/20237/29/202338返回8/8/2023返回7/29/202339

选址问题--中心问题

TOMATLAB(road3(floyd))8/8/2023选址问题--中心问题TOMATLAB(road340S(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处.返回8/8/2023S(v1)=10,S(v2)=7,S(v3)=6,S(41

选址问题--重心问题返回8/8/2023选址问题--重心问题返回7/29/202342图论算法（２）－中国邮递员问题和ＴＳＰ问题8/8/2023图论算法（２）7/29/202343邮路问题及ＴＳＰ问题一、中国邮递员问题二、推销员问题三、建模案例：最佳灾情巡视路线（一）欧拉图（二）中国邮递员问题（一）哈密尔顿图（二）推销员问题8/8/2023邮路问题及ＴＳＰ问题一、中国邮递员问题二、推销员问题三、建模44

7

3

1

2

3

4

1

2

4

5

5

6

6

7

8

9割边G的边是割边的充要条件是不含在G的圈中．

割边的定义：设G连通，E(G),若从G中删除边后，图G-{}不连通，则称边为图G的割边．8/8/2023731234124556645

e3

v1

v2

v3

v4e1e2e4

e5e6欧拉图

e3

v1

v2

v3

v4

e1e

2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v18/8/2023e3v1v2v3v4e1e2e4e5e6欧拉图46e3

v1

v2

v3v4e1e2e4

e5e3

v1

v2

v3v

4

e1

e2e4

e5e6欧拉图非欧拉图返回8/8/2023e3v1v2v3v4e1e2e4e5e3v147中国邮递员问题-定义8/8/2023中国邮递员问题-定义7/29/202348中国邮递员问题-算法

Fleury算法基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.8/8/2023中国邮递员问题-算法Fleury算法基本思想：从任49

v7e3

v1v2

v3v4e1

e2e4

e5

v5

e6e6

e7

e8

e9e108/8/2023v7e3v1v2v3v4e1e2e4e5v550若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．

8/8/2023若G不是欧拉图，则G的任何一个巡回经过某些边必51v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e98/8/2023v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8528/8/20237/29/202353（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．8/8/2023（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．754返回8/8/2023返回7/29/202355哈密尔顿图返回8/8/2023哈密尔顿图返回7/29/202356推销员问题-定义流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题．若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题．8/8/2023推销员问题-定义流动推销员需要访问某地区的所有城57定义在加权图G=(V,E)中，（１）权最小的哈密尔顿圈称为最佳H圈(Hamilton圈)．（２）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路．一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈．H回路，长22最佳推销员回路，长48/8/2023定义在加权图G=(V,E)中，一般说来，最佳哈588/8/20237/29/202359推销员问题近似算法：二边逐次修正法：8/8/2023推销员问题近似算法：二边逐次修正法：7/29/202360例对以下完备图，用二边逐次修正法求较优H圈．8/8/2023例对以下完备图，用二边逐次修正法求较优H圈．7/29/2061返回8/8/2023返回7/29/202362图论算法（３）－匹配

匹配问题是运筹学的重要问题之一,也是图论研究的重点内容,它提供了解决“人员分配问题”和“最优分配问题”一种新的思想.定义1.设G=<V,E>是无环图,ME(G),M,若M中任意两条边都不相邻,则称M是图G的一个匹配.若对图G的任何匹配M’,均有M’<M,则称M是图G的最大匹配,记作’(G).定义2.设M是图G的匹配,G中与M中的边关联的顶点称为M饱和点.若图G的顶点都是M饱和,则称为G的完美匹配.8/8/2023图论算法（３）－匹配匹配问题是运筹学的重要问题之63说明:(1)完美匹配是最大匹配,反之未然;(2)匹配的定义与边的方向无关,故匹配是针对无向图而言.定义3.(可增广路):设M是图G的匹配,P是G的一条路,且在P中,M的边和E(G)-M的边交替出现,则称P是G的一条交错路.若M交错路P的两个端点为M非饱和点,则称P为M可增广路.例1.求下图G的一条交错路和一条可增广路.623415878/8/2023说明:(1)完美匹配是最大匹配,反之未然;62341587764匹配的几个性质定理定理1.设M1和M2是图G的两个不同匹配,由M1M2导出的G的边导出子图,记作H,则H的任意连通分支是下列情况之一:(1)边在M1和M2中交错出现的偶圈.(2)边在M1和M2中交错出现的路.定理2.M是图G的最大匹配,当且仅当G中不存在M可增广路.定义:设S是图G的任意顶点子集,G中与S的顶点邻接的所有顶点的集合,称为S的邻集,记做NG(S).8/8/2023匹配的几个性质定理定理1.设M1和M2是图G的两个不同匹配,65定理3(Hall定理,1935)设G是有二部划分(V1,V2)的二分图,则G含有饱和V1的每个顶点的匹配M的充要条件是,对SV1,有N(S)S.推论1具有二部划分(V1,V2)的二分图G有完美匹配V1=V2,且对SV1(或V2),有N(S)S.推论2.

设G是k(>0)正则二分图,则G有完美匹配.由定理3可知,G有饱和V1的匹配M,再据V1=V2和推论1即知M是完美匹配.推论3.设G是二部划分(V1,V2)的简单二分图，且V1=V2=n，若(G)n/2，则G有完美匹配.8/8/2023定理3(Hall定理,1935)设G是有二部划分(V1,V266定理4.

G有完美匹配O(G-S)S,SV(G),其中O(G-S)是G-S的奇数阶连通分支数目例1.有n张纸牌,每张纸牌的正反两面都写上1,2,…n的某一个数,证明:如果每个数字恰好出现两次,则这些纸牌一定可以这样摊开,使朝上的面中1,2,…n都出现.证明:作一个二分图G=<V1,V2,E>,其中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都出现.8/8/20237/29/202367例2.某工厂生产由6种不同颜色的纱布织成的双色布,由该厂所生产的双色布中,每一种颜色至少和其他三种颜色搭配.证明可以挑选出三种不同的双色布,它们含有所有的6种颜色.证明:构造图G=<V,E>,其中V={v1,v2,v3,v4,v5,v6}表示6种颜色,工厂生产出一种颜色vi与vj搭配而成的双色布边{vi,vj}E(G).由题意知,G为简单图,且每个结点的度数至少为3,下证G中含有一个完美匹配.今设{v1,v2}E(G),由于d(v3)≥3,所以存在一个不同于v1和v2的顶点vi(4≤i≤6),使{v3,vi}E(G),不妨设vi=4,即{v3,v4}E(G).8/8/2023例2.某工厂生产由6种不同颜色的纱布织成的双色布,由该7/268

如果边{v5,v6}E(G),由于d(v5)≥3,v1,v2,v3,v4中至少有3个顶点与v5相邻,即v5与边{v1,v2},{v3,v4}中的每一边的某一个端点相邻,不妨设{v1,v5}E(G)和{v3,v5}E(G).对于顶点v6,同样与v1,v2,v3,v4中至少3个顶点相邻,即在v2和v4中至少有一个顶点与v6相邻.如果{v2,v6}E(G),则边{v1,v5},{v3,v4},{v2,v6}是G的一个完美匹配;如果{v4,v6}E(G),则{v1,v2},{v3,v5},{v4,v6}是G的一个完美匹配.综上所述,G总存在完美匹配,完美匹配中的三条边所对应的三种双色布即为所求.8/8/2023如果边{v5,v6}E(G),由于d(v5)≥3,v69最大匹配的生成算法-匈牙利算法定义1.根在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=H∩V1,T=H∩V2,则:(1)TNG(S);(2)下述三条等价:(a)G中不存在以x为端点的M可增广路;(b)x是H中唯一的非M饱和点;(c)T=NG(S),且T=S-1.(不证)8/8/2023最大匹配的生成算法-匈牙利算法定义1.根在x的M交错子图:70匈牙利算法基本思想:设G是具有二部划分(V1,V2)的二分图,从图G的任意匹配M开始.若M饱和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的最大匹配.8/8/2023匈牙利算法基本思想:设G是具有二部划分(V1,V2)的二分图71匈牙利算法步骤:设G是具有二部划分(V1,V2)的二分图.(1)任给初始匹配M;(2)若M饱和V1则结束.否则转(3);(3)在V1中找一非M饱和点x,令S={x},T=;(4)若N(S)=T,则停止,否则任选一点yN(S)-T;(5)若y为M饱和点转(6),否则作求一条从x到y的M可增广路P,置M=MP,转(2)；(6)由于y是M饱和点,故M中有一边{y,u},置S=S{u},T=T{y},转(4).8/8/2023匈牙利算法步骤:7/29/202372例1.如图G所示,V1={x1,x2,x3,x4,x5},V2={y1,y2,y3,y4,y5}，试求图G的最大匹配.x1,,x2x3x4x5y1y2y3y4y5图ax1x2x3x4x5y1y2y3y4y5图b8/8/2023例1.如图G所示,V1={x1,x2,x3,x4,x5},73解:任取初始匹配M={x2y2,x3y3,x5y5},如图(a)中虚线所示.解题过程如下表:MxSTN(S)yN(S)-T{y,u}MP{x2y2,x3y3,x5y5}x1{x1}{y2,y3}y2饱和{y2,x2}{x1,x2}{y2}{y1,y2,y3,y4,y5}y1非饱和(x1y2x2y1){x1y2,x2y1,x3y3x5y5}x4{x4}{y2,x3}y2饱和{y2,x1}{x4,x1}{y2}{y2,y