最短路与最大流

2014年数学建模暑期培训——图论模型主讲教师：陈六新联系方式：13983837287图论问题的起源18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块，它们通过七座桥相互连接，如下图。当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”SNAB七桥问题的分析•七桥问题看起来不难，很多人都想试一试，但没有人找到答案。后来有人写信告诉了当时的著名数学家欧拉。千百人的失败使欧拉猜想，也许那样的走法根本不可能。1876年，他证明了自己的猜想。•Euler把南北两岸和四个岛抽象成四个点，将连接这些陆地的桥用连接相应两点的一条线来表示，就得到如下一个简图:SNAB图的作用图是一种表示工具。改变问题的描述方式，往往是创造性的启发式解决问题的手段。一种描述方式就好比我们站在一个位置和角度观察目标，有的东西被遮挡住了，但如果换一个位置和角度，原来隐藏着的东西就可能被发现。采用一种新的描述方式，可能会产生新思想。图论中的图提供了一种直观，清晰表达已知信息的方式。它有时就像小学数学应用题中的线段图一样，能使我们用语言描述时未显示的或不易观察到的特征、关系，直观地呈现在我们面前，帮助我们分析和思考问题，激发我们的灵感。图的广泛应用图的应用是非常广泛的，在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络，如河道网、灌溉网、管道网、公路网、铁路网、电话线网、计算机通讯网、输电线网等等。还有许多看不见的网络，如各种关系网，像状态转移关系、事物的相互冲突关系、工序的时间先后次序关系等等，这些网络都可以归结为图论的研究对象——图。其中存在大量的网络优化问题需要我们解决。还有象生产计划、投资计划、设备更新等问题也可以转化为网络优化的问题。基本的网络优化问题基本的网络优化问题有：最短路径问题、最小生成树问题、最大流问题和最小费用问题。图论作为数学的一个分支，已经有有效的算法来解决这些问题。当然这当中的有些问题也可以建立线性规划的模型，但有时若变量特别多，约束也特别多，用线性规划的方法求解效率不高甚至不能在可忍受的时间内解决。而根据这些问题的特点，采用网络分析的方法去求解可能会非常有效。例如，在1978年，美国财政部的税务分析部门在对卡特尔税制改革做评估的过程中，就有一个100000个约束以上，25000000个变量的问题，若用普通的线性规划求解，预计要花7个月的时间。他们利用网络分析的方法，将其分解成6个子问题，利用特殊的网络计算机程序，花了大约7个小时问题就得到了解决。目的内容2.会用MATLAB软件求最短路与最优匹配1.了解最短路与最优匹配的算法及其应用1.图论的基本概念2.最短路问题及其算法3.最短路的应用5.建模案例：最优截断切割问题6.实验作业4.最优匹配及算法图论的基本概念一、图的概念1.图的定义2.顶点的次数3.子图二、图的矩阵表示1.关联矩阵2.邻接矩阵返回定义有序三元组𝐺=(𝑉,𝐸,Ψ)称为一个图，如果：[1]12{,,,}nVvvv是有限非空集，V称为顶点集，其中的元素叫图G的顶点.[2]E称为边集，其中的元素叫图G的边.[3]是从边集E到顶点集V中的有序或无序的元素偶对构成集合的映射，称为关联函数.例1设(,,)GVE，其中124{,,,}Vvvv125{,,,}Eeee112213314414544(),(),(),(),()evvevvevvevvevv.G的图解如图图的定义定义在图G中，与V中的有序偶(vi，vj)对应的边e，称为图的有向边（或弧），而与V中顶点的无序偶vivj相对应的边e，称为图的无向边.每一条边都是无向边的图，叫无向图；每一条边都是有向边的图，称为有向图；既有无向边又有有向边的图称为混合图.定义若将图G的每一条边e都对应一个实数w(e)，则称w(e)为边的权，并称图G为赋权图.规定用记号和分别表示图的顶点数和边数.常用术语：（１）端点相同的边称为环．（２）若一对顶点之间有两条以上的边联结，则这些边称为重边（或平行边）．（３）有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边．（４）边和它的端点称为互相关联的．（５）既没有环也没有平行边的图，称为简单图．（６）任意两顶点都相邻的简单图，称为完备图，记为Kn，其中n为顶点的数目．(7)若V=XY，XY=，且X中任两顶点不相邻，Y中任两顶点不相邻，则称G为二元图（或二分图）；若X中每一顶点皆与Y中一切顶点相邻，则G称为完备二元图，记为Km,n，其中m,n分别为X与Y的顶点数目．返回完全图二分图完全二分图顶点的次数定义（１）在无向图中，与顶点v关联的边的数目（环算两次）称为v的次数（或度数），记为()dv．（２）在有向图中，从顶点v引出的边的数目称为v的出度，记为()dv＋，从顶点v引入的边的数目称为v的入度，记为()dv－，()dv=()dv＋+()dv－称为v的次数．4()4dv5)(3)(2)(444vdvdvd定理１()()2()vVGdvEG推论１任何图中奇次顶点的总数必为偶数．例在一次聚会中，认识奇数个人的人数一定是偶数。返回子图定义设图G=(V,E,),G1=(V1,E1,1)(1)若V1V，E1E,且当eE1时，1(e)=(e),则称G1是G的子图．特别的，若V1=V，则G1称为G的生成子图．(2)设V1V，且V1，以V1为顶点集、两个端点都在V1中的图G的边为边集的图G的子图，称为G的由V1导出的子图，记为G[V1].(3)设E1E,且E1,以E1为边集,E1的端点集为顶点集的图G的子图,称为G的由E1导出的子图,记为G[E1].GG[{v1,v4,v5}]G[{e1,e2,e3}]返回关联矩阵对无向图Ｇ，其关联矩阵Ｍ＝)(ijm，其中：10ijijijvemve若与相关联若与不关联M=43215432110110011000101110001vvvveeeee对有向图Ｇ，其关联矩阵Ｍ＝)(ijm，其中：不关联与若的终点是若的起点是若jijijiijevevevm011注：假设图为无向简单图返回邻接矩阵对无向图Ｇ，其邻接矩阵)(ijaA，其中：不相邻与若相邻与若jijiijvvvva01注：假设图为简单无向图A=432143210111101011011010vvvvvvvv对有向图Ｇ＝（Ｖ，Ｅ），其邻接矩阵)(ijaA，其中：EvvEvvajijiij），若（），若（01对有向赋权图Ｇ，其邻接矩阵)(ijaA，其中：EvvjiwEvvwajiijjiijij),(0,),(若若为其权且若无向赋权图的邻接矩阵可类似定义．A=4321432105375083802720vvvvvvvv返回最短路问题及其算法一、基本概念二、固定起点的最短路三、每对顶点之间的最短路返回基本概念通路44112544141vevevevevWvv道路4332264521141vevevevevevTvv路径4521141vevevPvv定义１在无向图G=(V,E,)中：（１）顶点与边相互交错且iiivve1)((i=1,2,…,k)的有限非空序列)(12110kkkvevevevw称为一条从0v到kv的通路（链），记为kvvW0（２）边不重复但顶点可重复的通路称为道路（迹），记为kvvT0（３）边与顶点均不重复的通路称为路径（路），记为kvvP0定义２　（１）任意两点均有路径的图称为连通图．　　　　（２）起点与终点重合的路径称为圈．　　　　（３）连通而无圈的图称为树．定义３（１）设(,)Puv是赋权图G中从u到v的路径，则称)()()(PEeewPw为路径P的权．(2)在赋权图G中，从顶点u到顶点v的具有最小权的路(,)Puv，称为u到v的最短路．返回固定起点的最短路最短路是一条路径，且最短路的任一段也是最短路。假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树。因此，可采用树生长的过程来求指定顶点到其余顶点的最短路。62341587Dijkstra算法：求G中从顶点0u到其余顶点的最短路.设G为赋权有向图或无向图，G边上的权均非负．对每个顶点，定义两个标记（lv()，zv()），其中:lv()：表从顶点0u到v的一条路的权．zv()：v的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终lv()为从顶点0u到v的最短路的权．S：具有永久标号的顶点集输入:G的带权邻接矩阵),(vuw算法步骤：（１）赋初值：令S＝{u0},lu()0=0\vSVS,令lv()=Wuv(,)0,zv()=u0uu0（3）设v*是使lv()取最小值的S中的顶点，则令S=S∪{v*}，uv*（4）若Sφ，转（2），否则，停止.用上述算法求出的lv()就是u0到v的最短路的权，从v的父亲标记)(vz追溯到u0,就得到u0到v的最短路的路线.（2）更新lv()、zv()：vSVS\,若lv()luWuv()(,)则令lv()=luWuv()(,),zv()=u例求下图从顶点u1到其余顶点的最短路．先写出带权邻接矩阵：03064093021509701608120W因G是无向图，故W是对称矩阵．TOMATLAB(road1))(iul迭代次数1u2u3u4u5u6u7u8u１2345678０２１８281083108610127101291212最后标记:)(vl)(vz0217369121u1u1u6u2u5u4u5u03064093021509701608120WluWuv()(,))(iul1u2u3u4u5u6u7u8u最后标记:)(vl)(vz0217369121u1u1u6u2u5u4u5u12345678返回uuuuuuuu每对顶点之间的最短路(二)算法原理1.求距离矩阵的方法2.求路径矩阵的方法3.查找最短路路径的方法（一）算法的基本思想（三）算法步骤返回算法的基本思想直接在图的带权邻接矩阵中用插入顶点的方法依次构造出个矩阵D(1)、D(2)、…、D()，使最后得到的矩阵D()成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径．返回nnnnnnnnnnnnnndddddddddddddddddddddddddddddddddddddddddddddddddD654321666656463626155655545352514464544434241336353433323122625242322211161514131211算法原理——求距离矩阵的方法把带权邻接矩阵W作为距离矩阵的初值，即D(0)=)()0(ijd=W（１）D(1)=)()1(ijd，其中)0(1)0()1(,min{iijijddd})0(1jd)1(ijd是从vi到vj的只允许以v1作为中间点的路径中最短路的长度．（2）D(2)=)()2(ijd，其中)1(2)1()2(,min{iijijddd})1(2jd)2(ijd是从vi到vj的只允许以v1、v2作为中间点的路径中最短路的长度．…（3）D(ν)=)()(ijd，其中)1()1()(,min{iijijddd})1(jd)(ijd是从vi到vj的只允许以v1、v2、…、v作为中间点的路径中最短路的长度．即是从vi到vj中间可插入任何顶点的路径中最短路的长，因此D(ν)即是距离矩阵．