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

1、数学建模数学建模 图论方法专题图论方法专题内容内容一图论的基本概念一图论的基本概念二最短路二最短路三行遍性问题三行遍性问题四网络流四网络流图论的基本概念图论的基本概念问题问题1:哥尼斯堡七桥问题哥尼斯堡七桥问题 能否从任一陆地出发通过每座桥恰好回到能否从任一陆地出发通过每座桥恰好回到出发点出发点?ABCDDACB欧拉指出欧拉指出:如果每块陆地所连接的桥都是偶数座如果每块陆地所连接的桥都是偶数座,则从任一陆则从任一陆地出发地出发,必能通过恰好一次而回到出发地必能通过恰好一次而回到出发地.问题问题2:哈密顿圈哈密顿圈(环球旅行游戏环球旅行游戏)十二面体的十二面体的20个顶点代表世界上个顶点代表世界

2、上20个城市个城市,能否能否从某个城市出发在十二面体上依次经过每个城从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点市恰好一次最后回到出发点?问题问题3:四色问题四色问题 对任何一张地图进行着色对任何一张地图进行着色,两个共同边界两个共同边界的国家染不同的颜色的国家染不同的颜色,则只需要四种颜色则只需要四种颜色就够了就够了.问题问题4:关键路径问题关键路径问题 一项工程任务一项工程任务,大到建造一座大坝大到建造一座大坝,一座体一座体育中心育中心,小至组装一台机床小至组装一台机床,一架电视机一架电视机,都都要包括许多工序要包括许多工序,这些工序相互约束这些工序相互约束,只有只有在

3、某些工序完成之后在某些工序完成之后,一个工序才能开始一个工序才能开始,即它们之间存在完成的先后次序关系即它们之间存在完成的先后次序关系,一一般认为这些关系是预知的般认为这些关系是预知的,而且也能够完而且也能够完成每个工序所需要的时间成每个工序所需要的时间.这时工程领导人员迫切希望了解最这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项少需要多少时间才能够完成整个工程项目目,影响工程进度的要害工序是哪几个影响工程进度的要害工序是哪几个?1.定义定义有序三元组G=(V,E,)称为一个图图,如果：一一.图的基本概念图的基本概念2.常用术语常用术语无向图无向图 有向图有向图 顶点的度顶点

4、的度 子图子图 网络图网络图用图论思想求解用图论思想求解例例1 一摆渡人欲将一只狼一摆渡人欲将一只狼,一头羊一头羊,一蓝菜从一蓝菜从河西渡过河到河东河西渡过河到河东,由于船小由于船小,一次只能带一次只能带一物过河一物过河,并且并且,狼与羊狼与羊,羊与菜不能独处羊与菜不能独处,给出渡河办法给出渡河办法.解解:用四维用四维0-1向量表示向量表示(人人,狼狼,羊羊,菜菜)的在西的在西岸状态岸状态,(在西岸则分量取在西岸则分量取1,否则取否则取0.)共共16种状态种状态,由题设由题设,状态状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是是不允许的不允许的,从而对应状态从而对应状态(1,

5、0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的也是不允许的,人在河西人在河西:人在河东:(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

6、,0)终止终止,得到有向图即是得到有向图即是.邻接矩阵邻接矩阵A=432143210111101011011010vvvvvvvv3.图图 的的 矩矩 阵阵 表表 示示A=4321432105375083802720vvvvvvvv1.1.固定起点的最短路固定起点的最短路二二.最最 短短 路路 03064093021509701608120W算法步骤：算法步骤：（4）若S，转 2，否则，停止.（2）更新l v()、z v()：vSVS,若l v()l uW u v()(,)则令l v()=l uW u v()(,),z v()=u TO MATLAB(road1)1 2 34 5 6 7 8u

7、uuuuuuu2.2.每对顶点之间的最短路每对顶点之间的最短路例例 求下图中加权图的任意两点间的距离与路径求下图中加权图的任意两点间的距离与路径算法的基本思想算法的基本思想算法原理算法原理 求距离矩阵的方法求距离矩阵的方法算法原理算法原理 求路径矩阵的方法求路径矩阵的方法)()0()0(ijrR,jrij)0(每求得一个 D(k)时，按下列方式产生相应的新的 R(k)否则若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距离矩阵的同时可建立路径矩阵在建立距离矩阵的同时可建立路径矩阵R 即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来

8、查找任何点对之间最短路的路径)(D)(R)(Rvi j算法原理算法原理 查找最短路路径的方法查找最短路路径的方法若1)(prij，则点 p1是点 i 到点 j 的最短路的中间点.pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21,12算法步骤算法步骤Floyd 算法：算法：求任意两点间的最短路(2)更新 d(i,j),r(i,j)对所有 i,j，若 d(i,k)+d(k,j)d(i,j)，则 d(i,j)d(i,k)+d(k,j),r(i,j)k(3)若 k=，停止否则 kk+1，转（）,053142503330212044401210 )0(D,654321

9、654321654321654321654321654321)0(R,053142503330212044401210 )0(D,053132503330212043401210)1(D,654311654321654321654321154321654321)1(R插入点插入点 v1，得：得：,053132503330267120453640127510)3(D,654311654321654333654322153321653221)3(R插入点插入点 v3，得：得：,05313250333021204534012510)2(D,053132503330267120453640127510

10、)3(D插入点插入点 v4，得：得：,05313250359103302671520453964012107510)4(D,654311654444654333644322143321643221)4(R,)4()5(DD插入点插入点 v5，得：得：,)4()5(RR插入点插入点 v6，得：得：,05313250359103302671520453964012107510)5(D,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621)6(R,05313250358733026515204338

11、6401275310)6(D.654311654466654336644326163321666621)6(R8)6(52d故从故从v5到到v2的最短路为的最短路为8 6)6(52R由由v6向向v5追溯追溯:.6)6(56R由由v6向向v2追溯追溯:,1)6(62R.2)6(12R所以从到的最短路径为：所以从到的最短路径为：.2165vvvv插入点插入点 v2，得：得：,053132503330212043401210)1(D,05313250333021204534012510)2(D,654311654321654321654322154321654221)2(R 例例 1 设备更新问题：

12、企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少.已知该种设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213 使用不同时间设备所需维修费为：使用年限0112233445维修费56811183.最最 短短 路路 的的 应应 用用 选址问题选址问题-中心问题中心问题则kv就是要求的建立消防站的地点此点称为图的中心点中心点 TO MATLAB(road3(floyd)05.15.55.86475.10475.45.2

13、5.55.54032475.8730571065.42502545.24720375.5710530DS(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处.选址问题选址问题-重心问题重心问题三三.行遍性问题行遍性问题 定义定义 设图设图G=（V，E），），ME，若，若M的边互不相邻，的边互不相邻，则称则称M是是G 的一个的一个匹配匹配.若顶点若顶点v与与M的一条边关联，则称的一条边关联，则称v是是M饱和饱和的的.设设M是是G的一个匹配，若的一个匹配，若G的每个顶点都是的每个顶点都是M饱和的

14、，饱和的，则称则称M是是G的的理想匹配理想匹配.7 3 1 2 3 4 1 2 4 5 5 6 6 7 8 9割边G的边的边 是割边的充要条件是是割边的充要条件是 不含在不含在G的圈中的圈中 割边的定义：割边的定义：设设G连通，连通，E(G),若从若从G中删除边中删除边 后，后，图图G-不连通，则称边不连通，则称边 为图为图G的的割边割边eeeeeevvvvvvveeeeeeeee e3 v1 v2 v3 v4e1e2e4 e5e6欧欧 拉拉 图图 e3 v1 v2 v3 v4 e1e 2e4e5巡回巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路欧拉道路：v1e1v2e2v

15、3e5v1e4v4e3v3欧拉巡回：欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1定义定义设设G=(V,E)是连通无向图是连通无向图（）经过（）经过G的每边至少一次的闭通路称为的每边至少一次的闭通路称为巡回巡回（）经过（）经过G的每边正好一次的巡回称为的每边正好一次的巡回称为欧拉巡回欧拉巡回（）存在欧拉巡回的图称为（）存在欧拉巡回的图称为欧拉图欧拉图（）经过（）经过G的每边正好一次的道路称为的每边正好一次的道路称为欧拉道路欧拉道路e3 v1 v2 v3v4e1e2e4 e5e3 v1 v2 v3v 4 e1 e2e4 e5e6欧拉图欧拉图 非欧拉图非欧拉图定理定理对于非空连通图

16、对于非空连通图G，下列命题等价：，下列命题等价：（）（）G是欧拉图是欧拉图（）（）G无奇次顶点无奇次顶点（）（）G的边集能划分为圈的边集能划分为圈 推论推论设设G是非平凡连通图，则是非平凡连通图，则G有欧拉道路的充有欧拉道路的充要条件是要条件是G最多只有两个奇次顶点最多只有两个奇次顶点中国邮递员问题中国邮递员问题-定义定义邮递员发送邮件时，要从邮局出发，经过他投递范邮递员发送邮件时，要从邮局出发，经过他投递范围内的每条街道至少一次，然后返回邮局，但邮递围内的每条街道至少一次，然后返回邮局，但邮递员希望选择一条行程最短的路线这就是员希望选择一条行程最短的路线这就是中国邮递中国邮递员问题员问题.若

17、将投递区的街道用边表示，街道的长度用边若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图中国邮递员问题转化为：构成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为回这样的巡回称为最佳巡回最佳巡回 中国邮递员问题中国邮递员问题-算法算法 Fleury算法基本思想算法基本思想：从任一点出发，每当访问：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条边时，先要进行检查如果可供访问的边不只一条

18、，则应选一条不是未访问的边集的导出子图的一条，则应选一条不是未访问的边集的导出子图的割边割边作为访问边，直到没有边可选择为止作为访问边，直到没有边可选择为止.1.G是欧拉图是欧拉图 此时此时G的任何一个欧拉巡回便是最佳巡回问题归结的任何一个欧拉巡回便是最佳巡回问题归结为在欧拉图中确定一个欧拉巡回为在欧拉图中确定一个欧拉巡回 Fleury算法算法：求欧拉图的欧拉巡回：求欧拉图的欧拉巡回.v7e3 v1v2 v3v4e1 e2e4 e5 v5 e6e6 e 7 e8 e9e10Fleury算法算法算法步骤：算法步骤：（）任选一个顶点）任选一个顶点v0，令道路，令道路w0=v0.（）假定道路（）假定

19、道路wi=v0e1v1e2eivi已经选好，则从已经选好，则从Ee1,e2,ei 中选一条边中选一条边ei+1，使：，使：a）ei+1与与vi相关联相关联 b）除非不能选择，否则一定要使）除非不能选择，否则一定要使ei+1不是不是Gi=GE-e1,e2,ei 的割边的割边（）第（）步不能进行时就停止（）第（）步不能进行时就停止 若若G不是欧拉图，则不是欧拉图，则G的任何一个巡回经过某的任何一个巡回经过某些边必定多于一次些边必定多于一次 解决这类问题的一般方法是：在一些点对之间解决这类问题的一般方法是：在一些点对之间引入重复边（重复边与它平行的边具有相同的权）引入重复边（重复边与它平行的边具有相

20、同的权）,使原图成为欧拉图，但希望所有添加的重复边的使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小权的总和为最小2.G不是欧拉图不是欧拉图v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e9情形情形G正好有两个奇次顶点正好有两个奇次顶点（）用（）用Dijkstra算法求出奇次顶点算法求出奇次顶点u与与v之间的最短路径之间的最短路径P（）令（）令G*=GP，则，则G*为欧拉图为欧拉图.（）用（）用Fleury算法求出算法求出G*的欧拉巡回，这就是的欧拉巡回，这就是G的最佳巡回的最佳巡回情形情形G有有n个奇次顶点（个奇次顶点（n）Edmonds最小对集算法：最小对集算法：基本

21、思想：基本思想：先将奇次顶点配对，要求最佳配对，即点对之间先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小再沿点对之间的最短路径添加重复边距离总和最小再沿点对之间的最短路径添加重复边得欧拉图得欧拉图G*，G*的欧拉巡回便是原图的最佳巡回的欧拉巡回便是原图的最佳巡回（）求出（）求出G1的的最小权理想匹配最小权理想匹配M，得到奇次顶点的，得到奇次顶点的最佳配对最佳配对算法步骤：算法步骤：（）用（）用Floyd算法求出所有奇次顶点之间的最短路径和距离算法求出所有奇次顶点之间的最短路径和距离（）以（）以G的所有奇次顶点为顶点集（偶数个元素），作一的所有奇次顶点为顶点集（偶数个元素），作一完备图，

22、边上的权为两端点在原图完备图，边上的权为两端点在原图G中的最短距离，将此完中的最短距离，将此完备加权图记为备加权图记为G1（）在（）在G中沿配对顶点之间的最短路径添加重复边得欧拉图中沿配对顶点之间的最短路径添加重复边得欧拉图G*（）用（）用Fleury算法求出算法求出G*的欧拉巡回，这就是的欧拉巡回，这就是G的最佳巡回的最佳巡回3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv例求右图所示投递区的一条最佳邮

23、递路线例求右图所示投递区的一条最佳邮递路线1图中有图中有v4、v7、v8、v9四个奇次顶点四个奇次顶点用用Floyd算法求出它们之间的最短路径和距离：算法求出它们之间的最短路径和距离：2以以v4、v7、v8、v9为顶点，他们之间的距离为边权构造完备图为顶点，他们之间的距离为边权构造完备图G13求出求出G1的最小权完美匹配的最小权完美匹配M=(v4,v7),(v8,v9).4在在G中沿中沿v4到到v7的最短路径添加重复边，沿的最短路径添加重复边，沿v8到到v9的最短路径的最短路径v8v9添加重复添加重复边，得欧拉图边，得欧拉图G2G2中一条欧拉巡回就是中一条欧拉巡回就是G的一条最佳巡回其权值为的

24、一条最佳巡回其权值为64哈哈 密密 尔尔 顿顿 图图定义设定义设G=(V,E)是连通无向图.（1）经过G的每个顶点正好一次的路径，称为G的一条哈密尔顿路径哈密尔顿路径（2）经过G的每个顶点正好一次的圈，称为G的哈密尔顿圈或哈密尔顿圈或H圈（）含H圈的图称为哈密尔顿图或哈密尔顿图或H图推销员问题推销员问题-定义定义 流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题推销员问题 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题定义定义在加权图G=(V,

25、E)中，（）权最小的哈密尔顿圈称为最佳最佳H圈圈（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长4定理在加权图定理在加权图G=(V,E)中，若对任意x,y,z V，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)=m

26、indG(x,y)定理加权图定理加权图G的最佳推销员回路的权与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即为所求例例对以下完

27、备图，用二边逐次修正法求较优H圈返回返回三三.网络流问题网络流问题 基本概念基本概念VsVtV2V4V1V3345522311 给定一个有向图给定一个有向图G=(V,E)，其中仅有一个点的入，其中仅有一个点的入次为零称为次为零称为发点发点(源源),记为记为Vs,仅有一个点的出次为零仅有一个点的出次为零称为称为汇点汇点，记为，记为Vt，其余点称为，其余点称为中间点中间点。对于对于G中的每一个弧中的每一个弧(vi,vj),相应地给一个数相应地给一个数Cij，称为弧称为弧(vi,vj)的容量。我们把这样的图称为的容量。我们把这样的图称为网络网络（或（或容量网络），记为容量网络），记为G=(V,E,C

28、).最大流问题最大流问题VsVtV2V4V1V33,14,15,25,22,22,13,11,01,0 所谓网络上的所谓网络上的流流，是指定义在弧集，是指定义在弧集E上的函数上的函数f=f(vi,vj)，并称，并称f(vi,vj)为弧为弧(vi,vj)上的上的流量流量，并记为，并记为fij。标示方式：每条边上标示两个数字，第一个是标示方式：每条边上标示两个数字，第一个是容量容量，第二是第二是流量流量。可行流、可行流的流量、最大流可行流、可行流的流量、最大流可行流是指满足如下条件的流可行流是指满足如下条件的流:0ijijfC(2)平衡条件平衡条件:对中间点对中间点,有有:ijkijkff对收点对

29、收点Vt与发点与发点Vs,有有:sijtijffW(1)容量限制条件容量限制条件:对对G中每条边中每条边(vi,vj),有有:可行流总是存在的可行流总是存在的.所谓所谓最大流问题最大流问题就是在容量网络中寻找流量最大的可就是在容量网络中寻找流量最大的可行流行流.一个流一个流f=fij,当当fii=Cij,则称则称f对边对边(vi,vj)是是饱和饱和的的,否则称否则称f对边对边(vi,vj)不饱和不饱和的的.VsVtV2V4V1V33,14,15,25,22,22,13,11,01,0 给定容量网络给定容量网络G=(V,A,E)，若点集，若点集V被剖分为两被剖分为两个非空集合个非空集合V1和和V

30、2,使使vsV1,vt V2,则把弧集则把弧集(V1,V2)称为称为割集割集。割集不是唯一的割集不是唯一的。VsVtV2V4V1V3345522311 割集割集(V1,V2)中所有起点在中所有起点在V1,终点在终点在V2的边的容的边的容量的和称为量的和称为割集容量割集容量。VsVtV2V4V1V3345522311 在所有割集中，割集容量最小的割集称为在所有割集中，割集容量最小的割集称为最最小割集小割集。VsVtV2V4V1V33,14,15,25,22,22,13,11,01,0术语术语:饱和弧、非饱和弧、零流弧、非零弧、饱和弧、非饱和弧、零流弧、非零弧、前向弧、后向弧前向弧、后向弧设设f是

31、一个可行流，是一个可行流，是从是从vs到到vt 的一条链，的一条链，若若满足前向孤都是非饱和弧，后向弧都是非零流弧，满足前向孤都是非饱和弧，后向弧都是非零流弧，则称是一条则称是一条增广链增广链。对最大流问题有下列定理：对最大流问题有下列定理：定理定理容量网络中任一可行流的流量不超过其任一容量网络中任一可行流的流量不超过其任一割集的容量割集的容量定理定理（最大流最小割定理）任一容量网络中最（最大流最小割定理）任一容量网络中最大流的流量等于最小割集的割量大流的流量等于最小割集的割量推论推论可行流可行流f*是最大流，当且仅当中不存在关于是最大流，当且仅当中不存在关于f*的增广链的增广链求最大流的标号

32、法求最大流的标号法标号法的思想是：标号法的思想是：先找一个可行流对于一个可行流，先找一个可行流对于一个可行流，经过标号过程得到从发点经过标号过程得到从发点vs到收点到收点vt 的增广链：经过调整的增广链：经过调整过程沿增广链增加可行流的流量，得新的可行流重复过程沿增广链增加可行流的流量，得新的可行流重复这一过程，直到可行流无增广链，得到最大流这一过程，直到可行流无增广链，得到最大流调整过程：调整过程：在增广链上，前向弧流量增加在增广链上，前向弧流量增加l(vt)，后向，后向弧流量减少弧流量减少l(vt)算法算法(标号法标号法):1.对任意的弧对任意的弧e=(x,y)E，置，置f(x,y)=0;

33、标发点为标发点为(s+,),令令 ;s 2.若点若点x已标号，则对当与已标号，则对当与x相邻的未标号的点相邻的未标号的点y，按，按下法标号：下法标号：min(,)(,),xc x yf x yya.(x,y)E,当当f(x,y)0时，令时，令min(,),xf x yy给给y标标 ;当当f(y,x)=0时，不给时，不给y标号；标号；(,)yx3.重复重复2直至收点直至收点t被标号或不存在可标号的点。若被标号或不存在可标号的点。若t被被 标号，标号，则转则转4；若；若t不能被标号且不存在可以标号的点，则停止，输不能被标号且不存在可以标号的点，则停止，输出出fv.4.令令u=t;5.若若u的标号为

34、的标号为 ，则令，则令(,)uv(,)(,)tf v uf v u若若u的标号为的标号为 ，则令，则令(,)uv(,)(,)tf v uf v u6.若若v=s,则去掉除发点则去掉除发点s的所有点的标号，转的所有点的标号，转2;否则令否则令u=v，转转5.(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+,)stacb

35、d3,35,35,04,03,01,03,35,02,0(s+,4)(b+,3)(d+,3)(a)(b)(c)(d)(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)实例实例国庆期间旅游非常火爆国庆期间旅游非常火爆,机票早已订购一空机票早已订购一空.成都一家旅行成都一家旅行社由于信誉好社由于信誉好服务好服务好,所策划的国庆首都游的行情好，要

36、所策划的国庆首都游的行情好，要求参加的游客众多，游客甚至多花机票钱暂转取道它地也求参加的游客众多，游客甚至多花机票钱暂转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：办事处已订购机票的详细情况表：成都成都重

37、庆重庆武汉武汉上海上海西安西安郑州郑州沈阳沈阳昆明昆明广州广州北京北京成都成都106158121030重庆重庆561525武汉武汉10上海上海158西安西安86郑州郑州148沈阳沈阳18昆明昆明810广州广州82610 成成 重重 西西 郑郑 武武 广广 沈沈 京京 上上 昆昆10668888561010152510301526810181214158发点发点s=成都，收点成都，收点t=北京。前面已订购机票情况表中的北京。前面已订购机票情况表中的数字即是各边上的容量，当各边上的实际客流量为零时数字即是各边上的容量，当各边上的实际客流量为零时略去不写，以零流作为初始可行流。略去不写，以零流作为初

38、始可行流。成成 重重 西西 郑郑 武武 广广 沈沈 京京 上上 昆昆100682060610601010301200810181210100W(f*)=10+6+12+30+12+10+6=86最小费用流问题最小费用流问题目标：目标：从发点到收点的总的流量费用最小从发点到收点的总的流量费用最小约束：约束：1）容量约束，各边流量不大于容量）容量约束，各边流量不大于容量 2）流量平衡约束，各点进出流量总和相等）流量平衡约束，各点进出流量总和相等 3）从发点到收点的总流量为）从发点到收点的总流量为括号内第一个数字是容量，第二个是单位流量费用括号内第一个数字是容量，第二个是单位流量费用wsv1v2t4,23,14,25,23,6最小费用流问题的一般提法最小费用流问题的一般提法CEVG,容量网络容量网络 的每边另外赋值非负的单位的每边另外赋值非负的单位流量费用流量费用 ，记为，记为 ，给，给定从定从 到到 的总流量的总流量 ，要求一个总流量等于，要求一个总流量等于 的可行流的可行流 使得总费用使得总费用达到最小，特别是，如果给定总流量等于最大流，达到最小，特别是，如果给定总流量等于最大流，所求问题称为最小费用最大流问题所求问题称为最小费用最大流问题Evvijijjixd),(wtvsvEvvdjiij),(,DCEVG,ijxX w