运筹学(第6章图与网络分析).ppt

《运筹学(第6章图与网络分析).ppt》由会员分享，可在线阅读，更多相关《运筹学(第6章图与网络分析).ppt（137页珍藏版）》请在三一办公上搜索。

1、,运筹学基础及应用(Operations Research),主讲：杨启明,第6章 图与网络分析,近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡 7 桥”难题。Euler1736年证明了不可能存在这样的路线。,Knigsberg桥对应的图,6.1 图的基本概念与模型,岛,北区,东区,南区,图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。,例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图6-1就是一个表示这

2、种关系的图。,图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：,其中:V点集 E边集,当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵陈等七人的相互认识关系我们也可以用图6-2来表示，可见图论中的图与几何图、工程图是不一样的。,图与网络的基本概念,图与网络的基本概念,如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图6-3就是一个反

3、映这七人“认识”关系的图。相互认识用两条反向的弧表示。,图的基本概念与模型,定义:图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=v1,v1;e2=v1,v2;,端点,关联边,相邻,若有边e可表示为e=vi,vj，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。,图的基本概念与模型,环,多重边,简单图,如果边e的两个端点相重，称该边为环。如右图中边e1为环。如果两个点之间多于一条，称为多重边，如右图中的e4和e5，对无环、无多重边的图称作简单图。,图的基本概念

4、与模型,次，奇点，偶点，孤立点,与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。,图的次:一个图的次等于各点的次之和。,图的基本概念与模型,链，圈，连通图,图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用表示：,起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。,图的基本概念与模型,二部图（偶图）,图G=(V,E)的点集V可以分为两各非空子集X，

5、Y，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。,(a),(b),(c),(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。,图的基本概念与模型,子图，部分图(支撑子图),图G1=V1、E1和图G2=V2，E2如果有 称G1是G2的一个子图。,(a),(b),（G图）,若有，则称G1是G2的一个部分图(支撑子图)。,图的基本概念与模型,网络（赋权图）,设图G（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权,赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。,9,10

6、,20,15,7,14,19,25,6,端点无序的赋权图称为无向网络端点有序的赋权图称为有向网络。,图的基本概念与模型,出次与入次,有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示；以vi为终点的边数称为点vi 的入次，用表示d-(vi)；vi 点的出次和入次之和就是该点的次。,有向图中，所有顶点的入次之和等于所有顶点的出次之和。,图的基本概念与模型,图的模型应用,例6.1 有甲,乙,丙,丁,戊,己6名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打的是各运动员报告参加的比赛项目。问6个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。,图的基本概念

7、与模型,解：用图来建模。把比赛项目作为研究对象，用点表示。如果2个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。,在图中找到一个点序列，使得依次排列的两点不相邻，即能满足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A,图的基本概念与模型,一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。,思考题,图的基本概念与模型,思考题解答：以每门课程

8、为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是在图中寻找一条哈密顿道路，如CEAFDB，就是一个符合要求的考试课程表。,图的基本概念与模型,A,F,E,D,C,B,图的基本概念与模型,A,F,E,D,C,B,图的基本概念与模型,图的基本性质：,定理1 任何图中，顶点次数之和等于所有边数的2倍。,定理2 任何图中，次为奇数的顶点必为偶数个。,证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。,证明：设V1和V2分别为图G中奇点与偶点的集合。由定理

9、1可得：,2m为偶数，且偶点的次之和 也为偶数，所以 必为偶数，即奇数点的个数必为偶数。,图的基本概念与模型,图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。,1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中,例6.2 下图所表示的图可以构造邻接矩阵A如下,对于赋权图G=(V,E),其中边 有权,构造矩阵B=(bij)nn 其中：,图的基本概念与模型,2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有mn阶矩阵

10、M=(mij)mn，其中:,3.权矩阵,1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0,v1v2v3v4v5v6v7v8,e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12,例6.3 下图所表示的图可以构造邻接矩阵M如下:,M=（mij）=,例6.4

11、下图所表示的图可以构造权矩阵B如下:,无向图：由点和边构成的图，记作G=（V，E）。有向图：由点和弧构成的图，记作D=（V，A）。连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。回路：若路的第一个点和最后一个点相同，则该路为回路。赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。,图与网络的基本概念,树是图论中的重要概念，所谓树就是一个无圈的连通图。,图6-11中

12、，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。,6.2 树图和图的最小部分树,6.2 树图和图的最小部分树,树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。,例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。,运动员,树与图的最小树,例6.3 某企业的组织机构图也可用树图表示。,树与图的最小树,树：无圈的连通图即为树,性质1：任何树中必存在次为1的点。性质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间

13、加一条边，恰得到一个圈。,树与图的最小树,图的最小部分树(支撑树),如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。,G1,G2,树与图的最小树,树与图的最小树,树与图的最小树,树与图的最小树,树与图的最小树,树与图的最小树,求树的方法：破圈法和避圈法,破圈法,树与图的最小树,部分树,树与图的最小树,避圈法,树与图的最小树,赋权图中求最小树的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1

14、,边数n-1=5,树与图的最小树,得到最小树：,Min C(T)=15,避圈法（Kruskal）,思想：在图中取一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之 与已选取的边不构成圈（每一步中，如果有两条或两条以上的边都是最小权的边，则从中任选一条）。,树与图的最小树,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,

15、v6,20,15,9,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,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,树与图的最

16、小树,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,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,

17、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,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,树与图的最小树,v1,v7,v4,v3,v

18、2,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,6.3 最短路问题,如何用最短的线路将三部电话连起来？此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。,A,B,C,A,B,C,P,但若增加一个周转站（新点P）连接4点的新网络的最短路线为PAPBPC。最短

19、新路径之长N比原来只连三点的最短路径O要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。,最短路问题,问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,最短路问题,例6.4 渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问

20、题就可以用求最短路方法解决。,最短路问题,定义：1）人M（Man），狼W（Wolf），羊G（Goat），草H（Hay）2）点 vi 表示河岸的状态3）边 ek 表示由状态 vi 经一次渡河到状态 vj 4）权边 ek 上的权定为 1,我们可以得到下面的加权有向图,状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G),此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。,v1,v2,v3,v4,v5,u5,u4,u3,u2,u1,求最短路有两种算法:,狄克斯屈拉(Dijkstra)标号算法

21、 逐次逼近算法,最短路问题,狄克斯屈拉(Dijkstra)标号算法的基本思路：若序列 vs,v1.vn-1,vn 是从vs到vt间的最短路，则序列 vs,v1.vn-1 必为从vs 到vn-1的最短路。,假定v1v2 v3 v4是v1 v4的最短路，则v1 v2 v3一定是v1 v3的最短路，v2 v3 v4也一定是v2 v4的最短路。,最短路问题,求网络图的最短路，设图的起点是vs,终点是vt,以vi为起点vj为终点的弧记为(i,j)距离为dij,P标号(点标号)：b(j)起点vs到点vj的最短路长；T标号(边标号)：k(i,j)=b(i)+dij，,步骤：,1.令起点的标号；b(s)0。,

22、2.找出所有已标号vi到未标号vj的弧集合 B=(i,j)如果这样的弧不存在或vt已标号则计算结束；,3.计算集合B中弧k(i，j)=b(i)+dij的标号,4.选一个点标号 在终点vl处标号b(l),返回到第2步。,例6.5 求下图v1到v7的最短路长及最短路线,0,8,6,2,2,5,4,4,11,14,7,5,10,7,12,11,v7已标号，计算结束。从v1到v7的最短路长是 11,最短路线：v1 v4 v6 v7,已标号点,未标号点,（，），（，），（，）0+8 0+6 0+2,（，），（，），（，），（，）0+8 0+6 2+3 2+2,（，）（，）（，）（，）（，）（，）0+8

23、0+6 2+3 4+3 4+10 4+7,(,)(,)(,)（,)(,)(,)(,)(,)0+8 0+6 5+2 5+10 5+4 4+3 4+10 4+7,12,最短路问题,例 求下图中v1到v6的最短路,（0,s),解：采用Dijkstra算法，,最短路径为v1 v3 v4 v6,(3,3),(2,1),(3,1),(8,4),点v5不能标号，说明vs不可达v5,最短路问题,从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，,注：无向图最短路的求法只将上述步骤2将弧改成边即可。,因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达v

24、j。,例6.6 求下图v1到各点的最短距离及最短路线。,0,4,5,2,2,3,10,3,9,6,12,6,4,11,6,6,18,8,12,24,8,24,18,所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。,课堂练习：1.用Dijkstra算法求下图从v1到v6的最短距离及路线。,v3,v5,4,v1到v6的最短路为：,最短路问题,2.求从v1到v8的最短路径,最短路问题,v1到v8的最短路径为v1v4v7v5v8，最短距离为10,最短路问题,3.求下图中v1点到另外任意一点的最短路径,v1,v2,v3,v4,v6,v5,3,2,2,7,6,2,1,3,3,最短

25、路问题,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,最短路问题,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,最短路问题,算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。,例6.7 如右图所示中按dijkstra算法可得P(v1)=5为从vsv1的最短路长显然是错误的，从vsv2v1路长只有3。,v2,vs,v1,5,-5,8,最短路问题的应用：例6.7 电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短

26、？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。,v1（甲地）,15,17,6,2,4,4,3,10,6,5,v2,v7(乙地),v3,v4,v5,v6,解：这是一个求无向图的最短路的问题。直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。,最短路径v1 v3 v5 v6 v7,（0,s),（10,1),（13,3),（14,3),（16,5),（18,5),（22,6),最短路问题,例6.8 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如

27、果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表,最短路问题,设备维修费如下表,解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。,v1,v2,v3,v4,v5,v6,把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。,最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和 v1v4v6,

28、邮递员的工作是每天在邮局里选出邮件，然后送到他所管辖的客户中，再返回邮局。自然地，若他要完成当天的投递任务，则他必须要走过他所投递邮件的每一条街道至少一次。问怎样的走法使他的投递总行程为最短？这个问题就称为中国邮路问题。,1、提出问题,上图表示从R1-R15个街道交叉点，街道上的数字表示该街道的长度，单位为米。,6.4 中国邮路问题,首先把这个实际问题转换成一个非负赋权图G，G的顶点代表街与街之间的交叉路口和终端，两个顶点相邻当且仅当这两点所对应的路口有直通街道而中间不通过其他路口，每条边的权是这条边所对应街道的长度。G的通过每条边至少一次的闭途径称为G的环游。具有最小权的环游称为G的最优环游

29、，则中国邮路问题就是要在赋权图G中找一条最优环游。,2、分析问题,街道结构图,由上构造右图,3、解决问题,返回 结束,寻找Euler图的最优环游的基本思路：（1）用双倍边方法求 的一个Euler赋权母图，使 达到最小。（2）用Fleury算法求得 的Euler环游,就是 图 的环游；,定理（管梅谷，1960）设 是一个连通的赋权图，是 的一个Euler赋权生成母图，则当且仅当 没有重复数大于2的边。并且 的每一个长度至少是3的回路中多重边的权和不超过此回路权和的一半。,返回 结束,奇偶点图上作业法（求最优环游算法）：,(1)把 中度为奇数的顶点两两配对，记为。对每个，中取一条 路，将 上的每一

30、条边都添加一条边，从而得到 的一个赋权Euler生成母图。,(2)去掉 中关于 的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接。,(4)用Fleury算法求 的Euler环游。,(3)检查 的每一个回路，如果某个回路 上多重边 的权和超过此回路权和的一半，则将 进行调整：删除，的边重数增加 1。,解：根据上述算法(1)，把 和 配对，和 配对，取，并对 中每条边各添加一条边；又取，并对 中每条 边各添加一条边。得图(b).依次按算法，得到图(c),(d),(e),奇偶点图上作业法缺陷：奇偶点图上作业法需要检查图中的

31、每个回路。随着顶点个数和边数增加，回路个数增加。如下图一，图二。图一回路超过150个，图二回路至少有上千个。,思考：如何求恰好有两个奇点的赋权图的最优环游？,设 恰好有两个奇点 和，则可以利用2.2节求出 的一条最短 路，在 中只要把 中的每一条边中再添加一条边，加上权就可得Eluer图。可以证明 的Eluer环游就是 的最优环游。下左图的最优环游即为右图。,如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。,6.5 网络的最大流,网络的最大流,基本概念：1.容量网络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中

32、通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。,s,t,4,8,4,4,1,2,2,6,7,9,2.网络的最大流是指网络中从发点到收点之间允许通过的最大流量。,3.流与可行流 流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。满足以下条件的一组流称为可行流。,容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。,若以v(f)表示网络中从st的流量，则有：,网络的最大流,结论：任何网络上一定存在可行流。（零流即是可行流）,网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使v

33、(f)值达到最大。,割与割集,割是指容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用 表示。,左图中，AA将网络上的点分割成 两个集合。,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,现有，称弧的集合(v1,v3),(v2,v4)是一个割，且 的流量为18。,定理1 设网络N中一个从 s 到 t 的流 f 的流量为v(f)，(V,V)为任意一个割集，则 v(f)=f(V,V)f(V,V),推论1 对网络 N中任意流量v(f)和割集(V,V)，有v

34、(f)c(V,V),证明 w=f(V,V)f(V,V)f(V,V)c(V,V),推论2 最大流量v(f)不大于最小割集的容量，即：v(f)minc(V,V),定理2 在网络中st的最大流量等于它的最小割集的容量，即：v(f)=c(V,V),增广链在网络的发点和收点之间能找到一条链，在该链上所有指向为st的弧，称为前向弧，记作+,存在f0，则称这样的链为增广链。例如下图中，sv2v1v3v4t。,定理3 网络N中的流f 是最大流当且仅当N中不包含任何增广链,s,t,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(4),7(5),求网络最大流的标号算法

35、：基本思想 由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。,基本方法,找出第一个可行流，（例如所有弧的流量fij=0。）用标号的方法找一条增广链,首先给发点s标号(),标号中的数字表示允许的最大调整量。选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：,如果弧的起点为vi，并且有fij0，则vj标号(fji),(3)重复第(2)步，可能出现两种结局：,标号过程中断，t无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V,(V,V)为网络的最小割。t得到标号，反向追踪在网络中找到一

36、条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步,(4)修改流量。设原图可行流为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,v

37、4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(0，),(2)检查与s点相邻的未标号的点，因fs1cs1，故对v1标号=min,cs1-fs1=1,(s，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),(0，),(s，1),(2)检查与v1点相邻的未标号的点，因f13c13，故对v3标号=min1,c13-f13=min1,6=1,(v1，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

38、),(0，),(s，1),(v1，1),(3)检查与v3点相邻的未标号的点，因f3tc3t，故对vt标号=min1,c3t-f3t=min1,1=1,(v3，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),(0，),(s，1),(v1，1),(v3，1),(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(0),2(0),9(9),5(3

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

40、),10(8),6(1),2(0),9(9),5(3),7(5),(0，),(s，2),(v2，2),(v1，2),(v3，1),(v4，1),s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。,(0，),(s，2),(v2，2),(v1，2),(v3，1),(v4，1),s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(s，1),(v2，1),(v1，1),(7)擦除所有标号，重复上述标号

41、过程，寻找另外的增广链。,(2)=min,1=1,(1)=min1,2=1,(3)=min1,4=1,(0，),例6.9 求下图st的最大流，并找出最小割,解:(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,

42、(3)=min1,2=1,(1),(1),(t)=min1,3=1,存在增广链：sv2v5v3 t,(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。,