运筹学第十章图与网络优化ppt课件.ppt

第十章图与网络优化(Graph Theory and Network Analysis),图的基本概念树及最小支撑树最短路问题网络最大流问题最小费用最大流问题中国邮递员问题,图论的起源和发展,1736年，Euler哥尼斯堡七桥问题 (Knigsberg Bridge Problem),一笔画问题,1847年，kirchhoff，电网络，“树”；,1852年，四色猜想；,1964年，华罗庚，统筹方法平话。,1857年，Cogley，同分异构，“树”；,1956年，杜邦公司，CPM，关键路线法；,1958年，美国海军部，PERT，计划评审技术；,1962年，管梅谷，中国邮路问题；,第一节 图的基本概念,一、几个例子,例1 是北京、上海等十个城市间的铁路交通图。与此类似的还有电话线分布图、煤气管道图、航空路线图等。,北京,天津,济南,青岛,武汉,南京,上海,郑州,连云港,徐州,例2 分别用点v1,v2,v3,v4,v5分别代表甲、乙、丙、丁、戊五支球队。若有两支球队之间比赛过，就在相应的点之间联一条线，且这条线不过其他点。如下图所示：,v1,v2,v3,v4,v5,可知各队之间的比赛情况如下：甲 乙、丙、丁、戊乙 甲、丙丙 甲、乙、丁丁 甲、丙、戊戊 甲、丁,例3 “染色问题” 储存8种化学药品，其中某些药品不能存放在同一个库房里。 用v1,v2,v8分别代表这8种药品。规定若两种药品不能存放在一起，则其相应的点之间联一条线。如下图所示：,v1,v2,v3,v4,v5,v6,v7,v8,可知需要4个库房，其中一个答案是： v1 v2, v4, v7 v3, v5 v6, v8 还有其他的答案。,二、基本概念,有向图 由点及弧所构成的图，记为D=(V,A)， V,A分别是D的点集合和弧集合。,无向图 由点及边所构成的图。记为G=(V,E), V，E分别是G的点集合和边集合。,v1,v2,v3,v4,v1,v2,v3,v4,a1,a2,a3,a4,a5,e1,e2,e3,e4,e5,a6,e6,边 两点之间不带箭头的联线。 如 e3,v1,v4,a3,弧 两点之间带箭头的联线。 如 a3,v1,v4,e3,端点及关联边,若边e =u,vE，则称u,v 为e的端点，也称u,v是相邻的，称e是点u(及点v)的关联边。,如：v1,v4为e3的端点，v1,v4是相邻的，e3 是v1（v4 ）的关联边。,环 若在图G中，某个边的两个端点相同，则称e是环。如 e7,v1,v2,v3,v4,e1,e2,e3,e4,e5,e6,e7,多重边 若两个点之间有多于一条的边，称这些边为多重边。如 e1,e2,简单图 一个无环，无多重边的图。,多重图 一个无环、但允许有多重边的图。,点v的次 以点vi为端点边的个数，记为dG(vi)或d(vi)。,v1,v2,v3,v4,e1,e2,e3,e4,e5,e6,e7,如 d(v4)=5,d(v2)=4,v5,悬挂点 次为1的点，如 v5,悬挂边 悬挂点的关联边，如 e8,e8,孤立点 次为0的点,偶点 次为偶数的点，如 v2,奇点 次为奇数的点, 如 v5,链中间点初等链圈初等圈简单圈,v1,v2,v5,v6,v7,v3,v4,e1,e2,e4,e3,e5,e6,e7,e8,e9,在上图中,(v1,v2,v3,v4,v5,v3,v6,v7)是一条链, 但不是初等链,在该链中,v2,v3,v4,v5,v3,v6是中间点,(v1,v2,v3,v6,v7)是一条初等链,(v1,v2,v3,v4,v1)是一个初等圈,( v4,v1,v2,v3,v5,v7,v6,v3,v4)是一个简单圈,连通图图G中，若任何两个点之间，至少有一条链，称为连通图。否则称为不连通图。,连通分图(分图)若G是不连通图，则它的每个连通的部分称为连通分图。,v1,v2,v3,v4,e1,e2,e3,e4,e5,e6,v5,v6,e7,如左图就是个不连通图，它是由两个连通分图构成的。,支撑子图给定一个图G=(V,E)，如果图G=(V,E)，使V=V及EE，则称G是G的一个支撑子图。,v1,v2,v3,v4,(G),v1,v2,v3,v4,(G),基础图给定一个有向图D=(V,A) ，从D中去掉所有弧上的箭头，所得到的无向图称为基础图。记之为G(D)。,v1,v2,v3,v4,a1,a2,a3,a4,a5,a6,D=(V,A),v1,v2,v3,v4,e1,e2,e3,e4,e5,e6,G(D),v1,v2,v3,v4,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,v6,v7,路 初等路 回路,v5,简单有向图 多重有向图,权与网络,在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作v1 ，一个称为终点（或收点），记作vn ，其余的点称为中间点。对每一条弧 ，对应一个数 ，称为弧上的“权”。通常把这种赋权的图称为网络。,对于网络（赋权图）G=（V，E），其中边有权 ，构造矩阵 ，其中：称矩阵A为网络G的权矩阵。,设图G=（V，E）中顶点的个数为n，构造一个矩阵 ，其中： 称矩阵A为网络G的邻接矩阵。,图的矩阵表示,权矩阵为：,邻接矩阵为：,图的矩阵表示,定理1图G=(V,E)中，所有点的次之和是边数的两倍，即,定理2任一图中奇点的个数为偶数。,三、基本定理,第二节 树,一、定义,例1 在五个城市之间架设电话线，要求任两个城市之间都可以相互通话（允许通过其他城市），并且电话线的根数最少。,用v1,v2,v3,v4,v5代表五个城市,如果在某两个城市之间架设电话线,则在相应的两点之间联一条边,这样一个电话线网就可以用一个图来表示。显然,这个图必须是连通的,而且是不含圈的连通图。如右图所示。,树的定义：一个无圈的连通图。,例2 某工厂的组织机构如下图所示,厂长,行政办公室,生产办公室,生产计划科,技术科,设计组,工艺组,供销科,财务科,行政科,车间,铸造工段,锻压工段,二车间,三车间,四车间,该厂的组织机构图就是一个树。,例3 树图倒置的树，根(root)在上，叶(leaf)在下,定理1 设图G=(V,E) 是一个树，p(G)2，则G中至少有两个悬挂点。,二、性质,证明,定理2 图G=(V,E) 是一个树的充分必要条件是G中不含圈，且恰有p-1条边。,证明,定理3 图G=(V,E)是一个树的充分必要条件是G是连通图，并且q(G)=p(G)-1。,证明,由定理2，必要性显然。,定理4 图G是树的充分必要条件是任意两个顶点之间恰有一条链。,证明,由树的定义，必要性显然。,因为任两个顶点间恰有一条链，显然G是连通的。如果G中含有圈的话，则其中至少有两个顶点间有两条链，这与题设矛盾。充分性得证。,推论：,从一个树中去掉一条边，则余下的图是不连通的。,在树中不相邻的两个点间添上一条边，则恰好得到一个圈。,三、图的支撑树,定义：设图T=(V,E) 是图G的支撑子图，如果图T=(V, E) 是一个树，则称T是G的一个支撑树。,定理：图G有支撑树的充分必要条件是图G是连通的。,证明,必要性显然。,再证充分性。 设图G是连通图，若G不含圈，则G本身是一个树，从而G是它自身的一个支撑树。,如果G含圈，任取一个圈，从圈中任意地去掉一条边，得到图G的一个支撑子图G1。如果G1不含圈，那么G1是G的一个支撑树；如果G1仍含圈，那么从G1中任取一个圈，从圈中再任意去掉一条边，得到图G的一个支撑子图G2，如此重复，最终可以得到G的一个支撑子图Gk,它不含圈，于是Gk是G的一个支撑树。,支撑树的求解方法,破圈法,例 用破圈法求解图的一个支撑树,v1,v2,v3,v4,v5,e1,e2,e3,e4,e5,e6,e7,e8,这就得到了该图的一个支撑树。,避圈法,v1,v2,v3,v4,v5,v6,e1,e2,e3,e4,e5,e6,e7,e8,e9,这就得到了该图的一个支撑树。,四、最小支撑树,定义1 给图G=(V,E) ，对G中的每一条边vi,vj，相应地有一个数wij，则称这样的图G为赋权图，wij称为边vi,vj上的权。,1. 定义,定义2 如果T=(V,E) 是G的一个支撑树，称E中所有边的权之和为支撑树T的权，记为w(T)，即,最小支撑树 如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树),即,2. 最小支撑树的求法,方法一 避圈法 开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。,v1,v2,v3,v4,v5,v6,6,5,1,5,7,2,3,4,4,这就得到了该图的一个最小支撑树。,方法二 破圈法 任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。,v1,v2,v3,v4,v5,v6,6,5,1,5,7,2,3,4,4,这就得到了该图的一个最小支撑树。,第三节 最短路问题,一、最短路问题的提出,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,例,左图为单行线交通网，弧旁数字表示通过这条单行线所需要的费用。求从v1出发到v8总费用最小的路线。(1)有很多条路线，与图论中的路一一对应；,(2)一条路线的费用就是相应的路中各条弧的费用之和。,如上图所示的路线为最短路。,在图论中，最短路问题可归结为：(1)给定一个赋权有向图D(V,A)及W(a)= Wij；(2)给定D中两个顶点vs、vt，P是D中从vs到vt的一条路；(3)定义路P的权为P中所有弧的权之和， W(P) Wij ；(4)求一条权最小的路P0: W(P0) =min W(P),二、求解方法,基本原理：最短路问题的特性 最短路线上的任一中间点到终（起）点的路线一定是该中间点到终（起）点的所有路线中最短的路线。 若求起点A到任一点G的最短路线，可先求A到G点的相邻前点的最短距离，在此基础上求出A到G点的最短距离。这样，最终求出起点到终点的最短距离。,狄克斯屈拉算法 (Dijkstra , 1959)。 从起点vs出发，逐步向外探寻最短路。在已知前点的最短距离基础上，求其后点的最短距离。,1. wij0,例1 狄克斯特拉算法,0,8,15,10,12,15,11,31,13,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,(v1,0),(v1,1),第一步：,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,(v1,0),(v1,3),(v1,1),第二步：,第三步：,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,(v1,0),(v1,3),(v1,1),(v3,5),第四步：,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,(v1,0),(v1,3),(v1,1),(v3,5),(v2,6),第五步：,(v5,9),v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,(v1,0),(v1,3),(v1,1),(v3,5),(v2,6),第六步：,(v5,9),v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,(v1,0),(v1,3),(v1,1),(v3,5),(v2,6),(v5,10),第七步：,(v5,12),(v5,9),v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,(v1,0),(v1,3),(v1,1),(v3,5),(v2,6),(v5,10),v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,(v1,0),(v3,5),(v1,3),(v1,1),最后，找出v1到v8的最短路为：,(v4,11),(v2,6),(v5,10),(v5,9),(v5,12),缺点：不能解决存在负权图的最短路问题。,计算步骤： (1)考察从所有标号点(已求出最短距离的点)出发的弧的终点vj (已标号的点除外) ，计算起点vs 到vj的距离dsj(标号值 Wij)；若vj不存在，算法终止，转(3)。 (2)增加新的标号点。比较所有dsj ，最小者对应的点成为新的标号点，即求出了vs 到某个vj的最短距离dsj*，转(1)。 (3) 逆着计算过程反推，找出最短路。,DP最短路与Dijkstra最短路的比较相同点： (1)依据最短路的特性； (2)隐含比较了vs 到vj 的所有路线。不同点： (1)Dijkstra更具普遍性，DP是特例； (2)DP隐含比较vs 到vj 的所有路线是完整的； Dijkstra隐含比较vs 到vj 的所有路线中，只有一部分是完整的，其它的只是vs 到vj 的路线的一段； (3)每迭代一次，DP可求出起点至某阶段末所有点的最短距离，而 Dijkstra只能求出起点至一个中间点的最短距离。,2. wij不全0,Dijkstra算法失效，即虽然完整的路线比完整中的片断距离短，但也不能断定该完整路线一定最短。 只能采用最原始的思想，即找出vs 到vj 的所有路线的权，才能确定vs 到vj 的最短距离。具体算法如下： 设有向图中有n个点，从vi 到vj的最短路线不一定从vi直达vj，也可能经过一个、两个或n2个中间点才能到达vj 。把从vi直达vj，称为走一步，经过一个中间点称为走二步，则vi 到vj的最短路线最多走n1 步。,应用条件：图中不存在负回路。,v1,v2,v3,v4,v5,v6,v7,v8,表格法,6,-1,-2,8,3,-3,-5,-1,2,1,1,1,2,-1,-3,-5,7,(v1,0),(v1,-1),(v1,3),(v1,-2),(v1,),(v1,),(v1,),(v1,),例: 求v1 到图中其他各点的最短路。,走1步时,v1,v2,v3,v4,v5,v6,v7,v8,6,-1,-2,8,3,-3,-5,-1,2,1,1,1,2,-1,-3,-5,7,(v1,0),(v1,-1),(v1,3),(v1,-2),(v1,),(v1,),(v1,),(v1,),(v3,-5),(v3,-7),(v3,-1),(v2,5),(v4,11),(v4,5),(v2,1),走2步时,v1,v2,v3,v4,v5,v6,v7,v8,6,-1,-2,8,3,-3,-5,-1,2,1,1,1,2,-1,-3,-5,7,(v1,0),(v1,-2),(v1,),(v1,),(v3,-5),(v3,-7),(v3,-1),(v2, 1),(v6,0),(v4, 5),(v4,-5),(v6,6),走3步时,(v5,0),(v2,1),(v4, 1),(v2,-3),(v6,0),(v7,4),v1,v2,v3,v4,v5,v6,v7,v8,6,-1,-2,8,3,-3,-5,-1,2,1,1,1,2,-1,-3,-5,7,(v1,0),(v1,-2),(v6,6),(v1,),(v3,-5),(v3,-7),(v3,-1),(v2, -3),(v6,0),(v4, -5),走4步时,(v5,-4),(v2,1),(v4, 1),(v6,0),(v7,-6),(v8,3),(v8, 1),说明：表中空格处为+。,缺点：不能解决负回路的情况。,3. Floyd （佛洛伊德）算法,这里介绍得Floyd（1962年）可直接求出网络中任意两点间的最短路。,令网络中的权矩阵为,其中,当,其他,算法基本步骤为：, 输入权矩阵,例: 求图中任意两点间的最短路。, 计算,其中,例如：,中不带角标的元素表示从 到 的距离（直接有边），带角标的元素表示借 为中间点时的最短路长。,中不带角标的元素表示从 到 的距离（直接有边），带角标的元素表示借 为中间点时的最短路长。,在放开 的基础上，再放开,注意到：,在放开 点的基础上，再放开 考察最短路。,注意到：,说明所有点经过 并没有缩短路程。,只有一个新增元素,表示任意两点间的最短路长及其路径。,三、应用举例,例 设备更新问题。某企业使用一台设备，在每年年初都要决定是购置新设备还是继续使用旧的。购置新设备要支付一定的购置费，使用旧设备则要支付维修费。制定一个五年内的设备更新计划，使得总支付费用最少。,已知该设备在各年年初的价格为：,已知使用不同时间的设备维修费用为：,设以vi(i=1,2,3,4,5)表示“第i年初购进一台新设备”这种状态，以v6表示“第5年末”这种状态；以弧(vi, vj)表示“第i年初购置的一台设备一直使用到第j年初”这一方案，以wij表示这一方案所需购置费和维修费之和。,这样，可建立本例的网络模型。于是，该问题就可归结为从图中找出一条从v1到v6的最短路问题。,从图中可以得出两条最短路： v1 v3v6 ; v1 v4v6,v1,v2,v3,v5,v6,v4,16,30,22,16,59,41,22,41,30,17,31,23,17,23,18,(v1,0),(v1,16),v1,v2,v3,v5,v6,v4,16,30,22,16,59,41,22,41,30,17,31,23,17,23,18,(v1,0),(v1,16),(v1,22),v1,v2,v3,v5,v6,v4,16,30,22,16,59,41,22,41,30,17,31,23,17,23,18,(v1,0),(v1,16),(v1,22),(v1,30),v1,v2,v3,v5,v6,v4,16,30,22,16,59,41,22,41,30,17,31,23,17,23,18,(v1,0),(v1,16),(v1,22),(v1,30),(v1,41),v1,v2,v3,v5,v6,v4,16,30,22,16,59,41,22,41,30,17,31,23,17,23,18,(v1,0),(v1,16),(v1,22),(v1,30),(v1,41),(v3,53),(v4,53),第四节 网络最大流问题,如下是一运输网络，弧上的数字表示每条弧上的容量，问：该网络的最大流量是多少？,vs,v2,v1,v3,v4,vt,4,3,2,1,1,5,2,3,4,一、问题的提出,二、求解方法,（一）概念,1. 可行流和最大流,容量限制条件：0 fij cij 平衡条件：,对于网络D(V，A，C)，网络D上的流 f 指定义在弧集合A上的一个函数 f = fij ， fij 为弧 aij 的流量。满足下列条件的流 f 称为可行流：,v( f )最大的可行流 f 称为最大流，记为 f *。可用以下LP模型求解。,对于任何网络，其可行流 f 一定存在。如令 f ij=0， f 为可行流，其v( f ) =0。,零流弧: fij = 0的弧,若是网络中连接起点vs和终点vt的一条链，定义链的方向是从vs到vt，则链上的弧被分成两类：,前向弧：弧的方向与链的方向一致, +表示中前向弧的集合,后向弧：弧的方向与链的方向相反, 表示中后向弧的集合,3. 前向弧和后向弧,零流弧和饱和弧,设 f 是一可行流，是从vs到vt的一条链，若满足下列条件，则称之为（关于流 f 的）一条增广链： 在弧(vi,vj)+上，0fijcij(非饱和弧) 在弧(vi,vj)上，0fijcij (非零流弧),4. 增广链,vs,v2,v1,v3,v4,vt,10(5),8(3),4(1),5(2),3(2),6(3),3(3),11(6),17(2),5(1),在左图中,(vs,v1,v2,v3,v4,vt)是一条增广链,因为+ 和中的弧满足增广链的条件。如：,5. 可扩充量,6. 调整后的弧流量,v5,v1,v2,v3,v4,v6,(2, 2),(8, 3),(3, 1),(2, 2),(4, 1),(2, 1),(2, 2),(5, 3),(二) 标号法求最大流(Ford Fulkerson),例：,思路：从一可行流出发，检查关于此流是否存在增广链。若存在增广链，则增大流量，使此链变为非增广链；这时再检查是非还有增广链，若还有，继续调整，直至不存在增广链为止。,v5,v1,v2,v3,v4,v6,(2, 2),(8, 3),(3, 1 ),(2, 2),(4, 1),(2, 1),(2, 2),(5, 3),(0, +),(v1,5),(v3,3),(-v4,1),(v2,1),(v5,1),按 =1进行调整，可得下图：,第一步：寻找增广链，通过给结点标号实现,第二步：调整可行流(增广链)的流量,v5,v1,v2,v3,v4,v6,(2, 2),(8, 4),(3, 0),(2, 2),(4, 2),(2, 2),(2, 2),(5, 4),(0, +),(v1,4),(v3,2),按同样的步骤找可行流。,此时,标号过程无法进行下去，算法结束。,三、标号算法的理论依据,定义,截集,截量,截集的概念将任何复杂的网络抽象成两个点之间的流量关系：,显然，若把截集去掉，则从vs到vt的路将不存在。截量制约了从vs到vt的流量。,最小截集,定理 可行流 f *是最大流的充要条件是不存在关于f *的增广链。,证明：,该定理证明的充分性部分就是标号法的寻找增广链过程；其必要性部分就是调整可行流的过程。,v5,v1,v2,v3,v4,v6,(2, 2),(8, 4),(3, 0),(2, 2),(4, 2),(2, 2),(2, 2),(5, 4),(0, +),(v1,4),(v3,2),例：,四、最大流最小截集的标号法举例,(0,+),(vs,6),(-v2,6),(v3,1),(v4,1),(0,),(vs,5),(v2,2),(-v5,2),(v4,2),(0,),(vs,3),(-v2,3),最小截集,(0,),(vs,5),(v2,2),(-v5,2),(v4,2),第五节 最小费用最大流问题,一、问题的提出,v1,v2,vs,v3,vt,(4, 10),(1, 8),(6, 2),(3, 10),(2, 5),(1, 7),(2, 4),二、算法的理论基础,(1) 若 f 是流量为 v( f ) 的所有可行流中费用最小者，而 是关于 f 的所有增广链中费用最小的增广链，那么沿 去调整 f ，得到的可行流 f ，就是流量为v( f )的所有可行流中的最小费用流。这样，当f 是最大流时,也就得到了我们所要的最小费用最大流。,由于同一流量存在多个可行流 f ，所以一定存在费用最小的可行流 f 。设 是关于可行流 f 的一条增广链，以 =1调整 f 得到新的可行流 f ，b( f )比b( f )增加的费用为：,把调整后增加的费用称为这条增广链 的费用。,已知最小费用流 f ，问题的关键是如何找到关于 f 的最小费用增广链 ，从而沿 去调整 f ，得到新的最小费用流 f 。,找关于 f 的最小费用增广链 ，等价于求从vs到vt的最短路。,已知下图为关于 f 的最小费用增广链,其最小费用：bs1+b2tb21,-bs1,-b21,-b2t,从vs到vt的路为vsv1 v2 vt，距离为bs1+b2tb21 ，与最小费用相等。,三、求解方法,v1,v2,vs,v3,vt,4,1,6,3,2,1,2,解： （1）构造赋权有向图W（f（0） 用标号法求最短路,(vs,1),(0,0),v1,v2,vs,v3,vt,4,1,6,3,2,1,2,(vs,1),(0,0),(v2,3),v1,v2,vs,v3,vt,4,1,6,3,2,1,2,(vs,1),(0,0),(v2,3),(v2,4),v1,v2,vs,v3,vt,4,1,6,3,2,1,2,(vs,1),(0,0),(v2,3),(v2,4),(v1,4),由此得到vs到vt的最短路：,v1,v2,vs,v3,vt,(4, 10),(1, 8),(6, 2),(3, 10),(2, 5),(1, 7),(2, 4),(vs,1),(v2,3),(v1,4),v1,v2,vs,v3,vt,(0, 10),(0, 8),(0, 2),(0, 10),(0, 5),(0, 7),(0, 4),调整f（0）= 0,弧旁数字为(fij,cij)。,调整最短路对应的增广链， =5。,(5, 8),(5, 5),(5, 7),（2）构造赋权有向图W（f（1）,v1,v2,vs,v3,vt,4,1,6,3,1,2,-1,-2,-1,v1,v2,vs,v3,vt,4,1,6,3,1,2,-1,-2,-1,用标号法求出最短路：,v1,v2,vs,v3,vt,(0, 10),(5, 8),(0, 2),(0, 10),(5, 5),(5, 7),(0, 4),调整最短路对应的增广链， =2。,(2, 10),(7, 7),（3）构造赋权有向图W（f（2）,v1,v2,vs,v3,vt,4,1,6,3,-1,2,-1,-2,-4,用标号法求出最短路：,v1,v2,vs,v3,vt,4,1,6,3,-1,2,-1,-2,-4,调整最短路对应的增广链， =3。,v1,v2,vs,v3,vt,(0, 10),(5, 8),(0, 2),(0, 10),(5, 5),(5, 7),(0, 4),(2, 10),(7, 7),(8, 8),(3, 10),(3, 4),（4）构造赋权有向图W（f（3）,v1,v2,vs,v3,vt,4,-1,6,3,-1,2,-2,-2,-4,-3,用标号法求出最短路：,v1,v2,vs,v3,vt,4,-1,6,3,-1,2,-2,-2,-4,-3,调整最短路对应的增广链， =1。,v1,v2,vs,v3,vt,(0, 10),(5, 8),(0, 2),(0, 10),(5, 5),(5, 7),(0, 4),(2, 10),(7, 7),(8, 8),(3, 10),(3, 4),(3, 10),(4, 5),(4, 10),(4, 4),（5）构造赋权有向图W（f（4）,v1,v2,vs,v3,vt,4,-1,6,3,-1,-2,-2,-4,-3,2,此时已不存在从vs到vt的最短路。,v1,v2,vs,v3,vt,(0, 10),(5, 8),(0; 6, 2),(0, 10),(5, 5),(5, 7),(0, 4),(2, 10),(7; 1,7),(8; 1, 8),(3, 10),(3, 4),(3; 4, 10),(4; 2, 5),(4; 3,10),(4; 2,4),弧旁数字为(fij; bij,cij),第六节 中国邮递员问题,一、问题的提出,用图的语言描述： 给定一个连通图，在每边ei 上赋予一个非负的权w(ei ),要求一个圈（未必是简单的），过每边至少一次，并使圈的总权最小。,（遍历全部边最短行程问题）邮递员从办公地出发将信件投递到所辖区域的每个地点，再回到出发地，希望每条路只走一次，则行走路程最短。但实际不可能，有的路必须重复。问题：重复哪些路，既能完成任务，而行走路程又最短？,二、解法,(1) 概念：Euler图每个顶点的次数均为偶数的连通图(2) 结论：一个连通图G能一笔画 G为Euler图算法：Step1：化圈G为Euler图G；Step2：检验: ( I ) 每条边至多重复一次; ( II ) 在图G的每一个圈中,重复边的长度之和应小于或等于圈的长度的一半；Step3：调整, 转Step2。,三、应用举例,v1,v2,v3,v4,v5,v6,v7,v8,v9,5,5,2,6,9,4,4,4,3,4,上图有四个奇点,分成两对,v2,v4一对, v6,v8一对,3,4,v1,v2,v3,v4,v5,v6,v7,v8,v9,5,5,2,6,9,4,4,4,3,4,3,4,任取v2、v4之间的一条链， v6、v8之间的一条链，加上重复边。 如下图所示:,v1,v2,v3,v4,v5,v6,v7,v8,v9,5,5,2,6,9,4,4,4,3,4,3,4,根据检验方法( I ), 同时去掉某些边的两条重复边，图上仍然无奇点，而总长度下降。,检验每一个圈的重复边， 对不符合检验方法( II )的作调整。,v1,v2,v3,v4,v5,v6,v7,v8,v9,5,5,2,6,9,4,4,4,3,4,3,4,此时达到最优方案，任一个欧拉圈就是邮递员的最优邮递线路。,