图与网络分析.pptx

《图与网络分析.pptx》由会员分享，可在线阅读，更多相关《图与网络分析.pptx（160页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、例1、有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况也可以用图表示出来。V1V2V3V4V5e5e4e1e2e3e6e7一、图基本概念第1页/共160页例2 某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映这个情况可以用点V1,V2,V8分别代表这八种药品，若药品Vi和药品Vj是不能存放在同一个库房的，则在Vi和Vj之间连一条线。V1V2 V3 V4 V5 V8 V7 V6第2页/共160页图的表示方法：一般地，当用图论研究一个实际问题时，常以顶点（Vertex）表示要研究的对象，以它们之间的连线，表示某种关系，这种连线称为边（Edge），目的是为了解决某个极值问题。

2、图中的点用v表示，边用e表示。对每条边可用它所连接的点表示，记作：e1=v1,v1;e2=v1,v2;第3页/共160页运筹学中研究的图具有下列特征:强调点与点之间的关联关系，不讲究图的比例大小与形状；每条边上赋有一个权；建立网络模型，求最大值或最小值。第4页/共160页下图可以提出很多极值问题142653876 63162 7 433716第5页/共160页v3e7e4e8e5e6e1e2e3v1v2v4v5 端点,关联边,相邻若有边e可表示为e=vi,vj，称vi和vj是边e的端点，反之称边e为点vi或vj的关联边。若点vi、vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的

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

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

5、。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。第10页/共160页 子图，部分图(支撑子图)图G1=V1、E1和图G2=V2，E2如果有 称G1是G2的一个子图。若有 ，则称G1是G2的一个部分图(支撑子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）第11页/共160页 网络（赋权图）赋权图）:权可以代表距离、费用、通过能力(容量)等等。无向网络:端点无序的赋权图称为.有向网络:端点有序的赋权图称为。910201571419256第12页/共160页 图的矩阵描

6、述：邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中第13页/共160页图的基本概念与模型v5v1v2v3v4v64332256437例6.2 下图所表示的图可以构造邻接矩阵A如下第14页/共160页对于赋权图G=(V,E),其中边 有权 ,构造矩阵B=(bij)nn 其中：2.2.权矩阵权矩阵第15页/共160页v5v1v2v3v4v64332256437例6.4 下图所表示的图可以构造权矩阵B如下:第16页/共160页G=(V,E)矩阵表示矩阵表示A A 邻接矩阵B B 关联矩阵边e=u,v 关联边 端点 重重合

7、合环多重边 平行边平行边简单图不含不含多重图含含点的次点的次 0 1 奇数 偶数 子图子图生成子图孤立点悬挂点奇点偶点顶点数p边数q点边关系各种链的概念第17页/共160页欧拉图与中国邮路问题欧拉图哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，哥尼斯堡（现名加里宁格勒）是欧洲一个城市，PregeiPregei河把该城分成两河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如人们提出这样的问题：有没有办法从某处（如A A）出发，经过各桥

8、一次且仅）出发，经过各桥一次且仅一次最后回到原地呢？一次最后回到原地呢？第18页/共160页Cab图 4-10 ad哥尼斯堡七桥问题第19页/共160页acbd(b)第20页/共160页 定理2 连通无向图G为欧拉链的充要条件是它恰含两个奇次顶点。定义1.在连通无向图G中,若存在经过每条边恰好一次的一个圈或一条链,就称此圈或链 为欧拉圈或欧拉链。若图G含一条欧拉圈，则称为欧拉图。定理1 连通无向图G为欧拉图的充要条件是它的全部顶点都是偶次顶点。（G中无奇次顶点）第21页/共160页欧拉链欧拉图第22页/共160页中国邮路问题第23页/共160页定理3 使图G成为总权最小的欧拉图的充要条件是：（

9、1）在有奇次顶点的图G中，通过加重复边的方法使图不再包含奇次顶点，但原图的每条边最多只能加一条重复边。（2）在图G的每个回路上，重复边之总权不超过该回路非重复边之总权。（或回路总长的一半）第24页/共160页 例1 试为图4-13（a)构成总权最小的欧拉图。图中线旁的数字为相应边的权。124332124（a)图4-13第25页/共160页例2 试为图4-14（a）所示的街道规划最优投递路线。解：可按以上所述步骤进行，最终结果示于图4-14（b)，总权等于52，重复边的长度等于10。1334333333222图4-14（a）2第26页/共160页413 333333 322 图4-14（b）22

10、第27页/共160页第二节 树树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员第28页/共160页例6.3 某企业的组织机构图也可用树图表示。第29页/共160页 树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6第30页/共160页 图的最小部分树(支撑树)如果G

11、2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2第31页/共160页 例如，图4-18（a）是一个有四个顶点（n=4）的连通图，它共有 nn-2=42=16个生成树。V1V2V3V4图4-18（a）第32页/共160页第33页/共160页第34页/共160页a ab bc cf fe ed dh hg gb bf fe ed d第35页/共160页a ab bc cf fe ed dh hg gb bf fd dg g第

12、36页/共160页b bc ce ed da ab bc cf fe ed dh hg g第37页/共160页a ab bc ch ha ab bc cf fe ed dh hg g第38页/共160页a af fd dg ga ab bc cf fe ed dh hg g第39页/共160页 赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数n-1=5第40页/共160页v1v2v3v4v5v643521得到最小树：Min C(T)=15第4

13、1页/共160页避圈法:去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v6843752618第42页/共160页v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15第43页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636练习：练习：应用破圈法求最小树应用破圈法求最小树第44页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v

14、6v6202015159 9161625253 3282817174 41 123233636第45页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323第46页/共160页树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323第47页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323第48页/共160页v1v1v7

15、v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323第49页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323第50页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323第51页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323第52页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6

16、v69 925253 3282817174 41 12323第53页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323第54页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323第55页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=57第56页/共160页练习：练习：应用避圈法求最小树应用避圈法求最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015

17、159 9161625253 3282817174 41 123233636第57页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第58页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第59页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第60页/共160页v1v1v7

18、v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第61页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第62页/共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=57第63页/共160页课堂练习：课堂练习：3749346321

19、Min C(T)=12Min C(T)=15254173314475答案：第64页/共160页34122323242Min C(T)=12213638534567454321Min C(T)=18第65页/共160页 一某一点到另一点的最短路的Dijkstra法二所有点对间的最短路 返回第三节 最短路问题第66页/共160页就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。第67页/共160页 里特城（Littletown）是一个乡

20、村的小镇。它的消防队要为包括许多农场社区在内大片的地区提供服务。在这个地区里有很多道路，从消防站到任何一个社区都有很多条路线。因为时间是一个到达火灾发生点的主要因素，所以消防队队长希望事先能够确定从消防站到每一个农场社区的最短路。例子：里特城 的消防队问题第68页/共160页第69页/共160页最短路：O A B E F T 19 英里第70页/共160页一、求最短路的Dijkstra算法 1、算法的基本思想第71页/共160页2、步骤：（1）、给vs以P标号，P（vs）=0，其余各点均给T标号，T（vi）=+。（2）、若vi点为刚得到P标号的点，考虑这样的点vj：（vi，vj）属于E，且vj

21、为T标号。对vj的T标号进行如下的更改：T(vj)=minT(vj),P(vi)+lij(3)、比较所有具有T标号的点，把最小者改为P标号，若全部点均为P标号则停止，否则转（2）。第72页/共160页v1v8v7v6v5v4v3v24645675795414例、用Dijkstra算法求下图中v1v8点的最短路。第73页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）T（）T（）T（）T（）T（）T（）T（）第74页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）T（）T（）T（）T（）T（）T（）T（）第75页/共160页

22、v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）T（6）T（）T（）T（）T（）T（）第76页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）T（6）T（）T（）T（）T（）T（）第77页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（v1,4）T（6）T（9）T（8）T（）T（）T（）第78页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）T（8）T（）T（）T（）第79页/共160页v1v8v

23、7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）T（8）T（）T（）T（）第80页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）P（8，v2）T（）T（）T（）第81页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）P（8，v2）T（）T（）T（）第82页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）P（8，v2）T（14）T（

24、13）T（）第83页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）P（8，v2）T（14）T（13）T（）第84页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（14）T（13）T（）P（9，v2）第85页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（14）T（13）T（）P（9，v2）第86页/共160页v1v8v7v6v5v4v3v24645675795

25、414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（14）T（）P（9，v2）P（13，v5）第87页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（14）T（）P（9，v2）P（13，v5）第88页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（14）T（17）P（9，v2）P（13，v5）第89页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，

26、v2）T（17）P（9，v2）P（13，v5）P（14，v5）第90页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（15）P（9，v2）P（13，v5）P（14，v5）第91页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）P（9，v2）P（13，v5）P（14，v5）P（15，v7）第92页/共160页v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）P（9，v2）P（

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

28、最短路也是一棵生成树，但不是最小生成树这个算法只设用于全部权为非负情况,如果某边上权为负的,算法失效;当vi与vj两点之间至少有两条边相关联时，留下一条最短边，去掉其它关联边。第94页/共160页1024149135787v1v2v3v4v5v6 例 求下图所示网络之顶点1至6的最短路和最短路长。P（0，v1）P（10，v1）P（15，v2）P（22，v5）P（22，v5）P（23，v2）第95页/共160页142653876 63162 7 433716第96页/共160页二、所有点对间的最短路Floyd算法 1、写出图的权矩阵 第97页/共160页步骤：、输入权矩阵（）；、对n个顶点的图G

29、,该方法迭代n步结束，第k次迭代的矩阵Dk的元素dij(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).。、（）中的元素就是到的最短路长。第98页/共160页v1v3v4v2v5512310655228442例 求下图所示网络图各点对间的最短路和最短路长。第99页/共160页第100页/共160页第101页/共160页第102页/共160页第103页/共160页23147 4 32 910例 求下图所示网络图各点对间的最短路和最短路长。第104页/共160页课堂练习：1.

30、用Dijkstra算法求下图从v1到v6的最短距离及路线。v3v54v1v2v4v635222421v1到v6的最短路为：第105页/共160页2.求从v1到v8的最短路径237184566134105275934682第106页/共160页237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路径为v1v4v7v5v8，最短距离为10第107页/共160页最短路问题的应用：例6.7 电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位

31、：公里）。v1（甲地）1517624431065v2v7(乙地)v3v4v5v6第108页/共160页解：这是一个求无向图的最短路的问题。第109页/共160页例6.8 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表年份年份12345年初价格年初价格1111121213第110页/共160页设备维修费如下表使用年数使用年数0-

32、11-22-33-44-5每年维修费用每年维修费用5681118解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。v1v2v3v4v5v6第111页/共160页把所有弧的权数计算如下表，把权数赋到图中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723第112页/共160页 最终得到下图，可知，v1到v6的距离是53，最短路径有两条：v1v3v6和 v1v4

33、v6 V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)第113页/共160页第四节 网络的最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。第114页/共160页实例：公司 的最大流问题 公司是欧洲一家生产豪华汽车的制造商。虽然它生产的汽车在所有发达国家的销量都不错，但是对于这家公司来说，出口到美国显得尤其重要。公司因为提供优质的服务而获得很好的 声誉，保持这个声誉一个很重要的秘诀是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商和

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

35、多，这就使得供应的总量非常庞大每月有超过300，000立方英尺的配件需要运到。现在，下个月需要多得多的数量以补充正在减少的库存。第116页/共160页 卡尔需要尽快做出一个方案，使得下个月从总厂运送到洛杉矾配送中心的供应件尽可能的多。他已经认识到了这是个最大流问题一个使得从总厂运送到洛杉矾配送中心的配件流最大的问题。因为总厂生产的配件量远远要大于能够运送到配送中心的量，所以，可以运送多少配件的限制条件就是该公司配送网络的容量。问题第117页/共160页第118页/共160页LASTLIROBONONY 806070405030507040BMZ的网络模型，图中的数字代表该弧的容量第119页/共

36、160页v1V2 5,2v410,54,1 3,38,3V3 6,3 v53,25,111,617,2图4-23v6如图4-23 是联接某产品产地v1和销售地v6点的交通网。第120页/共160页 一 基本概念二 求最大流的标号法返回第121页/共160页v1V2 5,2v410,54,0 3,38,3V3 6,2 v53,35,111,617,2图4-23v6如图4-23 是联接某产品产地v1和销售地v6点的交通网。第122页/共160页一、基本概念：1.1.容量网络：容量网络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量容量，简记为cij。容量网络中通常规定一个发

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

38、第125页/共160页 割与割集割是指容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用 表示。如下图中，AA将网络上的点分割成 两个集合。并有 ，称弧的集合(v1,v3),(v2,v4)是一个割，且 的流量为18。第126页/共160页stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABB第127页/共160页 定理定理1 1 在网络中st的最大流量等于它的最小割集的容量，即：v(f)=c(V,V)第128页/共160页vsv2v3v4v5v6vt（4，0）（13，11）（5，5）（9，9）

39、（5，4）（5，5）（6，6）（5，2）（9，7）（4，4）（4，4）（10，9）图5-3 最大流量网络图（网络最大流图）(-,)(vs+,2)第129页/共160页于是得到最小割为:（S，）=(vs,v3),(v2,v4),(v2,v5)最小割容量是：9+6+5=20恰好等于最大流流量。第130页/共160页 流量可增链流量可增链在网络的发点和收点之间能找到一条链，在该链上所有指向为st的弧，称为前向弧，记作+,存在f0，则称这样的链为增广链。例如下图中，sv2v1v3v4t。定理定理3 3 网络N中的流 F是最大流当且仅当N中不包含任何增广链第131页/共160页二、求网络最大流的标号法

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

41、的最小割。t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的流量可增链。继续第(4)步第133页/共160页(4)修改流量。设原图可行流为f，令得到网络上一个新的可行流F。(5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何流量可增链，计算结束。第134页/共160页例6.10 用标号算法求下图中st的最大流量，并找出最小割。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)第135页/共160页网络的最大流解：(1)先给s标号()stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4

42、)7(5)()第136页/共160页网络的最大流stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(2)检查与s点相邻的未标号的点，因fs1cs1，故对v1标号=min,cs1-fs1=1,(1)第137页/共160页网络的最大流stv1v3v2v48(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)第138页/共160页网络的最大流stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)

43、9(9)5(4)7(5)()(1)(1)(3)检查与v3点相邻的未标号的点，因f3tc3t，故对vt标号=min1,c3t-f3t=min1,1=1(1)找到一条增广链sv1v3t第139页/共160页网络的最大流(4)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)()(1)(1)(1)第140页/共160页网络的最大流(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)()(1)(1)(1)

44、第141页/共160页网络的最大流(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(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第142页/共160页网络的最大流(6)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)(2)(1)(1)第143页/共160页网络的最大流st

45、v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(2)(2)(2)(1)(1)(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。第144页/共160页网络的最大流stv1v3v2v48(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第145页/共160页网络的最大流例6.9 求下图st的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4

46、(3)3(2)5(3)4(2)2(2)7(6)8(3)第146页/共160页网络的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)解:(1)在已知可行流的基础上，通过标号寻找增广链。()(2)=min,6=6(6)(3)=min6,2=2(2)(t)=min2,5=2(2)存在增广链存在增广链svsv2 2vv3 3 t t第147页/共160页网络的最大流(2)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2

47、)2(2)7(6)8(3)()(6)(2)(2)第148页/共160页网络的最大流(3)擦除原标号，重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(6)(2)(2)第149页/共160页网络的最大流(4)重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(2)=min,4=4(4)(1)(5)=min4,1=1(3)=min1,2=1(1)(1)(t)=min1,3=1存在增广链：存在增广链：svsv2 2v

48、v5 5vv3 3 t t第150页/共160页网络的最大流(5)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(4)(1)(1)(1)第151页/共160页网络的最大流(6)擦除原标号stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()(4)(1)(1)(1)第152页/共160页网络的最大流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4

49、(4)2(2)7(6)8(6)()(1)(1)(1)(5)=min,1=1(5)=min1,1=1(5)=min1,2=1(7)重新搜寻增广链。存在增广链：存在增广链：svsv5 5vv3 3 t t第153页/共160页网络的最大流(8)调整增广链上的流量，非增广链流量不变，得到新的可行流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()(1)(1)(1)第154页/共160页网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)()(1

50、)(1)(1)(9)擦除原标号第155页/共160页网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)(10)重新标号，搜索增广链()(1)=min,1=1(1)(5)=min1,1=1(1)(4)=min1,1=1(1)(t)=min1,1=1(1)存在增广链：存在增广链：svsv1 1vv5 5vv4 4tt第156页/共160页网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)()(1)(1)(1)(1)(11)调整增广链