第5章图与网络分析.ppt

《第5章图与网络分析.ppt》由会员分享，可在线阅读，更多相关《第5章图与网络分析.ppt（162页珍藏版）》请在课桌文档上搜索。

1、第5章 图与网络分析(Graph Theory and Network Analysis),图的基本概念与模型树最短路问题网络的最大流最小费用流应用举例,近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。,第一节 图的基本概念与模型,Knigsberg桥对应的图,例1、有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况也可以用图表示出来。,一、图基本概念,例2 某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映这个情况可以用点V1,V

2、2,V8分别代表这八种药品，若药品Vi和药品Vj是不能存放在同一个库房的，则在Vi和Vj之间连一条线。,图的表示方法：,一般地，当用图论研究一个实际问题时，常以顶点（Vertex）表示要研究的对象，以它们之间的连线，表示某种关系，这种连线称为边（Edge），目的是为了解决某个极值问题。图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=v1,v1;e2=v1,v2;,运筹学中研究的图具有下列特征:,强调点与点之间的关联关系，不讲究图的比例大小与形状；每条边上赋有一个权；建立网络模型，求最大值或最小值。,下图可以提出很多极值问题,端点,关联边,相邻,若有边e可表示为e=vi,

3、vj，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。,二、关于图的另外一些名称和术语：,环,多重边,简单图,如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。,次，奇点，偶点，孤立点,与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤

4、立点。,图的次:一个图的次等于各点的次之和。,定理1 任何图中，顶点次数之和等于所有边数的2倍。,定理2 任何图中，次为奇数的顶点必为偶数个。,证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。,证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：,2m为偶数，且偶点的次之和 也为偶数，所以 必为偶数，即奇数点的个数必为偶数。,链，圈，连通图,图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用表示：,起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不

5、连通。,子图，部分图(支撑子图),图G1=V1、E1和图G2=V2，E2如果有 称G1是G2的一个子图。若有，则称G1是G2的一个部分图(支撑子图)。,(a),(b),（G图）,网络（赋权图）,赋权图）:权可以代表距离、费用、通过能力(容量)等等。无向网络:端点无序的赋权图称为.有向网络:端点有序的赋权图称为。,图的矩阵描述：邻接矩阵、关联矩阵、权矩阵等。,1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中,图的基本概念与模型,例6.2 下图所表示的图可以构造邻接矩阵A如下,对于赋权图G=(V,E),其中边 有权,构造矩阵B=(bij)nn 其中：

6、,2.权矩阵,例6.4 下图所表示的图可以构造权矩阵B如下:,G=(V,E),矩阵表示A 邻接矩阵B 关联矩阵,边e=u,v,关联边,多重边 平行边,简单图,多重图,0 1 奇数 偶数,点边关系,欧拉图与中国邮路问题,欧拉图,哥尼斯堡七桥问题,哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pregei河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？,哥尼斯堡七桥问题,定理2 连通无向图G为欧拉链的充要条件是它恰含两个奇次顶点。,定义1.在连通无向图G中,若存在经过每条边恰好一次的一

7、个圈或一条链,就称此圈或链 为欧拉圈或欧拉链。若图G含一条欧拉圈，则称为欧拉图。,定理1 连通无向图G为欧拉图的充要条件是它的全部顶点都是偶次顶点。（G中无奇次顶点）,欧拉链,欧拉图,中国邮路问题,定理3 使图G成为总权最小的欧拉图的充要条件是：（1）在有奇次顶点的图G中，通过加重复边的方法使图不再包含奇次顶点，但原图的每条边最多只能加一条重复边。（2）在图G的每个回路上，重复边之总权不超过该回路非重复边之总权。（或回路总长的一半）,例1 试为图4-13（a)构成总权最小的欧拉图。图中线旁的数字为相应边的权。,1,2,4,3,3,2,1,2,4,（a),图4-13,例2 试为图4-14（a）所

8、示的街道规划最优投递路线。解：可按以上所述步骤进行，最终结果示于图4-14（b)，总权等于52，重复边的长度等于10。,1,3,3,4,3,3,3,3,3,3,2,2,2,图4-14（a）,2,4,1,3,3,3,3,3,3,3,3,2,2,图4-14（b）,2,2,第二节 树,树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。,例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。,运动员,例6.3 某企业的组织机构图也可用树图表示。,树：无圈的连通图即为树,性质1：任何树中必存在次为1的点。性质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，

9、恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。,图的最小部分树(支撑树),如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。,G1,G2,例如，图4-18（a）是一个有四个顶点（n=4）的连通图，它共有 nn-2=42=16个生成树。,V1,V2,V3,V4,图4-18（a）,赋权图中求最小树的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v1,v2,v3,v4,

10、v5,v6,4,3,5,2,1,边数n-1=5,得到最小树：,Min C(T)=15,避圈法:去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,练习：应用破圈法求最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,树与图的最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,

11、16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3

12、,28,17,4,1,23,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,min=1+4+9+3+17+23=57,练习：应用避圈法求最小树,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7

13、,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,min=1+4+9+3+17+23=57,课堂练习：,Min C(T)=12,Min C(T)=15,答案：,3,4,1,2,2,3,2,3,2,4,2,Min C(T)=12,Min C(T)=18,某一点到另一点的最短路的Dijkstra法所有点对间的最短路 返回,第三节 最短路问题,就

14、是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,里特城（Littletown）是一个乡村的小镇。它的消防队要为包括许多农场社区在内大片的地区提供服务。在这个地区里有很多道路，从消防站到任何一个社区都有很多条路线。因为时间是一个到达火灾发生点的主要因素，所以消防队队长希望事先能够确定从消防站到每一个农场社区的最短路。,例子：里特城 的消防队问题,最短路：O A B E F T 19 英里,一、求最短路的Dijkstra算法,1、算法

15、的基本思想,2、步骤：,（1）、给vs以P标号，P（vs）=0，其余各点均给T标号，T（vi）=+。（2）、若vi点为刚得到P标号的点，考虑这样的点vj：（vi，vj）属于E，且vj为T标号。对vj的T标号进行如下的更改：T(vj)=minT(vj),P(vi)+lij(3)、比较所有具有T标号的点，把最小者改为P标号，若全部点均为P标号则停止，否则转（2）。,例、用Dijkstra算法求下图中v1v8点的最短路。,P（0，v1）,T（）,T（）,T（）,T（）,T（）,T（）,T（）,P（0，v1）,T（）,T（）,T（）,T（）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,T（

16、6）,T（）,T（）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,T（6）,T（）,T（）,T（）,T（）,T（）,P（0，v1）,P（v1,4）,T（6）,T（9）,T（8）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,T（8）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,T（8）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,P（8，v2）,T（）,T（）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,P（8，v2）,T（）,T（）,T（）,P（0

17、，v1）,P（4，v1）,P（6，v1）,T（9）,P（8，v2）,T（14）,T（13）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,T（9）,P（8，v2）,T（14）,T（13）,T（）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（14）,T（13）,T（）,P（9，v2）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（14）,T（13）,T（）,P（9，v2）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（14）,T（）,P（9，v2）,P（13，v5）,P（0，v1）,P（4，v1）,P（6，v1）,P（

18、8，v2）,T（14）,T（）,P（9，v2）,P（13，v5）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（14）,T（17）,P（9，v2）,P（13，v5）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（17）,P（9，v2）,P（13，v5）,P（14，v5）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,T（15）,P（9，v2）,P（13，v5）,P（14，v5）,P（0，v1）,P（4，v1）,P（6，v1）,P（8，v2）,P（9，v2）,P（13，v5）,P（14，v5）,P（15，v7）,P（0，v1）,P（4

19、，v1）,P（6，v1）,P（8，v2）,P（9，v2）,P（13，v5）,P（14，v5）,P（15，v7）,V3到v8的最短路：v1-v2-v5-v7-v8路长：P（v8）=15,Dijkstra最短路算法的特点和适应范围,每次迭代只有一个节点获得永久标号，若有两个或两个以上节点的临时标号同时最小，可任选一个永久标号；总是从一个新的永久标号开始新一轮的临时标号；永久标号Pj 表示 vs 到 vj 的最短路，第 k 次迭代得到的永久标号，最多有n1 次迭代；可以应用于简单有向图和混合图，在临时标号时，所谓相邻必须是箭头指向的节点；若第 n1 次迭代后仍有节点的标号为，则表明 vs 到该节点无

20、有向路径；vs 到所有点的最短路也是一棵生成树，但不是最小生成树这个算法只设用于全部权为非负情况,如果某边上权为负的,算法失效;当vi与vj两点之间至少有两条边相关联时，留下一条最短边，去掉其它关联边。,例 求下图所示网络之顶点1至6的最短路和最短路长。,P（0，v1）,P（10，v1）,P（15，v2）,P（22，v5）,P（22，v5）,P（23，v2）,1,4,2,6,5,3,8,7,6 6,3,1,6,2 7 4,3,3,7,1,6,二、所有点对间的最短路Floyd算法,1、写出图的权矩阵,步骤：,、输入权矩阵（）；、对n个顶点的图G,该方法迭代n步结束，第k次迭代的矩阵Dk的元素di

21、j(k)按下式选取 dij(k)=mindij(k-1),dik(k-1）+dkj(k-1）其中，i,j=1,2,3,n。但当i=k或j=k时，dij(k)=dij(k-1).。、（）中的元素就是到的最短路长。,例 求下图所示网络图各点对间的最短路和最短路长。,课堂练习：1.用Dijkstra算法求下图从v1到v6的最短距离及路线。,v3,v5,4,v1到v6的最短路为：,2.求从v1到v8的最短路径,v1到v8的最短路径为v1v4v7v5v8，最短距离为10,最短路问题的应用：例6.7 电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。

22、权数表示两地间公路的长度（单位：公里）。,v1（甲地）,15,17,6,2,4,4,3,10,6,5,v2,v7(乙地),v3,v4,v5,v6,解：这是一个求无向图的最短路的问题。,例6.8 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表,设备维修费如下表,解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新

23、设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。,最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和 v1v4v6,第四节 网络的最大流,如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。,实例：公司 的最大流问题,公司是欧洲一家生产豪华汽车的制造商。虽然它生产的汽车在所有发达国家的销量都不错，但是对于这家公司来说，出口到美国显得尤其重要。公司因为提供优质的服务而获得很好的 声誉，保持这个声誉一个很重要的秘

24、诀是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商和授权维修店。这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即送货。卡尔需要优先考虑的是改进这些配送中心的不足之处。,背景,该公司在美国有几个配送中心。但是，离洛杉矾中心最近的一个配送中心却坐落在离洛杉矾1000 多英里的西雅图。由于的汽车在加利福尼亚越来越受欢迎，所以保证洛杉矾中心良好的供应就显得尤为重要了。因此，现在那里的供应不断减少的现状成为了公司高层管理真正关心的问题正如现在卡尔深切领会到了一样。大部分的汽车配件以及新车是在该公司坐落于德国斯图加特的总厂和新车一起生产的。也就是这家工厂向洛杉矾中心供应汽车配件。

25、由于其中的一些配件体积很大，某些配件的需求量很多，这就使得供应的总量非常庞大每月有超过300，000立方英尺的配件需要运到。现在，下个月需要多得多的数量以补充正在减少的库存。,卡尔需要尽快做出一个方案，使得下个月从总厂运送到洛杉矾配送中心的供应件尽可能的多。他已经认识到了这是个最大流问题一个使得从总厂运送到洛杉矾配送中心的配件流最大的问题。因为总厂生产的配件量远远要大于能够运送到配送中心的量，所以，可以运送多少配件的限制条件就是该公司配送网络的容量。,问题,BMZ的网络模型，图中的数字代表该弧的容量,如图4-23 是联接某产品产地v1和销售地v6点的交通网。,一 基本概念二 求最大流的标号法,

26、返回,如图4-23 是联接某产品产地v1和销售地v6点的交通网。,一、基本概念：1.容量网络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。,s,t,4,8,4,4,1,2,2,6,7,9,2.网络的最大流是指网络中从发点到收点之间允许通过的最大流量。,3.流与可行流 流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。满足以下条件的一组流称为可行流。,容量限制条件。容量网络上所有的弧满足：0fijcij

27、 中间点平衡条件。,若以F表示网络中从st的流量，则有：,结论：任何网络上一定存在可行流。（零流即是可行流）,网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使F值达到最大。,割与割集,割是指容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用 表示。,如下图中，AA将网络上的点分割成 两个集合。并有，称弧的集合(v1,v3),(v2,v4)是一个割，且 的流量为18。,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(3),7(6),A,A,B,B,定理1 在网络中st的最大

28、流量等于它的最小割集的容量，即：v(f)=c(V,V),图5-3 最大流量网络图（网络最大流图）,(-,),(vs+,2),于是得到最小割为:,（S，）=(vs,v3),(v2,v4),(v2,v5),最小割容量是：9+6+5=20恰好等于最大流流量。,流量可增链在网络的发点和收点之间能找到一条链，在该链上所有指向为st的弧，称为前向弧，记作+,存在f0，则称这样的链为增广链。例如下图中，sv2v1v3v4t。,定理3 网络N中的流 F是最大流当且仅当N中不包含任何增广链,二、求网络最大流的标号法基本思想 由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。,

29、基本方法,找出第一个可行流，（例如所有弧的流量fij=0。）用标号的方法找一条增广链,首先给发点s标号(),标号中的数字表示允许的最大调整量。选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：,如果弧的起点为vi，并且有fij0，则vj标号(fji),(3)重复第(2)步，可能出现两种结局：,标号过程中断，t无法标号，说明网络中不存在流量可增链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V,(V,V)为网络的最小割。t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的流量可增链。继续第(4)步,(4)修改流量。设原图可行流

30、为f，令,得到网络上一个新的可行流F。,(5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何流量可增链，计算结束。,例6.10 用标号算法求下图中st的最大流量，并找出最小割。,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),网络的最大流,解：(1)先给s标号(),s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),网络的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9)

31、,5(4),7(5),(),(2)检查与s点相邻的未标号的点，因fs1cs1，故对v1标号=min,cs1-fs1=1,(1),网络的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(6),(),(1),(2)检查与v1点相邻的未标号的点，因f13c13，故对v3标号=min1,c13-f13=min1,6=1,(1),网络的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),(1),(1),(3)检查与v3点相邻的未标号的点，因f3

32、tc3t，故对vt标号=min1,c3t-f3t=min1,1=1,(1),找到一条增广链sv1v3t,网络的最大流,(4)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(3),7(5),(),(1),(1),(1),网络的最大流,(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(0),2(0),9(9),5(3),7(5),(),(1),(1),(1),网络的最大流,(5)擦除所有标号，重

33、复上述标号过程，寻找另外的增广链。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(),(2),(2)=min,2=2,(2),(1)=min2,3=2,(3)=min2,5=2,(2),(1),(4)=min2,1=1,(1),(t)=min1,2=1,网络的最大流,(6)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(),(2),(2),(2),(1),(1),网络的最大流,s

34、,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(),(2),(2),(2),(1),(1),(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。,网络的最大流,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(),(1),(1),(1),(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。,(2)=min,1=1,(1)=min1,2=1,(3)=min1,4=1,网络的最大流,例6.9 求下图st的最大流，并找出最小割,网络的最大流,

35、解:(1)在已知可行流的基础上，通过标号寻找增广链。,(),(2)=min,6=6,(6),(3)=min6,2=2,(2),(t)=min2,5=2,(2),存在增广链sv2v3 t,网络的最大流,(2)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,(),(6),(2),(2),网络的最大流,(3)擦除原标号，重新搜寻增广链。,(),(6),(2),(2),网络的最大流,(4)重新搜寻增广链。,(),(2)=min,4=4,(4),(1),(5)=min4,1=1,(3)=min1,2=1,(1),(1),(t)=min1,3=1,存在增广链：sv2v5v3 t,网络的最大流,

36、(5)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,(),(4),(1),(1),(1),网络的最大流,(6)擦除原标号,(),(4),(1),(1),(1),网络的最大流,(),(1),(1),(1),(5)=min,1=1,(5)=min1,1=1,(5)=min1,2=1,(7)重新搜寻增广链。,存在增广链：sv5v3 t,网络的最大流,(8)调整增广链上的流量，非增广链流量不变，得到新的可行流,(),(1),(1),(1),网络的最大流,(),(1),(1),(1),(9)擦除原标号,网络的最大流,(10)重新标号，搜索增广链,(),(1)=min,1=1,(1),(5)=min1,1=1,(1),(4)=min1,1=1,(1),(t)=min1,1=1,(1),存在增广链：sv1v5v4t,网络的最大流,(),(1),(1),(1),(1),(11)调整增广链上的流量，非增广链流量不变，得到新的可行流,网络的最大流,(),(1),(1),(1),(1),(11)擦除标号，在新的可行流上重新标号。,网络的最大流,(),(11)擦除标号，在新的可行流上重新标号。,(3),(1)=min,3=1,无法标号，不存在增广链，此可行流已为最大流。最大流量为14。,