数学建模图论方法专题课件

数学建模

图论方法专题数学建模图论方法专题1内容一．图论的基本概念二．最短路三．行遍性问题四．网络流内容一．图论的基本概念二．最短路三．行遍性问题四．网络流2图论的基本概念问题1:哥尼斯堡七桥问题

能否从任一陆地出发通过每座桥恰好回到出发点?ABCD图论的基本概念问题1:哥尼斯堡七桥问题ABCD3DACB欧拉指出:如果每块陆地所连接的桥都是偶数座,则从任一陆地出发,必能通过恰好一次而回到出发地.DACB欧拉指出:如果每块陆地所连接的桥都是偶数座,则从任一4问题2:哈密顿圈(环球旅行游戏)

十二面体的20个顶点代表世界上20个城市,能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点?问题2:哈密顿圈(环球旅行游戏)5问题3:四色问题

对任何一张地图进行着色,两个共同边界的国家染不同的颜色,则只需要四种颜色就够了.问题3:四色问题6问题4:关键路径问题

一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序,这些工序相互约束,只有在某些工序完成之后,一个工序才能开始,即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个?问题4:关键路径问题71.定义有序三元组G=(V,E,)称为一个图,如果：一.图的基本概念1.定义有序三元组G=(V,E,)称为一个图,如82.常用术语无向图有向图顶点的度子图网络图2.常用术语无向图有向图顶点的度子图网络9用图论思想求解例1一摆渡人欲将一只狼,一头羊,一蓝菜从河西渡过河到河东,由于船小,一次只能带一物过河,并且,狼与羊,羊与菜不能独处,给出渡河办法.用图论思想求解10解:用四维0-1向量表示(人,狼,羊,菜)的在西岸状态,(在西岸则分量取1,否则取0.)共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)也是不允许的,解:用四维0-1向量表示(人,狼,羊,菜)的在西岸状态,(11人在河西:人在河东:(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)以十个向量作为顶点,将可能互相转移的状态连线,则得10个顶点的偶图.问题:如何从状态(1,1,1,1)转移到(0,0,0,0)?方法:从状态(1,1,1,1)开始,沿关联边到达没有到达的相邻顶点,到(0,0,0,0)终止,得到有向图即是.人在河西:人在河东:(1,1,1,1)(112邻接矩阵A=3.图的矩阵表示邻接矩阵A=3.图的矩阵表示13A=A=141.固定起点的最短路二.最短路1.固定起点的最短路二.最短路15数学建模图论方法专题课件16算法步骤：算法步骤：17

TOMATLAB(road1)TOMATLAB(road1)18

12

34

5

6

7

812345678192.每对顶点之间的最短路例求下图中加权图的任意两点间的距离与路径．2.每对顶点之间的最短路例求下图中加权图的任意两点间的距离20算法的基本思想算法的基本思想21算法原理——求距离矩阵的方法算法原理——求距离矩阵的方法22算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．)(nR算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径23i

j算法原理——

查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：ij算法原理——查找最短路路径的方法pkp2p1p3q24算法步骤算法步骤25数学建模图论方法专题课件26插入点v1，得：插入点v1，得：27插入点v3，得：插入点v3，得：28插入点v4，得：插入点v5，得：插入点v4，得：插入点v5，得：29插入点v6，得：插入点v6，得：30故从v5到v2的最短路为8

由v6向v5追溯:由v6向v2追溯:所以从到的最短路径为：故从v5到v2的最短路为8由v6向v5追溯:由v6向v231插入点v2，得：插入点v2，得：323.最短路的应用3.最短路的应用33数学建模图论方法专题课件34

选址问题--中心问题

TOMATLAB(road3(floyd))选址问题--中心问题TOMATLAB(road335S(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处.S(v1)=10,S(v2)=7,S(v3)=6,S(36

选址问题--重心问题选址问题--重心问题37三.行遍性问题定义

设图G=（V，E），ME，若M的边互不相邻，则称M是G的一个匹配.若顶点与M的一条边关联，则称v是M饱和的.设M是G的一个匹配，若G的每个顶点都是M饱和的，则称M是G的理想匹配.三.行遍性问题定义设图G=（V，E），ME，若M的边38

7

3

1

2

3

4

1

2

4

5

5

6

6

7

8

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

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

e3

v1

v2

v3

v4e1e2e4

e5e6欧拉图

e3

v1

v2

v3

v4

e1e

2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1定义１设G=(V,E)是连通无向图（１）经过G的每边至少一次的闭通路称为巡回．（２）经过G的每边正好一次的巡回称为欧拉巡回．（３）存在欧拉巡回的图称为欧拉图．（４）经过G的每边正好一次的道路称为欧拉道路．e3v1v2v3v4e1e2e4e5e6欧拉40e3

v1

v2

v3v4e1e2e4

e5e3

v1

v2

v3v

4

e1

e2e4

e5e6欧拉图非欧拉图定理１对于非空连通图G，下列命题等价：（１）G是欧拉图．（２）G无奇次顶点．（３）G的边集能划分为圈．推论１设G是非平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点．e3v1v2v3v4e1e2e4e5e3v141中国邮递员问题-定义邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线．这就是中国邮递员问题.若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图．中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回．这样的巡回称为最佳巡回．中国邮递员问题-定义邮递员发送邮件时，要从邮局出发，经过他投42中国邮递员问题-算法

Fleury算法基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.1.G是欧拉图

此时G的任何一个欧拉巡回便是最佳巡回．问题归结为在欧拉图中确定一个欧拉巡回．Fleury算法：求欧拉图的欧拉巡回.中国邮递员问题-算法Fleury算法基本思想：从任43

v7e3

v1v2

v3v4e1

e2e4

e5

v5

e6e6

e7

e8

e9e10Fleury算法—算法步骤：（１）任选一个顶点v0，令道路w0=v0.（２）假定道路wi=v0e1v1e2…eivi已经选好，则从E\{e1,e2,…,ei}中选一条边ei+1，使：a）ei+1与vi相关联b）除非不能选择，否则一定要使ei+1不是Gi=G[E-{e1,e2,…,ei}]的割边．（３）第（２）步不能进行时就停止．v7e3v1v2v3v4e1e2e4e5v544若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权）,使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．2.G不是欧拉图若G不是欧拉图，则G的任何一个巡回经过某些边必45v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e9情形１G正好有两个奇次顶点（１）用Dijkstra算法求出奇次顶点u与v之间的最短路径P．（２）令G*=GP，则G*为欧拉图.（３）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回．v7e3v1v2v3v4e1e2e4e5v5v6e6e7e846情形２G有２n个奇次顶点（n２）Edmonds最小对集算法：基本思想：先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小．再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回．情形２G有２n个奇次顶点（n２）Edmonds最小对集算法47（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．算法步骤：（１）用Floyd算法求出所有奇次顶点之间的最短路径和距离．（２）以G的所有奇次顶点为顶点集（偶数个元素），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1．（４）在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*．（５）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回．（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．算48例求右图所示投递区的一条最佳邮递路线．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添加重复边，得欧拉图G2．G2中一条欧拉巡回就是G的一条最佳巡回．其权值为64．例求右图所示投递区的一条最佳邮递路线．1．图中有v4、v7、49哈密尔顿图定义设G=(V,E)是连通无向图.（1）经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径．（2）经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或H圈．（３）含H圈的图称为哈密尔顿图或H图．哈密尔顿图定义设G=(V,E)是连通无向图.50推销员问题-定义流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题．若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题．推销员问题-定义流动推销员需要访问某地区的所有城51定义在加权图G=(V,E)中，（１）权最小的哈密尔顿圈称为最佳H圈．（２）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路．一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈．H回路，长22最佳推销员回路，长4定义在加权图G=(V,E)中，一般说来，最佳哈52定理１在加权图G=(V,E)中，若对任意x,y,zV，zx,zy,都有w(x,y)w(x,z)+w(z,y)，则图G的最佳H圈也是最佳推销员回路．最佳推销员回路问题可转化为最佳H圈问题．方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图G’=(V,E’)，E’的每条边(x,y)的权等于顶点x与y在图中最短路的权．即：x,yE’,w(x,y)=mindG(x,y)定理２加权图G的最佳推销员回路的权与G’的最佳H圈的权相同．定理１在加权图G=(V,E)中，若对任意x,y,zV，z53推销员问题近似算法：二边逐次修正法：(1)任取初始H圈:C0=v1,v2,…,vi,,…,vj,…,vn,v1(2)对所有的i,j，1<i+1<j<n,若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即为所求．推销员问题近似算法：二边逐次修正法：(1)任取初始H圈:C54例对以下完备图，用二边逐次修正法求较优H圈．例对以下完备图，用二边逐次修正法求较优H圈．55返回返回56三.网络流问题基本概念VsVtV2V4V1V3345522311给定一个有向图G=(V,E)，其中仅有一个点的入次为零称为发点(源),记为Vs,仅有一个点的出次为零称为汇点，记为Vt，其余点称为中间点。对于G中的每一个弧(vi,vj),相应地给一个数Cij，称为弧(vi,vj)的容量。我们把这样的图称为网络（或容量网络），记为G=(V,E,C).最大流问题三.网络流问题基本概念VsVtV2V4V1V33455257VsVtV2V4V1V33,14,15,25,22,22,13,11,01,0所谓网络上的流，是指定义在弧集E上的函数f={f(vi,vj)}，并称f(vi,vj)为弧(vi,vj)上的流量，并记为fij。标示方式：每条边上标示两个数字，第一个是容量，第二是流量。可行流、可行流的流量、最大流VsVtV2V4V1V33,14,15,25,22,22,158可行流是指满足如下条件的流:(2)平衡条件:对中间点,有:对收点Vt与发点Vs,有:(1)容量限制条件:对G中每条边(vi,vj),有:可行流是指满足如下条件的流:(2)平衡条件:对收点Vt与发点59可行流总是存在的.所谓最大流问题就是在容量网络中寻找流量最大的可行流.一个流f={fij},当fii=Cij,则称f对边(vi,vj)是饱和的,否则称f对边(vi,vj)不饱和的.VsVtV2V4V1V33,14,15,25,22,22,13,11,01,0可行流总是存在的.所谓最大流问题就是在容量网络中60给定容量网络G=(V,A,E)，若点集V被剖分为两个非空集合V1和V2,使vs∈V1,vt∈V2,则把弧集(V1,V2)称为割集。割集不是唯一的。VsVtV2V4V1V3345522311给定容量网络G=(V,A,E)，若点集V被剖61割集(V1,V2)中所有起点在V1,终点在V2的边的容量的和称为割集容量。VsVtV2V4V1V3345522311在所有割集中，割集容量最小的割集称为最小割集。割集(V1,V2)中所有起点在V1,终点在V62VsVtV2V4V1V33,14,15,25,22,22,13,11,01,0术语:饱和弧、非饱和弧、零流弧、非零弧、前向弧、后向弧设f是一个可行流，是从vs到vt的一条链，若满足前向孤都是非饱和弧，后向弧都是非零流弧，则称是一条增广链。VsVtV2V4V1V33,14,15,25,22,22,163对最大流问题有下列定理：定理１容量网络中任一可行流的流量不超过其任一割集的容量．定理２（最大流－最小割定理）任一容量网络中最大流的流量等于最小割集的割量．推论１可行流f*是最大流，当且仅当Ｇ中不存在关于f*的增广链．对最大流问题有下列定理：定理１容量网络中任一可行流的流量不64求最大流的标号法标号法的思想是：先找一个可行流．对于一个可行流，经过标号过程得到从发点vs到收点vt的增广链：经过调整过程沿增广链增加可行流的流量，得新的可行流．重复这一过程，直到可行流无增广链，得到最大流．调整过程：在增广链上，前向弧流量增加l(vt)，后向弧流量减少l(vt)．求最大流的标号法标号法的思想是：先找一个可行流．对于一个可行65算法(标号法):1.对任意的弧e=(x,y)∈E，置f(x,y)=0;标发点为(s+,∞),令;2.若点x已标号，则对当与x相邻的未标号的点y，按下法标号：a.(x,y)∈E,当f(x,y)<c(x,y)时，令给y标;当f(x,y)=c(x,y)时，不给y标号；b.(y,x)∈E,当f(y,x)>0时，令给y标;当f(y,x)=0时，不给y标号；算法(标号法):1.对任意的弧e=(x,y)∈E，置f(x663.重复2直至收点t被标号或不存在可标号的点。若t被标号，则转4；若t不能被标号且不存在可以标号的点，则停止，输出fv.4.令u=t;5.若u的标号为，则令若u的标号为，则令6.若v=s,则去掉除发点s的所有点的标号，转2;否则令u=v，转5.3.重复2直至收点t被标号或不存在可标号的点。若t被标号，67(s+,∞)(s+,3)(s+,∞)(s+,3)(s+,4)(a+,3)(b+,3)(c+,3)stacbd3,05,05,04,03,01,03,05,02,0stacbd3,05,05,04,03,01,03,05,02,0(s+,4)(s+,∞)stacbd3,35,35,04,03,01,03,35,02,0(s+,4)(s+,∞)stacbd3,35,35,04,03,01,03,35,02,0(s+,4)(b+,3)(d+,3)(a)(b)(c)(d)(s+,∞)(s+,3)(s+,∞)(s+,3)(s+,4)68(s+,∞)stacbd3,35,35,04,33,31,03,35,32,0(s+,4)(s+,∞)stacbd3,35,35,04,33,31,03,35,32,0(s+,1)(b+,1)(a+,1)(c+,1)(d+,1)stacbd3,35,45,14,33,31,13,35,42,0(e)(f)(g)(s+,∞)stacbd3,35,35,04,33,31,069实例国庆期间旅游非常火爆,机票早已订购一空.成都一家旅行社由于信誉好\服务好,所策划的国庆首都游的行情好，要求参加的游客众多，游客甚至多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：实例国庆期间旅游非常火爆,机票早已订购一空.成都一家旅行社由70成都重庆武汉上海西安郑州沈阳昆明广州北京成都106158121030重庆561525武汉10上海158西安86郑州148沈阳18昆明810广州82610成都重庆武汉上海西安郑州沈阳昆明广州北京成都1061581271成重西郑武广沈京上昆10668888561010152510301526810181214158发点s=成都，收点t=北京。前面已订购机票情况表中的数字即是各边上的容量，当各边上的实际客流量为零时略去不写，以零流作为初始可行流。成重西郑武广沈京上昆106688885672成重西郑武广沈京上昆100682060610601010301200810181210100W(f*)=10+6+12+30+12+10+6=86成重西郑武广沈京上昆100682060673最小费用流问题目标：从发点到收点的总的流量费用最小约束：1）容量约束，各边流量不大于容量2）流量平衡约束，各点进出流量总和相等3）从发点到收点的总流量为括号内第一个数字是容量，第二个是单位流量费用sv1v2t4,23,14,25,23,6最小费用流问题目标：从发点到收点的总的流量费用最小约束：1）74最小费用流问题的一般提法容量网络的每边另外赋值非负的单位流量费用，记为，给定从到的总流量，要求一个总流量等于的可行流使得总费用达到最小，特别是，如果给定总流量等于最大流，所求问题称为最小费用最大流问题最小费用流问题的一般提法容量网络75数学建模

图论方法专题数学建模图论方法专题76内容一．图论的基本概念二．最短路三．行遍性问题四．网络流内容一．图论的基本概念二．最短路三．行遍性问题四．网络流77图论的基本概念问题1:哥尼斯堡七桥问题

能否从任一陆地出发通过每座桥恰好回到出发点?ABCD图论的基本概念问题1:哥尼斯堡七桥问题ABCD78DACB欧拉指出:如果每块陆地所连接的桥都是偶数座,则从任一陆地出发,必能通过恰好一次而回到出发地.DACB欧拉指出:如果每块陆地所连接的桥都是偶数座,则从任一79问题2:哈密顿圈(环球旅行游戏)

十二面体的20个顶点代表世界上20个城市,能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点?问题2:哈密顿圈(环球旅行游戏)80问题3:四色问题

对任何一张地图进行着色,两个共同边界的国家染不同的颜色,则只需要四种颜色就够了.问题3:四色问题81问题4:关键路径问题

一项工程任务,大到建造一座大坝,一座体育中心,小至组装一台机床,一架电视机,都要包括许多工序,这些工序相互约束,只有在某些工序完成之后,一个工序才能开始,即它们之间存在完成的先后次序关系,一般认为这些关系是预知的,而且也能够完成每个工序所需要的时间.这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目,影响工程进度的要害工序是哪几个?问题4:关键路径问题821.定义有序三元组G=(V,E,)称为一个图,如果：一.图的基本概念1.定义有序三元组G=(V,E,)称为一个图,如832.常用术语无向图有向图顶点的度子图网络图2.常用术语无向图有向图顶点的度子图网络84用图论思想求解例1一摆渡人欲将一只狼,一头羊,一蓝菜从河西渡过河到河东,由于船小,一次只能带一物过河,并且,狼与羊,羊与菜不能独处,给出渡河办法.用图论思想求解85解:用四维0-1向量表示(人,狼,羊,菜)的在西岸状态,(在西岸则分量取1,否则取0.)共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)也是不允许的,解:用四维0-1向量表示(人,狼,羊,菜)的在西岸状态,(86人在河西:人在河东:(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)以十个向量作为顶点,将可能互相转移的状态连线,则得10个顶点的偶图.问题:如何从状态(1,1,1,1)转移到(0,0,0,0)?方法:从状态(1,1,1,1)开始,沿关联边到达没有到达的相邻顶点,到(0,0,0,0)终止,得到有向图即是.人在河西:人在河东:(1,1,1,1)(187邻接矩阵A=3.图的矩阵表示邻接矩阵A=3.图的矩阵表示88A=A=891.固定起点的最短路二.最短路1.固定起点的最短路二.最短路90数学建模图论方法专题课件91算法步骤：算法步骤：92

TOMATLAB(road1)TOMATLAB(road1)93

12

34

5

6

7

812345678942.每对顶点之间的最短路例求下图中加权图的任意两点间的距离与路径．2.每对顶点之间的最短路例求下图中加权图的任意两点间的距离95算法的基本思想算法的基本思想96算法原理——求距离矩阵的方法算法原理——求距离矩阵的方法97算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．)(nR算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径98i

j算法原理——

查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：ij算法原理——查找最短路路径的方法pkp2p1p3q99算法步骤算法步骤100数学建模图论方法专题课件101插入点v1，得：插入点v1，得：102插入点v3，得：插入点v3，得：103插入点v4，得：插入点v5，得：插入点v4，得：插入点v5，得：104插入点v6，得：插入点v6，得：105故从v5到v2的最短路为8

由v6向v5追溯:由v6向v2追溯:所以从到的最短路径为：故从v5到v2的最短路为8由v6向v5追溯:由v6向v2106插入点v2，得：插入点v2，得：1073.最短路的应用3.最短路的应用108数学建模图论方法专题课件109

选址问题--中心问题

TOMATLAB(road3(floyd))选址问题--中心问题TOMATLAB(road3110S(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处.S(v1)=10,S(v2)=7,S(v3)=6,S(111

选址问题--重心问题选址问题--重心问题112三.行遍性问题定义

设图G=（V，E），ME，若M的边互不相邻，则称M是G的一个匹配.若顶点与M的一条边关联，则称v是M饱和的.设M是G的一个匹配，若G的每个顶点都是M饱和的，则称M是G的理想匹配.三.行遍性问题定义设图G=（V，E），ME，若M的边113

7

3

1

2

3

4

1

2

4

5

5

6

6

7

8

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

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

e3

v1

v2

v3

v4e1e2e4

e5e6欧拉图

e3

v1

v2

v3

v4

e1e

2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1定义１设G=(V,E)是连通无向图（１）经过G的每边至少一次的闭通路称为巡回．（２）经过G的每边正好一次的巡回称为欧拉巡回．（３）存在欧拉巡回的图称为欧拉图．（４）经过G的每边正好一次的道路称为欧拉道路．e3v1v2v3v4e1e2e4e5e6欧拉115e3

v1

v2

v3v4e1e2e4

e5e3

v1

v2

v3v

4

e1

e2e4

e5e6欧拉图非欧拉图定理１对于非空连通图G，下列命题等价：（１）G是欧拉图．（２）G无奇次顶点．（３）G的边集能划分为圈．推论１设G是非平凡连通图，则G有欧拉道路的充要条件是G最多只有两个奇次顶点．e3v1v2v3v4e1e2e4e5e3v1116中国邮递员问题-定义邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线．这就是中国邮递员问题.若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图．中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回．这样的巡回称为最佳巡回．中国邮递员问题-定义邮递员发送邮件时，要从邮局出发，经过他投117中国邮递员问题-算法

Fleury算法基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.1.G是欧拉图

此时G的任何一个欧拉巡回便是最佳巡回．问题归结为在欧拉图中确定一个欧拉巡回．Fleury算法：求欧拉图的欧拉巡回.中国邮递员问题-算法Fleury算法基本思想：从任118

v7e3

v1v2

v3v4e1

e2e4

e5

v5

e6e6

e7

e8

e9e10Fleury算法—算法步骤：（１）任选一个顶点v0，令道路w0=v0.（２）假定道路wi=v0e1v1e2…eivi已经选好，则从E\{e1,e2,…,ei}中选一条边ei+1，使：a）ei+1与vi相关联b）除非不能选择，否则一定要使ei+1不是Gi=G[E-{e1,e2,…,ei}]的割边．（３）第（２）步不能进行时就停止．v7e3v1v2v3v4e1e2e4e5v5119若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权）,使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．2.G不是欧拉图若G不是欧拉图，则G的任何一个巡回经过某些边必120v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e9情形１G正好有两个奇次顶点（１）用Dijkstra算法求出奇次顶点u与v之间的最短路径P．（２）令G*=GP，则G*为欧拉图.（３）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回．v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8121情形２G有２n个奇次顶点（n２）Edmonds最小对集算法：基本思想：先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小．再沿点对之间的最短路径添加重复边得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回．情形２G有２n个奇次顶点（n２）Edmonds最小对集算法122（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．算法步骤：（１）用Floyd算法求出所有奇次顶点之间的最短路径和距离．（２）以G的所有奇次顶点为顶点集（偶数个元素），作一完备图，边上的权为两端点在原图G中的最短距离，将此完备加权图记为G1．（４）在G中沿配对顶点之间的最短路径添加重复边得欧拉图G*．（５）用Fleury算法求出G*的欧拉巡回，这就是G的最佳巡回．（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．算123例求右图所示投递区的一条最佳邮递路线．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添加重复边，得欧拉图G2．G2中一条欧拉巡回就是G的一条最佳巡回．其权值为64．例求右图所示投递区的一条最佳邮递路线．1．图中有v4、v7、124哈密尔顿图定义设G=(V,E)是连通无向图.（1）经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径．（2）经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或H圈．（３）含H圈的图称为哈密尔顿图或H图．哈密尔顿图定义设G=(V,E)是连通无向图.125推销员问题-定义流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题．若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题．推销员问题-定义流动推销员需要访问某地区的所有城126定义在加权图G=(V,E)中，（１）权最小的哈密尔顿圈称为最佳H圈．（２）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路．一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈．H回路，长22最佳推销员回路，长4定义在加权图G=(V,E)中，一般说来，最佳哈127定理１在加权图G=(V,E)中，若对任意x,y,zV，zx,zy,都有w(x,y)w(x,z)+w(z,y)，则图G的最佳H圈也是最佳推销员回路．最佳推销员回路问题可转化为最佳H圈问题．方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图G’=(V,E’)，E’的每条边(x,y)的权等于顶点x与y在图中最短路的权．即：x,yE’,w(x,y)=mindG(x,y)定理２加权图G的最佳推销员回路的权与G’的最佳H圈的权相同．定理１在加权图G=(V,E)中，若对任意x,y,zV，z128推销员问题近似算法：二边逐次修正法：(1)任取初始H圈:C0=v1,v2,…,vi,,…,vj,…,vn,v1(2)对所有的i,j，1<i+1<j<n,若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即为所求．推销员问题近似算法：二边逐次修正法：(1)任取初始H圈:C129例对以下完备图，用二边逐次修正法求较优H圈．例对以下完备图，用二边逐次修正法求较优H圈．130返回返回131三.网络流问题基本概念VsVtV2V4V1V3345522311给定一个有向图G=(V,E)，其中仅有一个点的入次为零称为发点(源),记为Vs,仅有一个点的出次为零称为汇点，记为Vt，其余点称为中间点。对于G中的每一个弧(vi,vj),相应地给一个数Cij，称为弧(vi,vj)的容量。我们把这样的图称为网络（或容量网络），记为G=(V,E,C).最大流问题三.网络流问题基本概念VsVtV2V4V1V334552132VsVtV2V4V1V33,14,15,25,22,22,13,11,01,0所谓网络上的流，是指定义在弧集E上的函数f={f(vi,vj)}，并称f(vi,vj)为弧(vi,vj)上的流量，并记为fij。标示方式：每条边上标示两个数字，第一个是容量，第二是流量。可行流、可行流的流量、最大流VsVtV2V4V1V33,14,15,25,22,22,1133可行流是指满足如下条件的流:(2)平衡条件:对中间点,有:对收点Vt与发点Vs,有:(1)容量限制条件:对G中每条边(vi,vj),有:可行流是指满足如下条件的流:(2)平衡条件:对收点Vt与发点134可行流总是存在的.所谓最大流问题就是在容量网络中寻找流量最大的可行流.一个流f={fij},当fii=Cij,则称f对边(vi,vj)是饱和的,否则称f对边(vi,vj)不饱和的.VsVtV2V4V1V33,14,15,25,22,22,13,11,01,0可行流总是存在的.所谓最大流问题就是在容量网络中135给定容量网络G=(V,A,E)，若点集V被剖分为两个非空集合V1和V2,使vs∈V1,vt∈V2,则把弧集(V1,V2)称为割集。割集不是唯一的。VsVtV2V4V1V3345522311给定容量网络G=(V,A,E)，若点集V被剖136割集(V1,V2)中所有起点在V1,终点在V2的边的容量的和称为割集容量。VsVtV2V4V1V3345522311在所有割集中，割集容量最小的割集称为最小割集。割集(V1,V2)中所有起点在V1,终点在V137VsVtV2V4V1V33,14,15,25,22,22,13,11,01,0术语:饱和弧、非饱和弧、零流弧、非零弧、前向弧、后向弧设f是一个可行流，是从vs到vt的一条链，若满足前向孤都是非饱和弧，后向弧都是非零流弧，则称是一条增广链。VsVtV2V4V1V33,14,15,25,22,22,1138对最大流问题有下列定理：定理１容量网络中任一可行流的流量不超过其任一割集的容量．定理２（最大流－最小割定理）任一容量网络中最大流的流量等于最小割集的割量．推论１可行流f*是最大流，当且仅当Ｇ中不存在关于f*的增广链．对最大流问题有下列定理：定理１容量网络中任一可行流的流量不139求最大流的标号法标号法的思想是：先找一个可行流．对于一个可行流，经过标号过程得到从发点vs到收点vt的增广链：经过调整过程沿增广链增加可行流的流量，得新的可行流．重复这一过程，直到可行流无增广链，得到最大流．调整过程：在增广链上，前向弧流量增加l(vt)，后向弧流量减少l(vt)．求最大流的标号法标号法的思想是：先找一个可行流．对于一个可行140算法(标号法):1.对任意的弧e=(x,y)∈E，置f(x,y)=0;标发点为(s+,∞),令;2.若点x已标号，则对当与x相邻的未标号的点y，按下法标号：a.(x,y