《图论专题课件》由会员分享，可在线阅读，更多相关《图论专题课件（76页珍藏版）》请在金锄头文库上搜索。
1、数学建模,图论方法专题,内容,一图论的基本概念,二最短路,三行遍性问题,四网络流,图论的基本概念,问题1:哥尼斯堡七桥问题 能否从任一陆地出发通过每座桥恰好回到出发点?,欧拉指出:如果每块陆地所连接的桥都是偶数座,则从任一陆地出发,必能通过恰好一次而回到出发地.,问题2:哈密顿圈(环球旅行游戏) 十二面体的20个顶点代表世界上20个城市,能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点?,问题3:四色问题 对任何一张地图进行着色,两个共同边界的国家染不同的颜色,则只需要四种颜色就够了.,问题4:关键路径问题 一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一
2、架电视机,都要包括许多工序,这些工序相互约束,只有在某些工序完成之后,一个工序才能开始,即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够完成每个工序所需要的时间. 这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个?,一.图的基本概念,2.常用术语,无向图 有向图 顶点的度 子图 网络图,用图论思想求解 例1 一摆渡人欲将一只狼,一头羊,一蓝菜从河西渡过河到河东,由于船小,一次只能带一物过河,并且,狼与羊,羊与菜不能独处,给出渡河办法.,解: 用四维0-1向量表示(人,狼,羊,菜)的在西岸状态,(在西岸则分量取1,否则取0.
3、) 共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)转移到(0,0,0,0)?,方法 : 从状态(1,1,1,1)开始,沿关联边到达没有到达的相邻顶点,到(0,0,0,0)终止,得到有向图即是.,邻接矩阵,A=,3. 图 的 矩 阵 表 示,A=,1.固定起点的最短路,二.最 短 路,算法步骤：,TO MATLAB(road1),1,2,3,4,5,6,7
4、,8,2.每对顶点之间的最短路,例 求下图中加权图的任意两点间的距离与路径,算法的基本思想,算法原理 求距离矩阵的方法,算法原理 求路径矩阵的方法,在建立距离矩阵的同时可建立路径矩阵R,即当 k被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径,算法原理 查找最短路路径的方法,pk,p2,p1,p3,q1,q2,qm,则由点i到j的最短路的路径为：,算法步骤,插入点 v1，得：,插入点 v3，得：,插入点 v4，得：,插入点 v5，得：,插入点 v6，得：,故从v5到v2的最短路为8,由v6向v5追溯:,由v6向v2追溯:,所以从到的最短路
5、径为：,插入点 v2，得：,3.最 短 路 的 应 用,选址问题-中心问题,TO MATLAB (road3(floyd),S(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5,S(v3)=6,故应将消防站设在v3处.,选址问题-重心问题,三.行遍性问题,设M是G的一个匹配，若G的每个顶点都是M饱和的， 则称M是G的理想匹配.,G的边 是割边的充要条件是 不含在G的圈中,割边的定义：设G连通， E(G),若从G中删除边 后，图G- 不连通，则称边 为图G的割边,欧 拉 图,巡回：v1e1v2e2v3e5v1e4v4
6、e3v3e5v1,欧拉道路：v1e1v2e2v3e5v1e4v4e3v3,欧拉巡回： v1e1v2e2v3e5v1e4v4e3v3e6v1,定义 设G=(V,E)是连通无向图 （）经过G的每边至少一次的闭通路称为巡回 （）经过G的每边正好一次的巡回称为欧拉巡回 （）存在欧拉巡回的图称为欧拉图 （）经过G的每边正好一次的道路称为欧拉道路,欧拉图,非欧拉图,定理 对于非空连通图G，下列命题等价： （）G是欧拉图 （）G无奇次顶点 （）G的边集能划分为圈,推论 设G是非平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点,中国邮递员问题-定义,邮递员发送邮件时，要从邮局出发，经过他投递范围内
7、的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线这就是中国邮递员问题.,若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为最佳巡回,中国邮递员问题-算法,Fleury算法基本思想：从任一点出发，每当访问 一条边时，先要进行检查如果可供访问的边不只 一条，则应选一条不是未访问的边集的导出子图的 割边作为访问边，直到没有边可选择为止.,1. G是欧拉图,此时G的任何一个欧拉巡回便是最佳巡回问题归结为在欧拉图中确定一个欧拉巡回,Fleury算法：
8、求欧拉图的欧拉巡回.,Fleury算法算法步骤： （）任选一个顶点v0，令道路w0=v0. （）假定道路wi=v0e1v1e2eivi已经选好，则从Ee1,e2,ei 中选一条边ei+1，使： a）ei+1与vi相关联 b）除非不能选择，否则一定要使ei+1不是Gi=GE-e1,e2,ei 的割边 （）第（）步不能进行时就停止,若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次,解决这类问题的一般方法是：在一些点对之间 引入重复边（重复边与它平行的边具有相同的权）, 使原图成为欧拉图，但希望所有添加的重复边的 权的总和为最小,2. G不是欧拉图,情形 G正好有两个奇次顶点,（）用Dijk
9、stra算法求出奇次顶点u与v之间的最短路径P,（）令G*=G,P，则G*为欧拉图.,（）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回,情形 G有n个奇次顶点（n,）,Edmonds最小对集算法：,基本思想：,先将奇次顶点配对，要求最佳配对，即点对之间 距离总和最小再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回,（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对,算法步骤：,（）用Floyd算法求出所有奇次顶点之间的最短路径和距离,（）以G的所有奇次顶点为顶点集（偶数个元素），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G
10、1,（）在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*,（）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回,例求右图所示投递区的一条最佳邮递路线,1图中有v4、v7、v8、v9四个奇次顶点,用Floyd算法求出它们之间的最短路径和距离：,2以v4、v7、v8、v9为顶点，他们之间的距离为边权构造完备图G1,3求出G1的最小权完美匹配M=(v4,v7),(v8,v9).,4在G中沿v4到v7的最短路径添加重复边，沿v8到v9的最短路径v8v9添加重复 边，得欧拉图G2G2中一条欧拉巡回就是G的一条最佳巡回其权值为64,哈 密 尔 顿 图,定义 设G=(V,E)是连通无向图. （1
11、） 经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径 （2） 经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或H圈 （）含H圈的图称为哈密尔顿图或H图,推销员问题-定义,流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题,若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题,定义 在加权图G=(V,E)中， （）权最小的哈密尔顿圈称为最佳H圈 （）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路,一般说来，最佳哈密尔顿圈不一定是最佳推销
12、员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈,H回路，长22,最佳推销员回路，长4,所以：,汉密尔顿回路是要找经过G的每个顶点正好一次的圈，其中G=(V,E)是连通无向图，无权。 推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题 旅行推销员问题（旅行商问题）=赋权汉密尔顿回路最小化问题，具体指：在n个点及n个点两两之间的距离（或权数），求一条回路，使得经过所有点且经过每个点仅一次。,最佳推销员回路问题可转化为最佳H圈问题方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图G=(V,E)，E的每条边(x,y)的权等于顶点x与y在图中最短路的权即：,定理加权图G的
13、最佳推销员回路的权与G的最佳H圈的权相同,推销员问题近似算法：二边逐次修正法：,(1)任取初始H圈: C0=v1,v2,vi, ,vj,vn,v1,(2)对所有的i ,j，1i+1jn,若 w(vi, vj)+w(vi+1,vj+1) w(vi,vi+1)+w(vj,vj+1) 则在C0中删去边(vi,vi+1)和(vj,vj+1)而加入边(vi, vj)和(vi+1,vj+1)，形成 新的H圈C，即 C= v1,v2, ,vi,vj , vj-1, , vi+1,vj+1, ,vn,v1,(3)对C重复步骤(2)，直到条件不满足为止，最后得到的C即为所求,例 对以下完备图，用二边逐次修正法求
14、较优H圈,返回,三. 网络流问题,基本概念,给定一个有向图G=(V,E)，其中仅有一个点的入次为零称为发点(源) ,记为Vs,仅有一个点的出次为零称为汇点，记为Vt，其余点称为中间点。,对于G中的每一个弧(vi,vj),相应地给一个数Cij，称为弧(vi,vj)的容量。我们把这样的图称为网络（或容量网络），记为G=(V,E,C).,最大流问题,所谓网络上的流，是指定义在弧集E上的函数f=f(vi,vj)，并称f(vi,vj) 为弧(vi,vj)上的流量，并记为fij。,标示方式：每条边上标示两个数字，第一个是容量，第二是流量。,可行流、可行流的流量、最大流,可行流是指满足如下条件的流:,(2)
15、平衡条件: 对中间点,有:,对收点Vt与发点Vs,有:,(1)容量限制条件:对G中每条边(vi,vj),有:,可行流总是存在的.,所谓最大流问题就是在容量网络中寻找流量最大的可行流.,一个流f=fij,当fii=Cij,则称f对边(vi,vj)是饱和的,否则称f对边(vi,vj)不饱和的.,给定容量网络G=(V,A,E)，若点集V被剖分为两个非空集合V1和V2,使vsV1,vt V2,则把弧集(V1,V2)称为割集。割集不是唯一的。,割集(V1,V2)中所有起点在V1,终点在V2的边的容量的和称为割集容量。,在所有割集中，割集容量最小的割集称为最小割集。,术语: 饱和弧、非饱和弧、零流弧、非零弧、 前向弧、后向弧,设f是一个可行流， 是从vs到vt 的一条链， 若 满足前向孤都是非饱和弧，后向弧都是非零流弧，则称 是一条增广链。,对最大流问题有下列定理：,定理 容量网络中任一可行流的流量不超过其任一割集的容量,定理（最大流最小割定理） 任一容量网络中最大流的流量等于最小割集的割量,推论 可行流f*是最大流，当且仅当中不存在关于f*的增广链,求最大流的标号法,标号法的思想是：先找一个可行流对于一个可行流，经过标号过程得到从发点vs到收点vt 的增广链：经过调整过程
