图与网络分析物流运筹学

《图与网络分析物流运筹学》由会员分享，可在线阅读，更多相关《图与网络分析物流运筹学（79页珍藏版）》请在金锄头文库上搜索。

1、图与网络分析在物流系统中的应用图与网络分析在物流系统中的应用 (Graph Theory and Network Analysis)图与网络的基本知识图与网络的基本知识最短路问题最短路问题 树及最小树问题树及最小树问题1BDACABCD哥尼斯堡七空桥哥尼斯堡七空桥一笔画问题一笔画问题2应用及解决的问题应用及解决的问题配送运输规划问题物流车辆规划调度系统物流园区规划3一、一、 图与网络的基本知识图与网络的基本知识（一）、（一）、图与网络的基本概念图与网络的基本概念 EADCB 1、一个图是由点和连线组成。（连线可带箭头，也可、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）

2、不带，前者叫弧，后者叫边）4一一个个图图是是由由点点集集 和和 中中元元素素的的无无序序对对的的一一个个集集合合 构构成成的的二二元元组组，记记为为G G =(=(V V，E E) )，其其中中 V V 中中的的元元素素 叫叫做做顶顶点点，V 表表示示图图 G 的的点点集集合合；E 中的元素中的元素 叫做边，叫做边，E 表示图表示图 G 的边集合。的边集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例图图15 2 2、如如果果一一个个图图是是由由点点和和边边所所构构成成的的，则则称称其其为为无无向向图图，记记作作G G = (= (V V，E E) )，连接点的边记作

3、连接点的边记作 v vi i , v , vj j ，或者或者 v vj j , v , vi i 。 3 3、如果一个图是由点和弧所构成的，那么称它为有向图，记、如果一个图是由点和弧所构成的，那么称它为有向图，记作作D D=(=(V, AV, A) )，其中其中V V 表示有向图表示有向图D D 的点集合，的点集合，A A 表示有向图表示有向图D D 的弧的弧集合。一条方向从集合。一条方向从v vi i指向指向v vj j 的弧，记作的弧，记作( (v vi i , v , vj j) )。v4v6v1v2v3v5V = v1 , v2 , v3 , v4 , v5 , v6 ，A = (v

4、1 , v3 ) , (v2 , v1) , (v2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) 图图26 4 4、一条边的两个端点是相同的、一条边的两个端点是相同的, ,那么称为这条边是环。那么称为这条边是环。 5 5、如果两个端点之间有两条以上的边，那么称为它们、如果两个端点之间有两条以上的边，那么称为它们为多重边。为多重边。 6 6、一个无环，无多重边的图称为简单图，一个无环，、一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。有多重边的图称为多重图。 7、每一对顶点间都有

5、边相连的无向简单图称为完全图。、每一对顶点间都有边相连的无向简单图称为完全图。 有向完全图则是指任意两个顶点之间有且仅有一条有有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。向边的简单图。7v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 度为零的点称为弧立点，度为度为零的点称为弧立点，度为1 1的点称为悬挂点。悬挂的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。数的点称为偶点。 8 8、以点、以点v v为端点的边的个数称为点为端点的边的个数称为点v v 的度（次），记作的度（

6、次），记作 。图中图中 d(v1)= 4，d(v6)= 4（环计两度环计两度）8 定理定理1 1 所有顶点度数之和等于所有边数的所有顶点度数之和等于所有边数的2 2倍。倍。 定理定理定理定理2 2 2 2 在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。 所有顶点的入次之和等于所有顶点的出次之和。所有顶点的入次之和等于所有顶点的出次之和。 有有向向图图中中，以以 v vi i 为为始始点点的的边边数数称称为为点点v vi i的的出出次次，用用 表示表示 ；以；以 v vi i 为终点的边数称为点为终点的边数称为点v vi i 的入次，的入次，用用 表示；表示；v vi i 点的

7、出次和入次之和就是该点的次。点的出次和入次之和就是该点的次。9 9 9 9 9、设、设、设、设 GG1 1= =（ V V1 1 , E , E1 1 ），），），），GG2 2 = =（ V V2 2 ,E ,E2 2 ）如果如果 V2 V1 , , E2 E1 称称 G2 是是G1 的子图；如果的子图；如果 V2 = V1 , , E2 E1 称称 G2 是是 G1 的部分图或支撑子图。的部分图或支撑子图。 v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图子图v1v2v3v4v5v6v7e1e6e7e9e1

8、0e11(c)支撑子图支撑子图10 在实际应用中，给定一个图在实际应用中，给定一个图G=（V，E）或有向或有向图图D=（V，A），在在V中指定两个点，一个称为始点中指定两个点，一个称为始点（或发点），记作（或发点），记作v1 ，一个称为终点（或收点），记作一个称为终点（或收点），记作vn ，其余的点称为中间点。对每一条弧其余的点称为中间点。对每一条弧 ，对，对应一个数应一个数 ，称为弧上的，称为弧上的“权权”。通常把这种赋权的。通常把这种赋权的图称为网络。图称为网络。 10 10、由两两相邻的点及其相关联的边构成的点边序列、由两两相邻的点及其相关联的边构成的点边序列称为链。称为链。 如如: :

9、v v0 0 ，e e1 1，v v1 1，e e2 2，v v2 2，e e3 3 ， v v3 3 , ,v,vn-1n-1 , , e en n ， v vn n，记作（记作（ v v0 0 ， v v1 1 ， v v2 2， v v3 3 , , , , v vn-1n-1 ， v vn n ），）， 11e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10 11 11、图中任意两点之间均至少有一条通路，则称此图、图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。为连通图，否则称为不连通图。 其链长为其链长为 n ，其中其中 v0 ，vn 分别称为链

10、的起点和终点分别称为链的起点和终点 。若链中所含的边均不相同，则称此链为简单链；所含的。若链中所含的边均不相同，则称此链为简单链；所含的点均不相同的链称为初等链点均不相同的链称为初等链 , , 也称通路。也称通路。12（二）、（二）、 图的矩阵表示图的矩阵表示对于网络（赋权图）对于网络（赋权图）G=（V，E），其中边其中边有权有权 ，构造矩阵，构造矩阵 ，其中：，其中：称矩阵称矩阵A A为网络为网络G G的权矩阵。的权矩阵。 设图设图G=（V，E）中顶点的个数为中顶点的个数为n，构造一个构造一个矩阵矩阵 ，其中：，其中： 称矩阵称矩阵A A为网络为网络G G的邻接矩阵。的邻接矩阵。 13例例权

11、矩阵为：权矩阵为：邻接矩阵为：邻接矩阵为：v5v1v2v3v4v6433225643714问题图（顶点、边）、有限图、无限图无向图、有向图、环、多重边多重图、简单图、完全图、有向完全图、二部图顶点的次、出次、入次、悬挂点、孤立点、奇点、偶点子图、生成子图（支撑图）、网络（赋权图）链、初等链、圈、初等圈、回路、连通图图的矩阵表示、邻接矩阵欧拉道路、欧拉回路、中国邮路问题15树的概念树、树叶、分枝点数的性质生成子图、生成树、树枝、弦最小生成树避圈法、破圈法有向树、根树、叶、分枝点、叉树16 二、二、 树及最小树问题树及最小树问题 已已知知有有六六个个城城市市，它它们们之之间间 要要架架设设电电话话

12、线线，要要求求任任意意两个城市均可以互相通话，并且电话线的总长度最短。两个城市均可以互相通话，并且电话线的总长度最短。 v1v2v3v4v5v6 1 1、一个连通的无圈的无向图叫做树。、一个连通的无圈的无向图叫做树。 树中次为树中次为1 1的点称为树叶，次大于的点称为树叶，次大于1 1的点称为分支点。的点称为分支点。17 树树 的性质：的性质： （1 1）树必连通，但无回路（圈）。树必连通，但无回路（圈）。 （2 2）n 个顶点的树必有个顶点的树必有n-1 条边条边。 （3 3）树树 中任意两个顶点之间，恰有且仅有一条链（初中任意两个顶点之间，恰有且仅有一条链（初等链）。等链）。 （4 4）树

13、）树 连通，但去掉任一条边，连通，但去掉任一条边， 必变为不连通。必变为不连通。 （5 5） 树树 无回路（圈），但不相邻的两个点之间加一条无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。边，恰得到一个回路（圈）。v1v2v3v4v5v618 2 2、 设图设图 是图是图G=(V , E )的一支撑子图，的一支撑子图，如果图如果图 是一个树是一个树, ,那么称那么称K 是是G 的一个生成的一个生成树（支撑树），或简称为图树（支撑树），或简称为图G 的树。图的树。图G中属于生成树的中属于生成树的边称为树枝，不在生成树中的边称为弦。边称为树枝，不在生成树中的边称为弦。一个图一个图

14、G 有生成树的充要条件是有生成树的充要条件是G 是连通图。是连通图。 v1v2v3v4v5v1v2v3v4v519用避圈法求出下图的一个生成树。用避圈法求出下图的一个生成树。 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e820（一）（一）破圈法破圈法21（二）（二）避圈法避圈法 在图中任取一条边在图中任取一条边e1，找一条与找一条与e1不构成圈的边不构成圈的边e2，再找一条与再找一条与e1，e2不构成圈的边不构成圈的边e3。一般设已有一般设已有e1，e2，ek，找一条与找一条与e1，e2，ek中任何一

15、中任何一些边不构成圈的边些边不构成圈的边ek+1，重复这个过程，直到不能进行重复这个过程，直到不能进行为止。为止。22v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5233 3、最小生成树问题、最小生成树问题 如如果果图图 是是图图G G的的一一个个生生成成树树，那那么么称称E1上上所所有有边边的的权权的的和和为为生生成成树树T 的的权权，记记作作S(T)。如如果果图图G G的的生生成成树树T* 的权的权S(T*)，在在G 的所有生成树的所有生成树T 中的权最小，即中的权最小，即那么称那么称T*是是G 的最小生成树。的最小生成树。 某六个

16、城市之间的道路网如图某六个城市之间的道路网如图 所示，要求沿着已知长所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最度的道路联结六个城市的电话线网，使电话线的总长度最短。短。 v1v2v3v4v5v66515723445v1v2v3v4v5v61234424v1v2v3v4v51423135225 最短路的一般提法为：设 为连通图，图中各边 有权 （ 表示 之间没有边），为图中任意两点，求一条路 ，使它为从 到 的所有路中总权最短。即： 最小。(一一)、 狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法适用于wij0，给出了从vs到任意一个点vj的最短路。三三 、最短路问

17、题、最短路问题26算法步骤：算法步骤：1.给始点vs以P标号 ，这表示从vs到 vs的最短距离为0，其余节点均给T标号， 。2.设节点 vi 为刚得到P标号的点，考虑点vj，其中 ，且vj为T标号。对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即： 当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。27例一、例一、 用Dijkstra算法求下图从v1到v6的最短路。 v1v2v3v4v6v5352242421 解解 （1）首先给v1以P标号，给其余所有点T标号。（2）（3）（4）28v1v2v3v4v6v

18、5352242421（5）（6）（7）（8）（9）（10）反向追踪得v1到v6的最短路为：29237184566134105275934682求从求从1到到8的最短路径的最短路径30237184566134105275934682X=1, w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, p4=1p4=1p1=031237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, p2=2p1=0p4=1p2=2322

19、37184566134105275934682X=1,2,4min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6, p6=3p2=2p4=1p1=0p6=333237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7, p7=3p2=2p4=1p1=0p6=3p7=334237184566134105275934682X=1,2,4,6,7min c23,c25,c75,c78=min

20、2+6,2+5,3+3,3+8=min 8,7,6,11=6X=1,2,4,5,6,7, p5=6p2=2p4=1p1=0p6=3p7=3p5=635237184566134105275934682X=1,2,4,6,7min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7, p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=836237184566134105275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=1

21、0X=1,2,3,4,5,6,7,8, p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=1037237184566134105275934682X=1,2,3,4,6,7,81到8的最短路径为1，4，7，5，8，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=1038求从求从V V1 1 到到 V V8 8 的最短路线。的最短路线。 39V1V2V3V4V5V6V7V8 P=0T=+T=+T=+T=+T=+T=+T=+P=T=3T=+T=7T=+T=+T=+T=+T=6T=7P=T=5T=+T=+T=+P=T=6T=6T=8T=+T=+P=T=

22、6T=8T=9T=12P=T=8T=10T=10P=T=9T=11再无其它再无其它T 标号，所以标号，所以 T(V8)=P(V8)=10; min L()=10P=T=1040 由此看到，此方法不仅求出了从由此看到，此方法不仅求出了从V1 到到 V8 的最短路的最短路长，同时也求出了从长，同时也求出了从V1 到到 任意一点任意一点 的最短路长。将从的最短路长。将从V1 到到 任一点的最短路权标在图上，即可求出从任一点的最短路权标在图上，即可求出从V1 到到 任任一点的最短路线。本例中一点的最短路线。本例中V1 到到 V8 的最短路线是：的最短路线是： v1 v2 v5 v6 v8 416231

23、2164103623421042（二）、（二）、 逐次逼近法逐次逼近法算法的基本思路与步骤：首先设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程： 开始时，令 即用v1到vj的直接距离做初始解。从第二步起，使用递推公式：求 ，当进行到第t步，若出现则停止计算， 即为v1到各点的最短路长。43例二、例二、18v1v2v3v4v52635135211211v6v7v837求图中求图中

24、v v1 1到到各点的最短路各点的最短路4418v1v2v3v4v52635135211211v6v7v837（0，0）（ v3 ，-5）（ v1 ，-2）（ v3 ，-7）（ v2 ，-3）（ v4 ，-5）（ v3 ，-1）（ v6 ，6）45例三、求：例三、求：5 5年内，哪些年初购置新设备，使年内，哪些年初购置新设备，使5 5年内的总费用最年内的总费用最小。小。 解：（解：（1 1）分析：可行的购置方案（更新计划）是很多的，）分析：可行的购置方案（更新计划）是很多的， 如：如： 1 1） 每年购置一台新的，则对应的费用为：每年购置一台新的，则对应的费用为： 11+11+12+12+13

25、 +5+5+5+5+5 = 84 2 2 ) )第第一一年年购购置置新新的的，一一直直用用到到第第五五年年年年底底，则则总总费费用用为：为： 11+5+6+8+11+18 = 59 显然不同的方案对应不同的费用。显然不同的方案对应不同的费用。 第第i 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 1846 （2 2）方方法法：将将此此问问题题用用一一个个赋赋权权有有向向图图来来描描述述，然然后后求求这个赋权有向图的最短路。这个赋权有向图的最短路。 求解步骤：求解步骤： 1 1）画

26、赋权有向图：）画赋权有向图： 设设 V Vi i 表表示示第第i i年年初初，( (V Vi i ,V,Vj j ) )表表示示第第i i 年年初初购购买买新新设设备备用用到到第第j j年年初初（j-1j-1年年底底），而而W Wi i j j 表表示示相相应应费费用用，则则5 5年的一个更新计划相当于从年的一个更新计划相当于从V V1 1 到到V V6 6的一条路。的一条路。 2 2）求解）求解 （标号法）（标号法） 47W12 =11+5=16W13 =11+5+6=22W14 =11+5+6+8=30W15 =11+5+6+8+11=41W16 =11+5+6+8+11+18=59 W2

27、3 =11+5=16 W24 =11+5+6=22W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W45 =12+5=17 W46 =12+5+6=23W56 =13+5=18 W34 =12+5=17W35 =12+5+6=23W36 =12+5+6+8=31 48 例四、例四、 某工厂使用一种设备，这种设备在一定的年限内某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；若继续使备是否更新。若购置设备，每年需支付购置费用；若继续

28、使用旧设备，需要支付维修与运行费用，而且随着设备的老化用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。用最小。 年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 01 11 12 22 23 33 34 44 45

29、5维修费维修费5 57 712121818252549年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 01 11 12 22 23 33 34 44 45 5维修费维修费5 57 712121818252528v1v2v3v4v5v6232526293042608532446233453050四、四、 最大流问题最大流问题（一）、（一）、 基本概念基本概念1、设设一一个个赋赋权权有有向向图图D=（V, E）,在在V中中指指定定一一个个发发点点vs和和一一个个收收点点vt ,其其它它的的点点叫叫做做中中间间点点。对对于于D中中的的每每

30、一一个个弧弧（vi , vj）E ,都都有有一一个个非非负负数数cij,叫叫做做弧弧的的容容量量。我我们们把这样的图把这样的图D叫做一个容量网络，简称网络，记做叫做一个容量网络，简称网络，记做D=（V，E，C）。）。网络网络D上的流，是指定义在弧集合上的流，是指定义在弧集合E上的一个函数上的一个函数其中其中f(vi ,vj) =fij 叫做弧叫做弧(vi，vj)上的流量。上的流量。 512、称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi ,vj）E有 0 fij cij 。 （2）平衡条件：对于发点vs，有对于收点vt ，有对于中间点，有可行流中 fijcij 的弧叫做饱和弧，

31、fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧，fij0 的弧叫做零流弧。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，若 为网络中从vs到vt的一条链，给 定向为从vs到vt， 上的弧凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示。f 是一个可行流，如果满足： 则称 为从vs到vt 的关于f 的一条增广链。 推论推论 可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条

32、可增广链。 即即 中的每一条弧都是非饱和弧中的每一条弧都是非饱和弧即即 中的每一条弧都是非零流弧中的每一条弧都是非零流弧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），vs为始点，vt为终点。如果把V分成两个非空集合 使 ，则所有始点属于S，而终点属于 的弧的集合，称为由S决定的截集,记作 。截集 中所有弧的容量之和，称为这个截集的容量，记为 。 vsv1v2v4v3vt374556378S56 13 (5)

33、9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)设设 ，则截集为则截集为容量为容量为2457 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)设设 ，则截集为则截集为容量为容量为2058（二）（二） 求最大流的标号法求最大流的标号法 标号过程：1 给发点vs 标号（0，+）。2 取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理：（1）如果边 ，且 ，那么给vj 标号 ，其中：（2）如果边 ，且 ，那么给vj 标号 ，其中： 3重复步骤2，直

34、到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。59调整过程设1令 2去掉所有标号，回到第一步，对可行流重新标号。60 求下图所示网络中的最大流，弧旁数为(1 ,1)v2v1v4v3vsvt(3 , 3)(5 , 1)(1 , 1)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,1)(1 ,1)v2v1v4v3vsvt(3 , 3)(5 , 1)(1 , 1)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,1)（0，+）（-v1, 1）（+ vs , 4）（-v2 ，

35、1）（+v2，1）(+ v3 ，1)61(1 ,0)v2v1v4v3vsvt(3 , 3)(5 , 2)(1 , 0)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,2)(1 ,0)v2v1v4v3vsvt(3 , 3)(5 , 2)(1 , 0)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,2)（0，+）（+ vs , 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

36、)9 (9)10 (7)截集截集1 1截集截集2 2最小截量为：最小截量为：9+6+5=206470（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上 的 一 个 可 行 流 ， 为 一 条 从 vs到 vt的 增 广 链 ， 称为链的费用。 若 * 是从vs到vt的增广链中费用最小的增广链，则称 * 是最小费用增广链。结论：结论：如果可行流 f在流量为W

37、(f )的所有可行流中的费用最小，并且 *是关于f 的所有增广链中的费用最小的增广链，那么沿增广链 *调整可行流f，得到的新可行流f *也是流量为W(f*)的所有可行流中的最小费用流。当f * 是最大流时，就是最小费用最大流。 66寻找关于f 的最小费用增广链： 构造一个关于f 的赋权有向图L(f ) ，其顶点是原网络G的顶点，而将G中的每一条弧 ( vi, vj )变成两个相反方向的弧（vi， vj）和(vj , vi)，并且定义图中弧的权lij为：1.当 ，令 2.当（vj，vi）为原来网络G中（vi， vj）的反向弧，令 在网络G中寻找关于f 的最小费用增广链等价于在L(f )中寻求从v

38、s 到vt 的最短路。 67步骤：（1）取零流为初始可行流 ，f (0) =0。（2）一般地，如果在第k-1步得到最小费用流 f (k-1)，则构造图 L( f (k-1) )。（3）在L( f (k-1) )中，寻求从vs到vt的最短路。若不存在最短路，则f (k-1)就是最小费用最大流；否则转(4)。（4）如果存在最短路，则在可行流f (k1)的图中得到与此最短路相对应的增广链，在增广链上，对f (k1)进行调整，调整量为：68令得到新可行流f (k) 。对f (k)重复上面步骤，返回（2）。例例8.11 求网络的最小费用最大流，弧旁权是（bij , cij） (3 ,2)vsv2v1vt

39、v3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)693 vsv2v1vtv31 64 12 2 (1) L(f (0)(3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)0vsv2v1vtv3300333(2) f ( 1)1=3W(f(1)=31(3) L(f (1)2 3vsv2v1vtv31 64 12 12701vsv2v1vtv3400343 (4 ) f ( 2)2=1W(f(2)=4(3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)(5) L(f

40、(2)3 vsv2v1vtv31 4 12 2 231661vsv2v1vtv3401453 (6 ) f ( 3)3=1W(f(3)=571(7) L(f (3)vsv2v1vtv33 1 4 1-2 2 3161vsv2v1vtv3434450 (8 ) f ( 4)4=3W(f(4)=80vsv2v1vtv34455505=1W(f(5)=9(10 )f ( 5)1 -2 31vsv2v1vtv33 4 12 6(9) L( f ( 4)-4 -67231 2 14 (11) L( f ( 5)12 64vsv2v1vtv3673第六节第六节 中国邮递员问题中国邮递员问题 一、一、 欧拉

41、回路与道路欧拉回路与道路定定义义8.18 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图。定定理理8.7 一个多重连通图G是欧拉图的充分必要条件是G中无奇点。推论 一个多重连通图G有欧拉道路的充分必要条件是G有且仅有两个奇点。74ABCD75二、 奇偶点图上作业法奇偶点图上作业法（1）找出图G中的所有的奇顶点，把它们两两配成对，而每对奇点之间必有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点。（2）如果边e=（u,v）上的重复边多于一条，则可从重复

42、边中去掉偶数条，使得其重复边至多为一条，图中的顶点仍全部都是偶顶点。（3）检查图中的每一个圈，如果每一个圈的重复边的总长不大于该圈总长的一半，则已经求得最优方案。如果存在一个圈，重复边的总长大于该圈总长的一半时，则将这个圈中的重复边去掉，再将该圈中原来没有重复边的各边加上重复边，其它各圈的边不变，返回步骤（2）。76判判定定标标准准1: 在最优邮递路线上，图中的每一条边至多有一条重复边。 判判定定标标准准2 : 在最优邮递路线上，图中每一个圈的重复边总权小于或等于该圈总权的一半。例例8.12 求解下图所示网络的中国邮路问题，图中数字为该边的长。 v1v2v3v4v5v6v7v8v924344955643477v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v9243449643455l12+2 l23+2 l36+2 l89+2 l78+l69+l14+2 l47=51 v1v2v3v4v5v6v7v8v9243449556434v1v2v3v4v5v6v7v8v924344955643478v1v2v3v4v5v6v7v8v924344955643479