图与网络分析物流运筹学

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图与网络分析在物流系统中的应用,(,Graph Theory and Network Analysis),图与网络的基本知识,最短路问题,树及最小树问题,1,B,D,A,C,A,B,C,D,哥尼斯堡七空桥,一笔画问题,2,应用及解决的问题,配送运输规划问题,物流车辆规划调度系统,物流园区规划,3,一、,图与网络的基本知识,（一）、,图与网络的基本概念,E,A,D,C,B,1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）,4,一个图是由点集 和 中元素的无序对的一个集合 构成的二元组，记为,G,=(,V，E,)，,其中,V,中的元素 叫做顶点，,V,表示图,G,的点集合；,E,中的元素 叫做边，,E,表示图,G,的边集合。,v,1,v,2,v,3,v,4,v,5,v,6,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,e,9,e,10,例,图1,5,2、如果一个图是由点和边所构成的，则称其为无向图，记作,G,= (,V，E,)，,连接点的边记作,v,i, v,j,，,或者,v,j, v,i,。,3、如果一个图是由点和弧所构成的，那么称它为有向图，记作,D,=(,V, A,)，,其中,V,表示有向图,D,的点集合，,A,表示有向图,D,的弧集合。一条方向从,v,i,指向,v,j,的弧，记作(,v,i, v,j,)。,v,4,v,6,v,1,v,2,v,3,v,5,V = ,v,1,v,2,v,3,v,4,v,5,v,6,，,A = (,v,1,v,3,) , (,v,2,v,1,) , (,v,2,v,3,) ,(,v,2,v,5,) , (,v,3,v,5,) , (,v,4,v,5,) ,(,v,5,v,4,) , (,v,5,v,6,) ,图2,6,4、一条边的两个端点是相同的,那么称为这条边是环。,5、如果两个端点之间有两条以上的边，那么称为它们为多重边。,6、一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。,7、每一对顶点间都有边相连的无向简单图称为完全图。,有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。,7,v,1,v,2,v,3,v,4,v,5,v,6,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,e,9,e,10,度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。,8、以点,v,为端点的边的个数称为点,v,的度（次），记作 。,图中,d,(,v,1,)= 4，,d,(,v,6,)= 4（,环计两度,）,8,定理1 所有顶点度数之和等于所有边数的2倍。,定理2,在任一图中，奇点的个数必为偶数。,所有顶点的入次之和等于所有顶点的出次之和。,有向图中，以,v,i,为始点的边数称为点,v,i,的出次，用 表示 ；以,v,i,为终点的边数称为点,v,i,的入次，,用 表示；,v,i,点的出次和入次之和就是该点的次。,9,9、设,G,1,=（ V,1, E,1,），G,2,=（ V,2,E,2,）,如果,V,2,V,1,E,2,E,1,称,G,2,是,G,1,的子图；如果,V,2,= V,1,E,2,E,1,称,G,2,是,G,1,的部分图或支撑子图。,v,1,v,2,v,3,v,4,v,5,v,6,v,7,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,e,9,e,10,e,11,(,a,),e,5,e,7,v,1,v,2,v,5,v,6,v,7,e,1,e,6,e,8,(,b,),子图,v,1,v,2,v,3,v,4,v,5,v,6,v,7,e,1,e,6,e,7,e,9,e,10,e,11,(,c,),支撑子图,10,在实际应用中，给定一个图,G=（V，E）,或有向图,D=（V，A）,，,在,V,中指定两个点，一个称为始点（或发点），记作,v,1,，,一个称为终点（或收点），记作,v,n,，,其余的点称为中间点。对每一条弧 ，对应一个数 ，称为弧上的,“,权,”,。通常把这种赋权的图称为网络。,10、由两两相邻的点及其相关联的边构成的点边序列称为链。,如:,v,0,，,e,1,，,v,1,，,e,2,，,v,2,，,e,3,，,v,3,v,n-1,e,n,，,v,n,，,记作（,v,0,，,v,1,，,v,2,，,v,3,v,n-1,，,v,n,），,11,e,3,v,1,v,2,v,3,v,4,v,5,v,6,e,7,e,8,e,1,e,2,e,4,e,5,e,6,e,9,e,10,11、图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。,其链长为,n,，,其中,v,0,，,v,n,分别称为链的起点和终点 。若链中所含的边均不相同，则称此链为简单链；所含的点均不相同的链称为初等链 , 也称通路。,12,（二）、 图的矩阵表示,对于网络（赋权图）,G=（V，E）,，,其中边,有权 ，构造矩阵 ，其中：,称矩阵,A,为网络,G,的权矩阵。,设图,G=（V，E）,中顶点的个数为,n,，,构造一个,矩阵 ，其中：,称矩阵,A,为网络,G,的邻接矩阵。,13,例,权矩阵为：,邻接矩阵为：,v,5,v,1,v,2,v,3,v,4,v,6,4,3,3,2,2,5,6,4,3,7,14,问题,图（顶点、边）、有限图、无限图,无向图、有向图、环、多重边,多重图、简单图、完全图、有向完全图、二部图,顶点的次、出次、入次、悬挂点、孤立点、奇点、偶点,子图、生成子图（支撑图）、网络（赋权图）,链、初等链、圈、初等圈、回路、连通图,图的矩阵表示、邻接矩阵,欧拉道路、欧拉回路、中国邮路问题,15,树的概念,树、树叶、分枝点,数的性质,生成子图、生成树、树枝、弦,最小生成树,避圈法、破圈法,有向树、根树、叶、分枝点、叉树,16,二、 树及最小树问题,已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,v,1,v,2,v,3,v,4,v,5,v,6,1、一个连通的无圈的无向图叫做树。,树中次为1的点称为树叶，次大于1的点称为分支点。,17,树,的性质：,（1）,树必连通，但无回路（圈）。,（2）,n,个顶点的树必有,n-1,条边,。,（3）,树,中任意两个顶点之间，恰有且仅有一条链（初等链）。,（4）树,连通，但去掉任一条边， 必变为不连通。,（5）,树,无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。,v,1,v,2,v,3,v,4,v,5,v,6,18,2、 设图 是图,G,=(,V , E,),的一支撑子图，,如果图 是一个树,那么称,K,是,G,的一个生成树（支撑树），或简称为图,G,的树。图,G,中属于生成树的边称为树枝，不在生成树中的边称为弦。,一个图,G,有生成树的充要条件是,G,是连通图。,v,1,v,2,v,3,v,4,v,5,v,1,v,2,v,3,v,4,v,5,19,用避圈法求出下图的一个生成树。,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,v,1,v,2,v,3,v,4,v,5,e,2,e,4,e,6,e,8,v,1,v,2,v,3,v,4,v,5,e,1,e,2,e,3,e,4,e,5,e,6,e,7,e,8,20,（一）,破圈法,21,（二）,避圈法,在图中任取一条边,e,1,，,找一条与,e,1,不构成圈的边,e,2,，,再找一条与,e,1,，,e,2,不构成圈的边,e,3,。,一般设已有,e,1,，,e,2,，,e,k,，,找一条与,e,1,，,e,2,，,e,k,中任何一些边不构成圈的边,e,k,+1,，,重复这个过程，直到不能进行为止。,22,v,1,v,2,v,3,v,4,v,5,v,6,v,1,v,3,v,1,v,3,v,2,v,1,v,3,v,2,v,5,v,6,v,1,v,3,v,2,v,5,v,6,v,4,v,1,v,3,v,2,v,5,23,3、最小生成树问题,如果图 是图,G,的一个生成树，那么称,E,1,上所有边的权的和为生成树,T,的权，记作,S(T),。,如果图,G,的生成树,T*,的权,S(T*),，,在,G,的所有生成树,T,中的权最小，即,那么称,T*,是,G,的最小生成树。,某六个城市之间的道路网如图,所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。,v,1,v,2,v,3,v,4,v,5,v,6,6,5,1,5,7,2,3,4,4,5,v,1,v,2,v,3,v,4,v,5,v,6,1,2,3,4,4,24,v,1,v,2,v,3,v,4,v,5,1,4,2,3,1,3,5,2,25,最短路的一般提法为：设 为连通图，图中各边,有权 （ 表示 之间没有边），,为图中任意两点，求一条路 ，使它为从 到 的所有路中总权最短。即：,最小。,(一)、 狄克斯屈拉(,Dijkstra,),算法,适用于,w,ij,0,，给出了从,v,s,到任意一个点,v,j,的最短路。,三 、最短路问题,26,算法步骤：,1.给始点,v,s,以,P,标号 ，这表示从,v,s,到,v,s,的最短距离为0，其余节点均给,T,标号， 。,2.设节点,v,i,为刚得到,P,标号的点，考虑点,v,j,，,其中,，且,v,j,为,T,标号。对,v,j,的,T,标号进行如下修改：,3.比较所有具有,T,标号的节点，把最小者改为,P,标号，即：,当存在两个以上最小者时，可同时改为,P,标号。若全部节点均为,P,标号，则停止，否则用,v,k,代替,v,i,，,返回步骤（2）。,27,例一、,用,Dijkstra,算法求下图从,v,1,到,v,6,的最短路。,v,1,v,2,v,3,v,4,v,6,v,5,3,5,2,2,4,2,4,2,1,解,（1）首先给,v,1,以,P,标号，给其余所有点,T,标号。,（2）,（3）,（4）,28,v,1,v,2,v,3,v,4,v,6,v,5,3,5,2,2,4,2,4,2,1,（5）,（6）,（7）,（8）,（9）,（10）,反向追踪得,v,1,到,v,6,的最短路为：,29,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求从,1,到,8,的最短路径,30,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1, w,1,=0,min c,12,c,14,c,16,=min 0+2,0+1,0+3=min 2,1,3=1,X=1,4, p,4,=1,p,4,=1,p,1,=0,31,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,4,min c,12,c,16,c,42,c,47,=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2,X=1,2,4, p,2,=2,p,1,=0,p,4,=1,p,2,=2,32,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,min c,13,c,23,c,25,c,47,=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3,X=1,2,4,6, p,6,=3,p,2,=2,p,4,=1,p,1,=0,p,6,=3,33,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,min c,23,c,25,c,47,c,67,=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3,X=1,2,4,6,7, p,7,=3,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,34,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,7,min c,23,c,25,c,75,c,78,=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6,X=1,2,4,5,6,7, p,5,=6,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,35,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,4,6,7,min c,23,c,53,c,58,c,78,=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8,X=1,2,3,4,5,6,7, p,3,=8,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,36,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,3,4,6,7,min c,38,c,58,c,78,=min 8+6,6+4,3+7=min 14,10,11=10,X=1,2,3,4,5,6,7,8, p,8,=10,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,p,8,=10,37,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X,=1,2,3,4,6,7,8,1,到8的最短路径为1，4，7，5，8，长度为10。,p,2,=2,p,4,=1,p,1,=0,p,6,=3,p,7,=3,p,5,=6,p,3,=8,p,8,=10,38,求从,V,1,到,V,8,的最短路线。,39,V,1,V,2,V,3,V,4,V,5,V,6,V,7,V,8,P,=0,T=+,T=+,T=+,T=+,T=+,T=+,T=+,P,=T=3,T=+,T=7,T=+,T=+,T=+,T=+,T=6,T=7,P,=T=5,T=+,T=+,T=+,P,=T=6,T=6,T=8,T=+,T=+,P,=T=6,T=8,T=9,T=12,P,=T=8,T=10,T=10,P,=T=9,T=11,再无其它,T,标号，所以,T(V,8,)=P(V,8,)=10; min L()=10,P,=T=10,40,由此看到，此方法不仅求出了从,V,1,到,V,8,的最短路长，同时也求出了从,V,1,到 任意一点 的最短路长。将从,V,1,到 任一点的最短路权标在图上，即可求出从,V,1,到 任一点的最短路线。本例中,V,1,到,V,8,的最短路线是：,v,1, v,2, v,5, v,6, v,8,41,6,2,3,1,2,1,6,4,10,3,6,2,3,4,2,10,42,（二）、 逐次逼近法,算法的基本思路与步骤：,首先设任一点,v,i,到任一点,v,j,都有一条弧。,显然，从,v,1,到,v,j,的最短路是从,v,1,出发，沿着这条路到某个点,v,i,再沿弧(,v,i,v,j,),到,v,j,。,则,v,1,到,v,i,的这条路必然也是,v,1,到,v,i,的所有路中的最短路。设,P,1j,表示从,v,1,到,v,j,的最短路长，,P,1i,表示从,v,1,到,v,i,的最短路长，则有下列方程：,开始时，令,即用,v,1,到,v,j,的直接距离做初始解。,从第二步起，使用递推公式：,求 ，当进行到第,t,步，若出现,则停止计算， 即为,v,1,到各点的最短路长。,43,例二、,1,8,v,1,v,2,v,3,v,4,v,5,2,6,3,5,1,3,5,2,1,1,2,1,1,v,6,v,7,v,8,3,7,求图中,v,1,到,各点的最短路,44,1,8,v,1,v,2,v,3,v,4,v,5,2,6,3,5,1,3,5,2,1,1,2,1,1,v,6,v,7,v,8,3,7,（0，0）,（,v,3,，-5）,（,v,1,，-2）,（,v,3,，-7）,（,v,2,，-3）,（,v,4,，-5）,（,v,3,，-1）,（,v,6,，6）,45,例三、求：5年内，哪些年初购置新设备，使5年内的总费用最小。,解：（1）分析：可行的购置方案（更新计划）是很多的，,如： 1） 每年购置一台新的，则对应的费用为：,11+11+12+12+13 +5+5+5+5+5 = 84,2 )第一年购置新的，一直用到第五年年底，则总费用为：,11+5+6+8+11+18 = 59,显然不同的方案对应不同的费用。,第,i,年度,1 2 3 4 5,购置费,11 11 12 12 13,设备役龄,0-1 1-2 2-3 3-4 4-5,维修费用,5 6 8 11 18,46,（2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。,求解步骤：,1）画赋权有向图：,设,V,i,表示第,i,年初，(,V,i,V,j,),表示第,i,年初购买新设备用到第,j,年初（,j-1,年底），而,W,i j,表示相应费用，则5年的一个更新计划相当于从,V,1,到,V,6,的一条路。,2）求解 （标号法）,47,W,12,=11+5=16,W,13,=11+5+6=22,W,14,=11+5+6+8=30,W,15,=11+5+6+8+11=41,W,16,=11+5+6+8+11+18=59,W,23,=11+5=16 W,24,=11+5+6=22,W,25,=11+5+6+8=30 W,26,=11+5+6+8+11=41,W,45,=12+5=17,W,46,=12+5+6=23,W,56,=13+5=18,W,34,=12+5=17,W,35,=12+5+6=23,W,36,=12+5+6+8=31,48,例四、 某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。,年份,1,2,3,4,5,购置费,18,20,21,23,24,使用年数,0,1,1,2,2,3,3,4,4,5,维修费,5,7,12,18,25,49,年份,1,2,3,4,5,购置费,18,20,21,23,24,使用年数,0,1,1,2,2,3,3,4,4,5,维修费,5,7,12,18,25,28,v,1,v,2,v,3,v,4,v,5,v,6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,50,四、 最大流问题,（一）、 基本概念,1、设一个赋权有向图,D=（V, E）,在,V,中指定一个发点,v,s,和一个收点,v,t,其它的点叫做中间点。对于,D,中的每一个弧（,v,i,v,j,）,E,都有一个非负数,c,ij,叫做弧的容量。我们把这样的图,D,叫做一个容量网络，简称网络，记做,D,=（,V，E，C,）。,网络,D,上的流，是指定义在弧集合,E,上的一个函数,其中,f,(,v,i,v,j,) =,f,ij,叫做弧(,v,i,，,v,j,),上的流量。,51,2、称满足下列条件的流为可行流：,（1）容量条件：对于每一个弧（,v,i,v,j,）,E,有 0,f,ij,c,ij,。,（2）,平衡条件：,对于发点,v,s,，,有,对于收点,v,t,，,有,对于中间点，有,可行流中,f,ij,c,ij,的弧叫做饱和弧，,f,ij,c,ij,的弧叫做非饱和弧。,f,ij,0,的弧为非零流弧，,f,ij,0,的弧叫做零流弧。,52,13 (5),9 (3),4 (1),5 (3),6(3),5 (2),5 (2),5 (0),4 (2),4 (1),9 (5),10 (1),图中 为零流弧，其余为非饱和弧。,53,3、容量网络,G，,若 为网络中从,v,s,到,v,t,的一条链，给 定向为从,v,s,到,v,t,，,上的弧凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示。,f,是一个可行流，如果满足：,则称 为从,v,s,到,v,t,的关于,f,的一条增广链。,推论,可行流,f,是最大流的充分必要条件是不存在从,v,s,到,v,t,的关于,f,的一条可增广链。,即 中的每一条弧都是非饱和弧,即 中的每一条弧都是非零流弧,54,13 (5),9 (3),4 (1),5 (3),6(3),5 (2),5 (2),5 (0),4 (2),4 (1),9 (5),10 (1),是一个增广链,显然图中增广链不止一条,55,4、容量网络,G =（V，E，C），,v,s,为始点，,v,t,为终点。如果把,V,分成两个非空集合,使 ，则所有始点属于,S，,而终点属于 的弧的集合，称为由,S,决定的截集,记作 。截集 中所有弧的容量之和，称为这个截集的容量，记为 。,v,s,v,1,v,2,v,4,v,3,v,t,3,7,4,5,5,6,3,7,8,S,56,13 (5),9 (3),4 (1),5 (3),6(3),5 (2),5 (2),5 (0),4 (2),4 (1),9 (5),10 (1),设 ，,则截集为,容量为24,57,13 (5),9 (3),4 (1),5 (3),6(3),5 (2),5 (2),5 (0),4 (2),4 (1),9 (5),10 (1),设 ，,则截集为,容量为20,58,（二） 求最大流的标号法,标号过程：,1,给发点,v,s,标号（0，+）。,2,取一个已标号的点,v,i,，,对于,v,i,一切未标号的邻接点,v,j,按下列规则处理：,（1）如果边 ，且 ，那么给,v,j,标号 ，其中：,（2）如果边 ，且 ，那么给,v,j,标号 ，其中：,3重复步骤2，直到,v,t,被标号或标号过程无法进行下去，则标号结束。若,v,t,被标号，则存在一条增广链，转调整过程；若,v,t,未被标号，而标号过程无法进行下去，这时的可行流就是最大流。,59,调整过程,设,1令,2去掉所有标号，回到第一步，对可行流重新标号。,60,求下图所示网络中的最大流，弧旁数为,(1 ,1),v,2,v,1,v,4,v,3,v,s,v,t,(3 , 3),(5 , 1),(1 , 1),(4 ,3),(2 , 2),(3 ,0),(5 ,3),(2 ,1),(1 ,1),v,2,v,1,v,4,v,3,v,s,v,t,(3 , 3),(5 , 1),(1 , 1),(4 ,3),(2 , 2),(3 ,0),(5 ,3),(2 ,1),（0，+）,（-,v,1, 1）,（+,v,s, 4）,（-,v,2,，1）,（+,v,2,，1）,(+,v,3,，1),61,(1 ,0),v,2,v,1,v,4,v,3,v,s,v,t,(3 , 3),(5 , 2),(1 , 0),(4 ,3),(2 , 2),(3 ,0),(5 ,3),(2 ,2),(1 ,0),v,2,v,1,v,4,v,3,v,s,v,t,(3 , 3),(5 , 2),(1 , 0),(4 ,3),(2 , 2),(3 ,0),(5 ,3),(2 ,2),（0，+）,（+,v,s, 3）,最小截集,62,13 (5),9 (3),4 (1),5 (3),6(3),5 (2),5 (2),5 (0),4 (2),4 (1),9 (5),10 (1),63,13 (11),9 (9),4 (0),5 (5),6(6),5 (5),5 (4),5 (4),4 (4),4 (3),9 (9),10 (7),截集1,截集2,最小截量为：,9+6+5=20,64,70（70）,70（50）,130（100）,150（130）,150（150）,50（20）,50（50）,120（30）,100（100）, （120 ）, （230 ）, （150 ）, （200 ）,65,第五节 最小费用最大流问题,定义8.17,已知网络,G =（V，E，C，,d,），,f,是,G,上的一个可行流， 为一条从,v,s,到,v,t,的增广链， 称为链的费用。,若,*,是从,v,s,到,v,t,的增广链中费用最小的增广链，则称,*,是最小费用增广链。,结论：,如果可行流,f,在流量为,W(,f,),的所有可行流中的费用最小，并且,*,是关于,f,的所有增广链中的费用最小的增广链，那么沿增广链,*,调整可行流,f,，,得到的新可行流,f,*,也是流量为,W(,f,*,),的所有可行流中的最小费用流。当,f,*,是最大流时，就是最小费用最大流。,66,寻找关于,f,的最小费用增广链：,构造一个关于,f,的赋权有向图,L(,f,),，其顶点是原网络,G,的顶点，而将,G,中的每一条弧 (,v,i, v,j,),变成两个相反方向的弧（,v,i,，,v,j,）,和(,v,j,v,i,)，,并且定义图中弧的权,l,ij,为：,1.当 ，令,2.当（,v,j,，,v,i,）,为原来网络,G,中（,v,i,，,v,j,）,的反向弧，令,在网络,G,中寻找关于,f,的最小费用增广链等价于在,L(,f,),中寻求从,v,s,到,v,t,的最短路。,67,步骤：,（1）取零流为初始可行流 ，,f,(0) =0。,（2）,一般地，如果在第,k-1,步得到最小费用流,f,(,k,-1),，则构造图,L(,f,(,k,-1),)。,（3）,在,L(,f,(,k,-1),),中，寻求从,v,s,到,v,t,的最短路。若不存在最短路，则,f,(,k,-1),就是最小费用最大流；否则转(4)。,（4）如果存在最短路，则在可行流,f,(,k,1),的图中得到与此最短路相对应的增广链，在增广链上，对,f,(,k,1),进行调整，调整量为：,68,令,得到新可行流,f,(,k,),。对,f,(,k,),重复上面步骤，返回（2）。,例8.11,求网络的最小费用最大流，弧旁权是（,b,ij, c,ij,）,(3 ,2),v,s,v,2,v,1,v,t,v,3,(1 ,4),(6 ,7),(4 ,8),(1 ,6),(2 ,5),(2 ,3),69,3,v,s,v,2,v,1,v,t,v,3,1,6,4,1,2,2,(1),L(,f,(0),),(3 ,2),v,s,v,2,v,1,v,t,v,3,(1 ,4),(6 ,7),(4 ,8),(1 ,6),(2 ,5),(2 ,3),0,v,s,v,2,v,1,v,t,v,3,3,0,0,3,3,3,(2),f,( 1),1,=3,W(,f,(1),)=3,1,(3),L(,f,(1),),2,3,v,s,v,2,v,1,v,t,v,3,1,6,4,1,2,1,2,70,1,v,s,v,2,v,1,v,t,v,3,4,0,0,3,4,3,(4,),f,( 2),2,=1,W(,f,(2),)=4,(3 ,2),v,s,v,2,v,1,v,t,v,3,(1 ,4),(6 ,7),(4 ,8),(1 ,6),(2 ,5),(2 ,3),(5),L(,f,(2),),3,v,s,v,2,v,1,v,t,v,3,1,4,1,2,2,2,3,1,6,6,1,v,s,v,2,v,1,v,t,v,3,4,0,1,4,5,3,(6,),f,( 3),3,=1,W(,f,(3),)=5,71,(7),L(,f,(3),),v,s,v,2,v,1,v,t,v,3,3,1,4,1,-2,2,3,1,6,1,v,s,v,2,v,1,v,t,v,3,4,3,4,4,5,0,(8,),f,( 4),4,=3,W(,f,(4),)=8,0,v,s,v,2,v,1,v,t,v,3,4,4,5,5,5,0,5,=1,W(,f,(5),)=9,(10,),f,( 5),1,-2,3,1,v,s,v,2,v,1,v,t,v,3,3,4,1,2,6,(9),L,(,f,( 4),),-4,-6,72,3,1,2,1,4,(11),L(,f,( 5),),1,2,6,4,v,s,v,2,v,1,v,t,v,3,6,73,第六节 中国邮递员问题,一、 欧拉回路与道路,定义8.18,连通图,G,中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。,具有欧拉回路的图称为欧拉图。,定理8.7,一个多重连通图,G,是欧拉图的充分必要条件是,G,中无奇点。,推论 一个多重连通图,G,有欧拉道路的充分必要条件是,G,有且仅有两个奇点。,74,A,B,C,D,75,二、,奇偶点图上作业法,（1）找出图,G,中的所有的奇顶点，把它们两两配成对，而每对奇点之间必有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点。,（2）如果边,e,=（,u,v,）,上的重复边多于一条，则可从重复边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点。,（3）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）。,76,判定标准1:,在最优邮递路线上，图中的每一条边至多有一条重复边。,判定标准2 :,在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半。,例8.12,求解下图所示网络的中国邮路问题，图中数字为该边的长。,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,5,5,6,4,3,4,77,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,5,5,6,4,3,4,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,6,4,3,4,5,5,l,12,+2,l,23,+2,l,36,+2,l,89,+2,l,78,+,l,69,+,l,14,+2,l,47,=51,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,5,5,6,4,3,4,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,5,5,6,4,3,4,78,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,2,4,3,4,4,9,5,5,6,4,3,4,79,