[数学]运筹学第7：图与网络分析课件.ppt

1、BDACABCD哥尼斯堡七桥问题哥尼斯堡七桥问题一笔画问题一笔画问题上海上海连云港连云港青岛青岛北京北京南京南京武汉武汉徐州徐州济南济南郑州郑州天津天津左图是我国北京、左图是我国北京、上海等十个城市间上海等十个城市间的铁路交通图，反的铁路交通图，反映了这十个城市间映了这十个城市间的铁路分布情况。的铁路分布情况。电话线分布图电话线分布图煤气管道图煤气管道图航空线图航空线图 已知有已知有A、B、C、D、E五个球队，五个球队，A队和其他队和其他各队都比赛过一次，各队都比赛过一次，B队和队和A、C两队比赛过，两队比赛过，C队队和和A、B、D队比赛过，队比赛过，D队和队和A、C、E队比赛过，队比赛过，E

2、队和队和A、D队比赛过。队比赛过。EADCB用图表示的比赛情况用图表示的比赛情况 A B C D EEADCB1、一个图是由一些点及点与点之间的连线（不带一个图是由一些点及点与点之间的连线（不带箭头或带箭头）组成。箭头或带箭头）组成。两点间不带箭头的连线称作两点间不带箭头的连线称作边边，带箭头的连线，带箭头的连线称作称作弧弧。一、图与网络的基本概念一、图与网络的基本概念2 2、如果一个图是由点和边所构成的，则称其为、如果一个图是由点和边所构成的，则称其为无向图无向图，记作，记作G=(=(V，E)。其中，。其中，V表示无向图表示无向图G的点集合，的点集合，E表示无向图表示无向图G的边集合的边集合

3、,连接点的边记连接点的边记作作 vi,vj，或者或者 vj,vi。3 3、如果一个图是由点和弧所构成的，那么称它为、如果一个图是由点和弧所构成的，那么称它为有有向图向图，记作，记作D=(=(V,A)，其中其中V表示有向图表示有向图D的点集合，的点集合，A表示有向图表示有向图D的弧集合。一条方向从的弧集合。一条方向从vi 指向指向vj 的弧的弧,记记作作(vi,vj)。4 4、一条边的两个端点是相同的、一条边的两个端点是相同的,那么称为这条边是那么称为这条边是环环5 5、如果两个端点之间有两条以上的边，那么称为它、如果两个端点之间有两条以上的边，那么称为它们为们为多重边多重边。6 6、一个无环、

4、无多重边的图称为、一个无环、无多重边的图称为简单图简单图；一个无环，有多重边的图称为一个无环，有多重边的图称为多重图多重图。7、每一对顶点间都有边相连的无向简单图称为、每一对顶点间都有边相连的无向简单图称为完全图完全图 任意两个顶点之间有且仅有一条有向边的简单图称任意两个顶点之间有且仅有一条有向边的简单图称为为有向完全图有向完全图。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10 654321,vvvvvvV ,10987654321eeeeeeeeeeE，,211vve ,212vve ,323vve ,434vve ,315vve ,536vve ,537vve ,658

5、vve ,669vve ,6110vve v4v6v1v2v3v5V=v1,v2,v3,v4,v5,v6，A=(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)度为零的点称为度为零的点称为弧立点弧立点，度为，度为1 1的点称为的点称为悬挂点悬挂点。悬。悬挂点的关联边称为挂点的关联边称为悬挂边悬挂边。度为奇数的点称为。度为奇数的点称为奇点奇点，度为偶数的点称为度为偶数的点称为偶点偶点。8 8、以点、以点v为端点的边的个数称为点为端点的边的个数称为点v的的度度(次次)，记作，记作d(v)。(环记两度环记两度)有向图中，以有

6、向图中，以vi 为始点的边数称为点为始点的边数称为点vi的的出次出次,用用 表示；以表示；以vi 为终点的边数称为点为终点的边数称为点vi 的的入次入次，用，用 表表示；示；vi 点的出次和入次之和就是该点的点的出次和入次之和就是该点的次次。)(ivd)(ivd 定理定理1 1 所有顶点度数之和等于所有边数的所有顶点度数之和等于所有边数的2 2倍。倍。在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。有向图中，所有顶点的入次之和等于所有顶点的出有向图中，所有顶点的入次之和等于所有顶点的出次之和。次之和。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(

7、a)e5e7v1v2v5v6v7e1e6e8(b)子图子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图支撑子图如果如果2 1,2 1 称称2是是1的的子图子图；如果；如果2=1,2 1称称2是是1的部的部 分图或分图或支撑子图支撑子图。1010、在实际应用中，给定一个图、在实际应用中，给定一个图G=(V，E)或有向图或有向图D=(V，A)，在在V中指定两个点，一个称为始点（或发中指定两个点，一个称为始点（或发点），记作点），记作v1，一个称为终点（或收点），记作一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧其余的点称为中间点。对每一条弧 ，对应，对应

8、一个数一个数 ，称为弧上的，称为弧上的“权权”。通常把这种赋权的。通常把这种赋权的图称为图称为网络网络。Avvji),(jiw1 11 1、由两两相邻的点及其相关联的边构成的点边序列、由两两相邻的点及其相关联的边构成的点边序列称为称为链链。如。如:v0,e1,v1,e2,v2 ,e3,v3,vn-1,en,vn，记作记作(v0，v1，v2，v3 ,vn-1，vn),),其链长为其链长为n ，其中其中v0，vn分别称为链的分别称为链的起点起点和和终点终点。若链中所含的。若链中所含的边均不相同，则称此链为边均不相同，则称此链为简单链简单链；所含的点均不相同；所含的点均不相同的链称为的链称为初等链初

9、等链,也称也称通路通路。e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e10 1 12 2、图中任意两点之间均至少有一条通路，则称、图中任意两点之间均至少有一条通路，则称此图为此图为连通图连通图，否则称为不连通图。，否则称为不连通图。二、图的矩阵表示二、图的矩阵表示对于网络（赋权图）对于网络（赋权图）G=(V，E)，其中边其中边有权有权 ，构造矩阵，构造矩阵 ，其中：，其中：称矩阵称矩阵A为网络为网络G的的权矩阵权矩阵。),(jivvjiw EvvEvvwajijijiji),(0),(nnjiaA )(设图设图G=(V，E)中顶点的个数为中顶点的个数为n，构造一个矩阵构造一个矩

10、阵 ，其中：，其中：称矩阵称矩阵A为网络为网络G的的邻接矩阵邻接矩阵。nnjiaA )(EvvEvvajijiji),(0),(1654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB 例例权矩阵为：权矩阵为：邻接矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437654321654321 030303302004020576305020007204346040vvvvvvvvvvvvA 已知有六个城市，它们之间要架设电话线，要求任已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的

11、总长度意两个城市均可以互相通话，并且电话线的总长度最短。最短。v1v2v3v4v5v6一、相关概念一、相关概念 树的性质：树的性质：（1 1）树必连通，但无回路（圈）。树必连通，但无回路（圈）。（2 2）n 个顶点的树必有个顶点的树必有n-1 条边条边。（3 3）树树中任意两个顶点之间，恰有且仅有一条链中任意两个顶点之间，恰有且仅有一条链(初初等链等链)。（4 4）树连通，但去掉任一条边，）树连通，但去掉任一条边，必变为不连通。必变为不连通。（5 5）树树无回路无回路(圈圈)，但不相邻，但不相邻的两个点之间加一条边，恰得到的两个点之间加一条边，恰得到一个回路（圈）。一个回路（圈）。v1v2v3

12、v4v5v6 1 1、一个连通的无圈的无向图叫做、一个连通的无圈的无向图叫做树树(不含圈的图称不含圈的图称森林森林)树中次为树中次为1 1的点称为的点称为树叶树叶，次大于，次大于1 1的点称为的点称为分支点分支点。2 2、设图、设图 是图是图G=(V,E)的一支撑子图，如的一支撑子图，如果图果图 是一个树，那么称是一个树，那么称K是是G的一个的一个生成树生成树(支撑树支撑树)，或简称为图，或简称为图G 的树。图的树。图G 中属于生成树的中属于生成树的边称为边称为树枝树枝，不在生成树中的边称为，不在生成树中的边称为弦弦。),(1EVK 一个图一个图G 有生成树的充要条件是有生成树的充要条件是G

13、是连通图。是连通图。v1v2v3v4v5v1v2v3v4v5),(1EVK 求出下图的一个生成树。求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8（一）（一）破圈法破圈法（二）（二）避圈法避圈法在图中任取一条边在图中任取一条边e1，找一条与找一条与e1不构成圈的边不构成圈的边e2，再，再找一条与找一条与e1，e2不构成圈的边不构成圈的边e3。一般设已有一般设已有e1，e2，ek，找一条与找一条与e1，e2，ek中任何一些边不中任何一些边不构成圈的边构成圈的边ek+1，重复这个过程，

14、直到不能进行为止。重复这个过程，直到不能进行为止。v1v3v1v3v2v1v3v2v5v1v2v3v4v5v6v6v1v3v2v5v4v6v1v3v2v5二、最小生成树问题二、最小生成树问题 如果图如果图 是图是图G的一个生成树，那么称的一个生成树，那么称E1上上所有边的权的和为生成树所有边的权的和为生成树T的权，记作的权，记作S(T)。如果图如果图G的生成树的生成树T*的权的权S(T*)，在在G 的所有生成树的所有生成树T 中的权中的权最小，即最小，即那么称那么称T*是是G 的的最小生成树最小生成树。)(min)(*TSTST),(1EVT 某六个城市之间的道路网如某六个城市之间的道路网如图

15、所示，要求沿着已知长度图所示，要求沿着已知长度的道路联结六个城市的电话的道路联结六个城市的电话线网，使电话线的总长度最线网，使电话线的总长度最短。短。v1v2v3v4v5v6651572344v1v2v3v4v5v6651572344v1v2v3v4v551572344v2v4v1v3v55152344v2v4v1v3v5512344v2v4v1v3v551234第第1步：任取一个圈，从圈中去掉一条权最大的边步：任取一个圈，从圈中去掉一条权最大的边(如果有如果有两条或两条以上的边都是权最大的，则任意去掉其中一两条或两条以上的边都是权最大的，则任意去掉其中一条条)第第2步：在余下的图中，重复上述

16、步骤，一直得到一个不步：在余下的图中，重复上述步骤，一直得到一个不含圈的图为止。含圈的图为止。（一）（一）破圈法破圈法（二）（二）避圈法避圈法v1v2v3v4v5v6651572344第第1步：在图中取一条权最小的边步：在图中取一条权最小的边e1第第2步：若已选好步：若已选好e1，e2，ek，则从则从Ek中选取边中选取边ek+1，使满足：使满足：(1)e1，e2，ek，ek+1所组成的图不含圈；所组成的图不含圈；(2)ek+1为为Ek中权最小的边中权最小的边第第3步：重复第步：重复第2步，直到不能进行为止。步，直到不能进行为止。v1v2v3v4v514231352一、问题的提出一、问题的提出可

17、供选择的路线有很多，如果是你会如何选择路线？可供选择的路线有很多，如果是你会如何选择路线？最短路问题最短路问题 引例引例 已知如图所示的单行线交通网，每弧旁的数字表已知如图所示的单行线交通网，每弧旁的数字表示通过这条单行线的路程。现在某人要从示通过这条单行线的路程。现在某人要从v1出发，通过出发，通过这个交通网到这个交通网到v8去，他可以如何选择路线？去，他可以如何选择路线？1v2v3v4v5v9v8v7v6v623121641036234210最短路问题的一般提法：最短路问题的一般提法：给定一个有向赋权图给定一个有向赋权图D=(=(V,A)（或无向赋权图（或无向赋权图 G=(=(V,E)，对

18、图中各弧，对图中各弧(或边）或边）(vi,vj)，有权，有权 lij，vs、vt为图中任意两点，求一条路为图中任意两点，求一条路，使它为从，使它为从vs 到到vt的所有路中总权最短的，即的所有路中总权最短的，即 最小。最小。),()(jivvijlL二、最短路问题求解方法二、最短路问题求解方法狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法 适用于适用于lij 0 (1)给始点给始点vs以以P标号标号 ，这表示从，这表示从vs到到 vs的最短距的最短距离为离为0，其余节点均给，其余节点均给T标号，标号，。(2)设节点设节点vi为刚得到为刚得到P标号的点，考虑点标号的点，考虑点vj，其中其中 ，

19、且且vj为为T标号。对标号。对vj的的T标号进行如下修改：标号进行如下修改：若不存在满足上述条件的若不存在满足上述条件的vj，则直接进行步骤（则直接进行步骤（3）。）。(3)比较所有具有比较所有具有T标号的节点，把最小者改为标号的节点，把最小者改为P标号，即：标号，即：当存在两个以上最小者时，可同时改为当存在两个以上最小者时，可同时改为P标号。若全部节点标号。若全部节点 均为均为P标号，则停止，否则用标号，则停止，否则用vk代替代替vi，返回步骤（返回步骤（2）。）。0)(svP),2,1()(sinivTiAvvji),()(,)(min)(jiijjlvPvTvT)(min)(ikvTvP

20、例例1 1 假设引例中的数字表示通过单行线所需的费用，假设引例中的数字表示通过单行线所需的费用，用用Dijkstra方法求从方法求从v1出发到出发到v8费用最少的旅游路线。费用最少的旅游路线。1v2v3v4v5v9v8v7v6v6231216410362342101v3v2v5v8v注：注：对于对于lij00的情况，的情况，Dijkstra方法失效方法失效 Dijkstra方法的基本思想是从方法的基本思想是从vs出发，逐步向外探寻出发，逐步向外探寻 最短路最短路 Dijkstra方法不仅给出了一个从方法不仅给出了一个从vs到到vt的最短路，同的最短路，同 时也求出了从时也求出了从vs到任意一个

21、点到任意一个点vj的最短路的最短路 若若P是从是从vs到到vt的最短路，的最短路，vi是是P中的一个点，那么从中的一个点，那么从 vs沿沿P到到vi的路是从的路是从vs到到vi的最短路的最短路237184566134105275934682例例2 2 求从求从1到到8的最短路径的最短路径237184566134105275934682p1=0（1 1）首先给）首先给1 1以以P P标号，给其余所有点标号，给其余所有点T T标号标号（2 2）01PiT)8,3,2(i,min12122lPTT,min14144lPTT,min16166lPTT220,min1 10,min330,min2371

22、84566134105275934682p1=0（3 3）（4 4）)8,3,2(1min4iTPi11101,min,min42422lPTT321,min,min47477lPTTp4=1237184566134105275934682p4=1p1=0（5 5）（6 6）)8,7,6,5,3,2(2min2iTPi862,min,min23233lPTT752,min,min25255lPTTp2=2（7 7）（8 8）)8,7,6,5,3(3min76iTPPi237184566134105275934682p2=2p4=1p1=0633,7min,min75755lPTT1183,mi

23、n,min78788lPTTp7=3p6=3237184566134105275934682p2=2p4=1p1=0p6=3p7=3（9 9）（1010）)8,5,3(6min5iTPi896,8min,min53533lPTT1046,11min,min58588lPTTp5=6237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6)8,3(8min3iTPi（1111）（1212）1068,10min,min38388lPTTp3=8故从故从1到到8的最短路径为的最短路径为1，4，7，5，8，长度为，长度为10。p6=3p7=32371845661

24、34105275934682p2=2p4=1p1=0p5=6p3=8（1313）1088 TPp8=10练习：练习：求从求从v1到到v8 8的最短路线。的最短路线。3 3 V V 1 1 V V 2 2 V V V V 4 4 V V 5 5 V V V V 6 6 7 7 V V 8 8 3 3 7 7 2 2 1 1 2 2 3 3 3 3 4 4 1 1 2 2 2 2 6 6 V1V2V3V4V5V6V7V8 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=6 T=8T=+T=+P=T=

25、6 T=8T=9T=12 P=T=8T=10T=10 P=T=9T=11再无其它再无其它T 标号，所以标号，所以 T(V8)=P(V8)=10;min L()=10 v1 v2 v5 v6 v8v1 v2 v5 v6 v8 P=T=10例例3 用用Dijkstra算法求下图从算法求下图从v1到到v6的最短路的最短路（无向图）（无向图）v1v2v3v4v6v5352242421 解解 （1 1）首先给首先给v v1 1以以P P标号，给其余所有点标号，给其余所有点T T标号。标号。0)(1vP)6,3,2()(ivTi（2 2）330,min)(,)(min)(12122lvPvTvT550,m

26、in)(,)(min)(13133lvPvTvT（3 3）)6,3,2(3)(2ivP（4 4）4 13,5min)(,)(min)(23233lvPvTvT523,min)(,)(min)(24244lvPvTvT523,min)(,)(min)(25255lvPvTvTv1v2v3v4v6v5352242421)6,5,4,3(4)(3ivP（5 5）（6 6）544,5min)(,)(min)(35355lvPvTvT)6,5,4(5)()(54ivPvP（7 7）945,min)(,)(min)(46466lvPvTvT（8 8）725,min)(,)(min)(56566lvPvTv

27、T（9 9）7)()(66vTvP（1010）反向追踪得反向追踪得v1到到v6的最短路为：的最短路为：6521vvvv三、最短路问题的应用三、最短路问题的应用例例4 4 某企业使用一台设备，在每年年初，企业领导部某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。若已知该种设备在各年年初则需支付一定的维修费用。若已知该种设备在各年年初的价格和使用不同时间的设备所需的维修费用如下表所的价格和使

28、用不同时间的设备所需的维修费用如下表所示，现在的问题是如何制定一个几年之内的设备更新计示，现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用为最少。划，使得总的支付费用为最少。1811865维修费用维修费用4-53-42-31-20-1使用年数使用年数1312121111购置费购置费第第5年年第第4年年第第3年年第第2年年第第1年年第第i年度年度分析：分析：可行的购置方案（更新计划）很多，如：可行的购置方案（更新计划）很多，如：1 1)每年购置一台新的，则对应的费用为：每年购置一台新的，则对应的费用为：11+11+12+12+13+5+5+5+5+5=84 2)2)第一年购置新的

29、，一直用到第五年年底，则总第一年购置新的，一直用到第五年年底，则总 费用为：费用为：11+5+6+8+11+18=59 3)第一、三、五年购置新设备，则所需总费用为：第一、三、五年购置新设备，则所需总费用为：11+12+13+5+6+5+6+5=63 显然不同的方案对应不同的费用，如何使总费用最小？显然不同的方案对应不同的费用，如何使总费用最小？第第i年度年度第第1年年第第2年年第第3年年第第4年年第第5年年购置费购置费1111121213使用年数使用年数0-11-22-33-44-5维修费用维修费用5681118 方法：方法：将此问题用一个赋权有向图来描述，转化为求这个将此问题用一个赋权有向

30、图来描述，转化为求这个赋权有向图的最短路问题赋权有向图的最短路问题。求解步骤：求解步骤：1）画赋权有向图：画赋权有向图：设设vi表示第表示第i年初购进一台新设备，年初购进一台新设备，(vi,vj)表示第表示第i 年初购买的新设备用到第年初购买的新设备用到第j年初（年初（j-1-1年底），而年底），而lij表表示相应费用，则示相应费用，则5 5年的一个更新计划相当于从年的一个更新计划相当于从v1到到v6的一条路。的一条路。（考虑如何赋权（考虑如何赋权lij）2）Dijkstra法求解最短路问题法求解最短路问题 练习：练习：某工厂使用一种设备，这种设备在一定的年限某工厂使用一种设备，这种设备在一定

31、的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购置设备，每年需支付购置费用；决定设备是否更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用，而且随若继续使用旧设备，需要支付维修与运行费用，而且随着设备的老化会逐年增加。计划期（五年）内中每年的着设备的老化会逐年增加。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费

32、在内的总费用最小。维修费与运行费在内的总费用最小。年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 01 11 12 22 23 33 34 44 45 5维修费维修费5 57 7121218182525年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 01 11 12 22 23 33 34 44 45 5维修费维修费5 57 712121818252528v1v2v3v4v5v623252629304260853244623345301、设一个赋权有向图、设一个赋权有向图

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

34、、称满足下列条件的流为可行流可行流：（1）容量条件：对于每一个弧（）容量条件：对于每一个弧（vi,vj）E，有有 0 fij cij（2）平衡条件：平衡条件：对于发点对于发点vs，有有 对于收点对于收点vt，有有 对于中间点，有对于中间点，有EvvEvvsjjsjssjWff),(),(EvvEvvt jjtjttjWff),(),(EvvEvvi jjijiijff),(),(03、可行流中、可行流中 fijcij 的弧叫做的弧叫做饱和弧饱和弧；fijcij的的弧叫做弧叫做非饱和弧非饱和弧。fij0 的弧为的弧为非零流弧非零流弧；fij0 的弧叫做的弧叫做零零流弧流弧。容量网络容量网络G，若

35、若 为网络中从为网络中从vs到到vt的一条链，的一条链，给定方向为从给定方向为从vs到到vt，上的弧凡与上的弧凡与 方向相同的称为方向相同的称为前向弧前向弧，凡与，凡与 方向相反的称为方向相反的称为后向弧后向弧，其集合分，其集合分别用别用 和和 表示。表示。f 是一个可行流，如果满足：是一个可行流，如果满足：则称则称 为从为从vs到到vt 的关于的关于f 的一条的一条增广链增广链。),(0),(0jijijijijijivvcfvvcf 即即 中的每一条弧都是非饱和弧中的每一条弧都是非饱和弧 即即 中的每一条弧都是非零流弧中的每一条弧都是非零流弧 2v1v3v4v5v6v7v 13(5)9(3

36、)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)推论推论 可行流可行流f 是最大流的充分必要条件是是最大流的充分必要条件是不存在从不存在从vs到到vt 的关于的关于f 的一条可增广链的一条可增广链。4、容量网络、容量网络G=（V，E，C），），vs为始点，为始点，vt为为终点。如果把终点。如果把V分成两个非空集合分成两个非空集合 ，使，使 则所有始点属于则所有始点属于S，而终点属于而终点属于 的弧的集合，称为的弧的集合，称为由由S决定的决定的截集截集，记作，记作 。截集。截集 中所有弧的中所有弧的容量之和，称为这个截集的容量（容量之和，称为这个截集的容量（截

37、量截量），记），记为为 。SS,SvSvts,S),(SS),(SS),(SSCvsv1v2v4v3vt374556378S),(2vvSs),(431tvvvvS ),(,),(,),(),(32421vvvvvvSSs 18567),(23241 lllSSCs2v1v3v4v5v6v7v 13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1),(),(),(),(75423121vvvvvvVV 设设 5211,vvvV 则截集为则截集为 76432,vvvvV 不不是是该该集集中中的的弧弧和和而而),(),(5423vvvv2v1v3v4v

38、5v6v7v 13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设设 ，211,vvV 则截集为则截集为 765432,vvvvvV ),(),(),(),(52423121vvvvvvVV 标号过程：标号过程：1给发点给发点vs 标号（标号（0，+）2取一个已标号的点取一个已标号的点vi，对于对于vi一切未标号的邻接一切未标号的邻接点点vj 按下列规则处理：按下列规则处理：（1）如果边）如果边 ，且，且 ，那么给，那么给vj 标标号号 ，其中：，其中：（2）如果边）如果边 ，且且 ，那么给，那么给vj 标标号号 ，其中：，其中：Evvij),

39、(0i jf),(jiv),min(ii jjfEvvji),(ijijcf),(jiv),min(ijijijfc二、寻求最大流的标号法二、寻求最大流的标号法3重复步骤重复步骤2，直到，直到vt 被标号或标号过程无法进被标号或标号过程无法进行下去，则标号结束。若行下去，则标号结束。若vt被标号，则存在一条增被标号，则存在一条增广链，转调整过程；若广链，转调整过程；若vt未被标号，而标号过程无未被标号，而标号过程无法进行下去，这时的可行流就是最大流。法进行下去，这时的可行流就是最大流。调整过程：调整过程：1设设令令2去掉所有标号，回到第一步，对可行流重新标号去掉所有标号，回到第一步，对可行流重

40、新标号),(min1jijijivvfc),(min2jijivvf),min(21),(),(),(jijijijijijijivvfvvfvvff 求下图所示网络中的最大流，弧旁数为求下图所示网络中的最大流，弧旁数为),(jijifc(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，1）（+v2，1）(+v3，1)(1,0)v2v1v4v3vsvt(3,3)(5,2)

41、(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）),(,),(4321tsvvvvvv最小截集最小截集2v1v3v4v5v6v7v 13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)2v1v3v4v5v6v7v 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 1截集截集2 2最小截量为：最小截量为：9+6+5=201sv2v2sv1

42、v1tv2tv3v70（70）70（50）130（100）150（130）150（150）50（20）50（50）120（30）100（100）svtv（120）（230）（150）（200）已知网络已知网络G=（V，E，C，d），），f是是G上的一个可行上的一个可行流，流，为一条从为一条从vs到到vt的增广链，的增广链，称称为链的费用。为链的费用。jijiddfd)(若若 *是从是从vs到到vt的增广链中费用最小的增广链，则称的增广链中费用最小的增广链，则称 *是最小费用增广链。是最小费用增广链。结论：结论：如果可行流如果可行流 f在流量为在流量为W(f)的所有可行流中的的所有可行流中的费用

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

44、反方向的弧（vi，vj）和和(vj,vi)，并且定义图中弧的并且定义图中弧的权权lij为：为：1.当当 ，令，令 2.当（当（vj，vi）为原来网络为原来网络G中中(vi，vj)的反向弧，令的反向弧，令 在网络在网络G中寻找关于中寻找关于f 的最小费用增广链等价于在的最小费用增广链等价于在L(f)中寻求从中寻求从vs 到到vt 的最短路。的最短路。jijijijijijicfcfdl当当00jijijii jffdl当当Evvji),(步骤：步骤：（1）取零流为初始可行流）取零流为初始可行流，f(0)=0（2）一般地，如果在第一般地，如果在第k-1步得到最小费用流步得到最小费用流 f(k-1)

45、，则构造图，则构造图 L(f(k-1)（3）在在L(f(k-1)中，寻求从中，寻求从vs到到vt的最短路。若不存的最短路。若不存在最短路，则在最短路，则f(k-1)就是最小费用最大流；否则转就是最小费用最大流；否则转(4)（4）如果存在最短路，则在可行流）如果存在最短路，则在可行流f(k1)的图中得的图中得到与此最短路相对应的增广链，在增广链上，对到与此最短路相对应的增广链，在增广链上，对f(k1)进行调整，调整量为进行调整，调整量为：)(min,)(minmin)1()1(kjikjijiffc),(),(),()1()1()1()(jikjijikjijikjikjivvfvvfvvff令

46、令得到新可行流得到新可行流f(k)。对。对f(k)重复上面步骤，返回（重复上面步骤，返回（2）例例 求网络的最小费用最大流，弧旁权是（求网络的最小费用最大流，弧旁权是（bij,cij）(3,2)vsv2v1vtv3(1,4)(6,7)(4,8)(1,6)(2,5)(2,3)3 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 3 vsv2v1vtv31 64 12 121vsv2v1vtv3400343(4

47、)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(2)3 vsv2v1vtv31 4 12 2 231661vsv2v1vtv3401453(6)f(3)3=1W(f(3)=5(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-631 2 14(11)L(f(5)12 64vsv2v

48、1vtv36第六节第六节 中国邮递员问题中国邮递员问题 一、一、欧拉回路与道路欧拉回路与道路定义定义8.18 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图。定理定理8.7 一个多重连通图G是欧拉图的充分必要条件是G中无奇点。推论 一个多重连通图G有欧拉道路的充分必要条件是G有且仅有两个奇点。ABCD二、奇偶点图上作业法奇偶点图上作业法（1）找出图G中的所有的奇顶点，把它们两两配成对，而每对奇点之间必有一条通路，把这条通路上的所有边作为重复边追加到图中去，这样得到的新连通图必无奇点

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