《数学建模培训资料PPT图论模型建模PPT.ppt》由会员分享，可在线阅读，更多相关《数学建模培训资料PPT图论模型建模PPT.ppt（82页珍藏版）》请在三一办公上搜索。
1、图 论 模 型,数学建模培训,图论模型,图论基本概念最短路径算法最小生成树算法遍历性问题5.网络流问题,1 引言,图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来。问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。,当然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图
2、”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。,我们首先通过一些例子来了解网络优化问题。例1 最短路问题（SPPshortest path problem）一名货车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。例2 公路连接问题
3、 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,例3 指派问题（assignment problem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？,上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimiza
4、tion）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化（netwok optimization）问题。,2023/2/10,图的定义,图论中的“图”并不是通常意义下的几何图形或物体的形状图,而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统.,定义1 一个有序二元组(V,E)称为一个图,记为G=(V,E),其中,V称为G的顶点集,V,其元素称为顶点或结点,简称点;E称为G的边集,其元素称为边,它联结V 中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边
5、.如果V=v1,v2,vn是有限非空点集,则称G为有限图或n阶图.,2023/2/10,如果E的每一条边都是无向边,则称G为无向图(如图1);如果E的每一条边都是有向边,则称G为有向图(如图2);否则,称G为混合图.,图1,图2,并且常记,V=v1,v2,vn,|V|=n;E=e1,e2,em(ek=vivj),|E|=m.,称点vi,vj为边vivj的端点.在有向图中,称点vi,vj分别为边vivj的始点和终点.该图称为(n,m)图,2023/2/10,对于一个图G=(V,E),人们常用图形来表示它,称其为图解.凡是有向边,在图解上都用箭头标明其方向.,例如,设V=v1,v2,v3,v4,E
6、=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4,则G=(V,E)是一个有4个顶点和6条边的图,G的图解如下图所示.,2023/2/10,一个图会有许多外形不同的图解,下面两个图表示同一个图G=(V,E)的图解.其中V=v1,v2,v3,v4,E=v1v2,v1v3,v1v4,v2v3,v2v4,v3v4.,这两个图互为同构图,今后将不计较这种外形上的差别,而用一个容易理解的、确定的图解去表示一个图.,2023/2/10,有边联结的两个点称为相邻的点,有一个公共端点的边称为相邻边.边和它的端点称为互相关联.常用d(v)表示图G中与顶点v关联的边的数目,d(v)称为顶点v的度数.对于
7、有向图,还有出度和入度之分.,d(v1)=d(v3)=d(v4)=4,d(v2)=2.,握手定理：,2023/2/10,定义2 若将图G的每一条边e都对应一个实数F(e),则称F(e)为该边的权,并称图G为赋权图(网络),记为G=(V,E,F).,定义3 任意两点均有通路的图称为连通图.定义4 连通而无圈的图称为树,常用T表示树.,2023/2/10,图的矩阵表示,邻接矩阵 邻接矩阵表示了点与点之间的邻接关系.一个n阶图G的邻接矩阵A=(aij)nn,其中,无向图G的邻接矩阵A是一个对称矩阵.,权矩阵 一个n阶赋权图G=(V,E,F)的权矩阵A=(aij)nn,其中,2023/2/10,无向图
8、G的权矩阵A是一个对称矩阵.,2023/2/10,关联矩阵（略）一个有m条边的n阶有向图G的关联矩阵A=(aij)nm,其中,若vi是ej的始点;若vi是ej的终点;若vi与ej不关联.,2023/2/10,一个有m条边的n阶无向图G的关联矩阵A=(aij)nm,其中,若vi与ej关联;若vi与ej不关联.,2023/2/10,2、最短路径算法,定义1 设P(u,v)是赋权图G=(V,E,F)中从点u到v的路径,用E(P)表示路径P(u,v)中全部边的集合,记,则称F(P)为路径P(u,v)的权或长度(距离).,定义2 若P0(u,v)是G 中连接u,v的路径,且对任意在G 中连接u,v的路径
9、P(u,v)都有F(P0)F(P),则称P0(u,v)是G 中连接u,v的最短路.,2023/2/10,重要性质：,若v0 v1 vm 是图G中从v0到vm的最短路,则1km,v0v1 vk 必为G中从v0到vk的最短路.,即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.下面分别介绍两种算法的基本过程.,2023/2/10,Dijkstra算法,求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0从近到远为
10、顺序，依次求得u0到的G各顶点的最短路和距离，直至所有顶点，算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。,2023/2/10,Dijkstra算法,用dij表示两相邻点i与j的距离。若i与j不相邻，令dij=，显然dii=0.用Lsi表示从s点到i点的最短距离。现要求从s点到某一点t的最短路，用Dijkstra算法步骤如下：,1、从s点出发，因Lss=0，将此值标注在s旁的小方框内，表示s已标号。2、从s点出发，找出与s相邻的点中距离最小的一个，设为r，将Lsr=Lss+dsr的值标注在r旁，表明r已标号。3、从已标号的点出发，找出与这些点相邻的所有未标号点p。若
11、有Lsp=minLss+dsp;Lsr+drp,则对p点标号，并将Lsp的值标注在p点旁的小方框内。4、重复第3步，一直到t点得到标号为止。,例 求下图v1点到v7点的最短路.,Foyd算法的基本思想,例 求下图中任意两点间的最短路.,例 设备更新问题,某人购买一台摩托车，准备在今后4年内使用，他可在第1年初购一台新车，连续使用4年，也可于任何一年年末卖掉，于下一年初换一台新车。已知各年初的新车购置见下表1，不同役龄车的使用维护费及年末处理价见表2.要求确定该人使用摩托车的最优更新策略，使4年内用于购买、更换及使用维护的总费用为最省。,2023/2/10,构造有向图，以点-表示各年初（同时也是
12、上一年年末），弧（i，j）旁的数字表示第i年初买新车到第j年初（即第j-1年末）卖掉时的总支出（ij），记成dij.dij等于第i年初的购车费用+用到第j年初支付的使用维护费-按役龄为（j-i-1）-（j-i）年末处理费。,d12=2.5=0.3-2.0=0.8d13=2.5+(0.3+0.5)-1.6=1.7d14=2.5+(0.3+0.5+0.8)-1.3=2.8d15=2.5+(0.3+0.5+0.8+1.2)-1.1=4.2d23=2.6+0.3-2.0=0.9d24=2.6+(0.3+0.5)-1.6=1.8d25=2.6+(0.3+0.5+0.8)-1.3=2.9d34=2.8+0
13、.3-2.0=1.1d35=2.8+(0.3+0.5)-1.6=2.0d45=3.1+0.3-2.0=1.4,用dijkstra算法求图从点-的最短有向路。由图中粗线可知，最优方案有3个。第一年初买新车，年末卖掉再买新车，一直用到第4年末卖掉；第一年初买新车，用两年后于第二年末卖掉再买新车，用两年后第四年末卖掉；第一年初买新车，年末卖掉后再买新车，用一年后即第二年末又卖掉再买新车，再用两年后于第四年末卖掉。每个最优方案总支出均为3.7万元。,2023/2/10,3、最小生成树,由树的定义不难知道,任意一个连通的(n,m)图G适当去掉m-n+1条边后,都可以变成树,这棵树称为图G的生成树.,设T
14、是图G的一棵生成树,用F(T)表示树T中所有边的权数之和,F(T)称为树T的权.一个连通图G的生成树一般不止一棵,图G的所有生成树中权数最小的生成树称为图G的最小生成树.求最小生成树问题有很广泛的实际应用.例如,把n个乡镇用高压电缆连接起来建立一个电网,使所用的电缆长度之和最短,即费用最小,就是一个求最小生成树问题.,最小生成树算法Kruskal 算法,思想：将图中所有边按权值从大到小排列，依次选所剩最小的边加入边集T，只要不和前面加入的边构成回路，直到T中有n-1条边，则T是最小生成树。例题（见黑板）,最小生成树算法Prim算法,不需要对边权进行排序，即可直接在网络图上操作，也可以在边权矩阵
15、上操作，后者适合在计算机上运算。步骤：1、先在G中任取一个节点，并放入T中2、令S=V(G)V(T),其中V(G)、V(T)分别为G与T的节点集。,3、在所有连接V（T）的节点与S的节点的边中，选出权数最小的边（u0,v0），即w(u0,v0)=minw(u,v)uV(T),v S4、将边（u0,v0）取入T中，重复（2）-（4），直至G中节点全部取入T中为止。,边权矩阵上的Prim算法,1、根据网格写出边权矩阵，两点间若没有边，则用表示；2、从v1开始标记，在第一行打，划去第一列；3、从所有打的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在的列，与该列数对应的行打；4、若所有列都划
16、掉，则已找到最小生成树（所有画圈的元素所对应的边）；否则返回第3步。,4、遍历性问题,定义3（割边）：设G连通，eE(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边。,上图中，e就是桥,定理：G的边e是割边的充要条件为：e不含在G的圈中。,2023/2/10,40,定义4设G=(V,E)是连通无向图（）经过G的每边至少一次的闭通路称为巡回（）经过G的每边正好一次的巡回称为欧拉巡回（）存在欧拉巡回的图称为欧拉图（）经过G的每边正好一次的道路称为欧拉道路,定理对于非空连通图G，下列命题等价：（）G是欧拉图（）G无奇次顶点（）G的边集能划分为圈,推论设G是非平凡（大于一个顶点）连通图
17、，则G有欧拉道路的充要条件是G最多只有两个奇次顶点,中国邮递员问题,邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线这就是中国邮递员问题.若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为最佳巡回,中国邮递员问题算法,1.G是欧拉图此时G的任何一个欧拉巡回便是最佳巡回.问题归结为在欧拉图中确定一个欧拉巡回.Fleury算法便解决了这一问题.Fleury算法的基本思想：从任一点出发，每当访问一条
18、边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.,Fleury算法：求欧拉图的欧拉巡回,2.G不是欧拉图,若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小,情形G正好有两个奇次顶点设G正好有两个奇次顶点u和v,求G 的最佳巡回如下：（1）用Dijkstra算法求出奇次顶点u与v之间的最短路径P（）令G*=GP，则G*为欧拉图（）用Fleury算法求出G*的欧拉巡回，这就是G的
19、最佳巡回,情形G有n个奇次顶点（n）Edmonds最小对集算法：基本思想：先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回,算法步骤：（）用Floyd算法求出的所有奇次顶点之间的最短路径和距离（）以G的所有奇次顶点为顶点集（个数为偶数），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对（）在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*（）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回,例求图所示投递区的一条最佳邮递路线
20、,解 图中有v4、v7、v8、v9四个奇次顶点，用Floyd算法求出它们之间的最短路径和距离：,二、推 销 员 问 题,一个旅行售货员想去访问若干城镇，然后回到出发地.给定各城镇之间的距离后，应怎样计划他的旅行路线，使他能对每个城镇恰好经过一次而总距离最小？它可归结为这样的图论问题：在一个赋权完全图中,找出一个最小权的H圈,称这种圈为最优圈.,1、哈密尔顿图,定义1设G=(V,E)是连通无向图（1）经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径，简称H路径.（2）经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或H圈.（3）含H圈的图称为哈密尔顿图或H图,2、推销员问题-定义,流动推
21、销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题,定义2在加权图G=(V,E)中，（）权最小的哈密尔顿圈称为最佳H圈（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈,定理在加权图G=(V,E)中，若对任意x,y,zV，zx,zy,都有w(x,y)w(x,z)+w(z,y)，则图G的最佳H圈也是最佳推销员回路最
22、佳推销员回路问题可转化为最佳H圈问题方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图G=(V,E)，E的每条边(x,y)的权等于顶点x与y在图中最短路的权即：x,yE,w(x,y)=mindG(x,y)定理加权图G的最佳推销员回路的权与G的最佳H圈的权相同.,3、推销员问题近似算法,（）对C重复步骤（），直到条件不满足为止，最后得到的C即为所求.,例1对以下完备图，用二边逐次修正法求较优H圈,5、网络流问题,在我们日常生活中有大量的网络，如电网、水管网、交通运输网、通讯网、生产管理网等。近二三十年来在解决网络方面的有关问题时，网络流理论及其应用起着很大的作用。我们先来研究网络最大流。
23、,网络最大流的有关概念,1、有向图与容量网络 前面研究的都是无向图，但研究流量问题时，如供水管道中水流总是从水厂流向用户，电网中的电流从高压流向低压等。因此网络流要在有向图中进行。,有向图上的连线是规定指向的，称作弧，弧(vi,vj)表明方向从vi指向vj，有向图是点与弧的集合，记作D（V，A）。容量网络是指对网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，记为C(vi,vj),或简写为Cij.在容量网络中通常规定一个发点和一个收点。网络中既非发点又非收点的其他点称为中间点。,网络最大流是指网络中从发点到收点之间允许通过的最大流量。对有多个发点和收点的网络，可另外虚设一个
24、总发点和总收点，并将其与各发点收点连接起来，就可转换为只含一个发点和一个收点的网络。,2、流与可行流,流：加在网络各条弧上的一组负载量。对加在弧（vi,vj）上的负载量记作f(vi,vj),简记为fij.若网络上所有的fij=0，这个流称为零流。,可行流：称满足以下条件的一组流为可行流：（1）容量限制条件 对所有弧 0f(vi,vj)C(vi,vj)(2)中间点平衡条件：流入量=流出量所谓最大流问题就是在容量网络中,寻找流量最大的可行流.。,2、割和流量,割：将容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。割的容量是组成它的集合中各弧容量之和，用c(v,v-)表示。,3、最大流最小割定理,增广链：假设有向网络上有流f，u是st的一条链，若u满足：1、前向弧u+上有fijcij2、后向弧u-上有fij0则这条链叫相对于流f的增广链。,当有增广链存在时，找出再令,定理1：流f*是最大流当且仅当网络中没有关于f*的增广链。定理2：在网络st的最大流量等于它的最小割集的容量。,4、求网络最大流的标号算法,
