第七章图与网络理论ppt课件

1、第七章图与网络理论第七章图与网络理论例例1 哥尼斯堡七桥问题哥尼斯堡七桥问题ABCDABCD 哥尼斯堡七桥问题哥尼斯堡城中有一条哥尼斯堡七桥问题哥尼斯堡城中有一条河，河上有七座连结着两岸和河中的两个小岛，河，河上有七座连结着两岸和河中的两个小岛，如图如图7.1所示。问题是一个人能否从一点出发，所示。问题是一个人能否从一点出发，经过每座桥一次且仅一次，回到原出发点。经过每座桥一次且仅一次，回到原出发点。 图图7.1第一节图的基本概念第一节图的基本概念 所谓图，就是顶点和边的集合，点的集合记为所谓图，就是顶点和边的集合，点的集合记为V=v1, v2, vn ，边的集合记为，边的集合记为E =e1,

2、 e2, em ， vi称为图的顶点，称为图的顶点， ej称为图的边，若边称为图的边，若边ej联联结结vs和和vt ，则记为，则记为(vs,vt )，即，即ej= (vs,vt ) 。 则图可则图可以表示为：以表示为：G=(V,E)， 点代表被研究的事物，边代表事物之间的联系，点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个因此，边不能离开点而独立存在，每条边都有两个端点。端点。 在画图时，顶点的位置、边和长短形状都是无在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，关紧要的，只要两个图的顶点及边是对应相同的，则两个图相

3、同。则两个图相同。123451234567115215312422524645734,( ,),( ,),( ,),(,),(,),(,),( ,)Vv v v v vEe e e e e e eev vev vev vev vev vev vev v有些图的边带有方向，这样的图称为有向图。有些图的边带有方向，这样的图称为有向图。而边不带方向的图称为无向图。而边不带方向的图称为无向图。图图7.7是一个无向图。是一个无向图。图图7.8是一个有向图。是一个有向图。v1v5v2v3v4e1e2e3e4e6e5e7图图7.7图图7.8 在一个图中，若在一个图中，若e=(u,v) ，则称，则称u,v是边

4、是边e的端点并的端点并u,v称相邻称称相邻称e是点是点uv及点及点的关联边。若边的关联边。若边ei,ej有一个公共的端点有一个公共的端点u，称边称边ei,ej相邻。若边相邻。若边e的两个端点是同一顶点，的两个端点是同一顶点，则称此边为环。若两顶点之间有多于一条的则称此边为环。若两顶点之间有多于一条的边，则这些边称为多重边。如图边，则这些边称为多重边。如图7.7中，中，e7是是环，环， e1, e2是多重边。是多重边。 一个不含环和多重边的图称为简单图。一个不含环和多重边的图称为简单图。含有多重边的图称为多重图。我们这里所说含有多重边的图称为多重图。我们这里所说的图，如不特别指明，都是简单图。的

5、图，如不特别指明，都是简单图。 以点以点v为端点的边的条数称为点为端点的边的条数称为点v的度，记作的度，记作d(v),如图如图7.7中中d(v1)=3, d(v3)=1。 度为零的点称为弧立点，度为度为零的点称为弧立点，度为1的点称为悬挂的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。奇点，度为偶数的点称为偶点。 不难证明：在一个图中，顶点度数的总和等不难证明：在一个图中，顶点度数的总和等于边数的倍，奇顶点的个数必为偶数。于边数的倍，奇顶点的个数必为偶数。 链：链： 由两两相邻的点及其相关联的边构成的点边序由两两相邻的

6、点及其相关联的边构成的点边序列列;如如: v0 ,e1 ,v1 ,e2 ,v2 ,e3 ,v3 ,vn-1, en , vn ; v0 ,vn分别为链的起点和终点；分别为链的起点和终点； 简单链：链中所含的边均不相同；简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同；初等链：链中所含的点均不相同；圈：在链中，假设圈：在链中，假设 v0 = vn 则称该链为圈；则称该链为圈；连通图：图中任意两点之间均至少有一连通图：图中任意两点之间均至少有一 条链相连条链相连 ，第二节树第二节树 树是一类结构简单而又十分有用的图。树是一类结构简单而又十分有用的图。一个不含圈的连通图称为树。一个不含圈

7、的连通图称为树。 设图设图T=(V,E)，含有，含有n个顶点，则下列命个顶点，则下列命题是等价的。题是等价的。（1T是树。是树。（2T的任意两顶点之间，有唯一的链相连。的任意两顶点之间，有唯一的链相连。（3T连通且有连通且有n1条边。条边。（4T无圈且有无圈且有n1条边。条边。（5T无圈但添加一条边得唯一一圈。无圈但添加一条边得唯一一圈。（6T连通但去掉一条边则不连通。连通但去掉一条边则不连通。 给定图给定图G=( V, E) ，若，若V V , E E，并且并且E中的边的端点都属于中的边的端点都属于V ，则称，则称G=( V , E)是是G的一个子图。特别地，若的一个子图。特别地，若V =

8、V ，则称，则称G为为G的支撑子图。的支撑子图。 设设T是图是图G的一个支撑子图，若的一个支撑子图，若T是一树，是一树，则称则称T是是G的一个支撑树。的一个支撑树。 给定图给定图G=( V, E),对于对于G的每一条边，可的每一条边，可赋以一个实数赋以一个实数w(e)，称为边，称为边e的权，图的权，图G连同连同它边上的权称为赋权图。赋权图在图论的应它边上的权称为赋权图。赋权图在图论的应用中经常出现。根据实际问题的需要，权可用中经常出现。根据实际问题的需要，权可以有不同的实际含义，它可以表示距离、流以有不同的实际含义，它可以表示距离、流量、时间、费用等。量、时间、费用等。 给定图给定图G=( V

9、, E), 设设T =( V, E)是是G的一的一个支撑树，定义树个支撑树，定义树T的权为的权为即支撑树即支撑树T上所有边的权的总和。图上所有边的权的总和。图G的的最小支撑树就是图最小支撑树就是图G中权最小的支撑树。中权最小的支撑树。 求图求图G的最小支撑树的方法是建立在求的最小支撑树的方法是建立在求图图G的支撑树基础上，只需在求图的支撑树基础上，只需在求图G的支的支撑树的算法再加适当限制。因此，求最小撑树的算法再加适当限制。因此，求最小支撑树方法也有相应的破圈法；避圈法。支撑树方法也有相应的破圈法；避圈法。 E)()(eewTw例例2分别用破圈法，避圈法求图分别用破圈法，避圈法求图7.17的

10、最小支撑树。的最小支撑树。 图图7.17v1v5v2v3v42v6v7v83434623664585v1v5v2v3v42v6v7v83434623664585解破圈法解破圈法v1v5v2v3v42v6v7v83434623664585避圈法：避圈法： 第三节最短路问题第三节最短路问题 最短路问题，一般来说就是从给定的赋权最短路问题，一般来说就是从给定的赋权图中，寻找两点之间权最小的链链的权即链中图中，寻找两点之间权最小的链链的权即链中所有边的权之和）。许多优化问题都需要求图的所有边的权之和）。许多优化问题都需要求图的最短路，如选址、管道铺设、设备更新、整数规最短路，如选址、管道铺设、设备更新

11、、整数规划等问题。由于所求问题不同，需要使用不同的划等问题。由于所求问题不同，需要使用不同的方法。下面我们介绍常用的算法。方法。下面我们介绍常用的算法。一、一、Dijkstra算法算法 Dijkstra算法是求赋权有向图中，某两点算法是求赋权有向图中，某两点之间最短路的算法。实际上，它可以求某一点到之间最短路的算法。实际上，它可以求某一点到其它各点的最短路。它是其它各点的最短路。它是Dijkstra于于1959年提出。年提出。目前被认为是求非负权最短路的最好的算法。目前被认为是求非负权最短路的最好的算法。 Dijkstra算法的基本思想是基于以下原理：算法的基本思想是基于以下原理：若若vs,v

12、l,vj是是vs到到vj的最短路，的最短路， vi是此路中某是此路中某一点，则一点，则vs,vl,vi必是从必是从vs到到vi的最短路。此的最短路。此算法的基本步骤是采用标号法，给图算法的基本步骤是采用标号法，给图G每一个每一个顶点一个标号。标号分两种：一种是顶点一个标号。标号分两种：一种是T标号，标号，一种是一种是P标号。标号。T标号也称临时标号，它表示从标号也称临时标号，它表示从vs到这一点的最短路长度的一个上界，到这一点的最短路长度的一个上界，P标号标号也称固定标号，它表示从也称固定标号，它表示从vs到这一点的最短路到这一点的最短路的长度这里最短路长度是指这条路上个边权的长度这里最短路长

13、度是指这条路上个边权的和）。算法每一步都把某点的的和）。算法每一步都把某点的T标号改变为标号改变为P标号。当终点得到标号。当终点得到P标号，算法结束。若要求标号，算法结束。若要求某点到其它各点的最短路，则最多经过某点到其它各点的最短路，则最多经过n-1步算步算法结束。法结束。 设设lij表示边表示边(vi,vj)的权，则的权，则Dijkstra算法步骤如算法步骤如下：下： （1给始点以给始点以P标号标号P0,0），给其它各点），给其它各点vj以以T标号标号T(dj, v1)，其中，其中，dj =l1j，（若，（若vj与与v1不不相邻，则令相邻，则令l1j =+）。）。（2在所有在所有T标号点中

14、，若标号点中，若vk的的T标号最小，标号最小，则把则把vk的的T标号改为标号改为P标号。若最小的标号。若最小的T标号不止标号不止一个，则可任取一个改为一个，则可任取一个改为P标号。标号。（3修改所有修改所有T标号标号T(dj, vt)；dj =min dj, dk+lk j ,若若dk+lk jdj vt= vk否则不变。否则不变。（4当终点或全部顶点都得到当终点或全部顶点都得到P标号，标号，算法结束，否则返回算法结束，否则返回2）。）。例例3求图求图7.20中，中，v1到到v8的最短路。的最短路。 图图 7.20v4v2v1v3v6v5v7v89838342567671094图图 7.20v

15、4v2v1v3v6v5v7v89838342567671094解解 P(0,0)T(9, v1)T(3, v1)T(8, v1)图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)T(9, v1)T(7, v3)T(3, v1)T(8, v1)P(3, v1)图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)T(9, v1)T(7, v3)T(8, v1)P(3, v1)P(7, v3)T(14, v6)T(16, v6)图图 7.20v4v2v1v3v6v5v7v89838342567671094解解

16、P(0,0)T(9, v1)T(8, v1)P(3, v1)P(7, v3)T(14, v6)P(9, v1)P(8, v1)T(17, v2)T(16, v6)图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)P(3, v1)P(17, v2)P(7, v3)T(14, v6)P(9, v1)P(8, v1)T(17, v2)T(16, v6)P(14, v6)P(16, v6)图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)P(3, v1)P(17, v2)P(7, v3)P(9, v1)P(8,

17、 v1)P(14, v6)P(16, v6)例例4 求图求图7.22中，中，v1到其它各点的最短路。到其它各点的最短路。图图 7.22v4v2v1v3v6v5v7v8354263441517498Dijkstra算法同样可用于求无向图的最短路。算法同样可用于求无向图的最短路。图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)T(3, v1)T(4, v1)T(2, v1)图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)T(3, v1)T(4, v1)T(2, v1)P(2, v1)T(7, v4)T(3,

18、 v4)P(3, v1)T(8, v2)T(9, v2)图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)P(2, v1)T(7, v4)T(3, v4)P(3, v1)T(8, v2)T(9, v2)P(3, v4)T(6, v3)图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)P(2, v1)T(7, v4)P(3, v1)T(8, v2)P(3, v4)T(6, v3)P(6, v3)T(7, v6)T(15, v6)图图 7.22v4v2v1v3v6v5v7v8354263441517498解解

19、P(0,0)P(2, v1)T(7, v4)P(3, v1)P(3, v4)P(6, v3)T(7, v6)P(7, v6)T(15, v6)T(11, v5)P(7, v4)图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)P(2, v1)P(3, v1)P(3, v4)P(6, v3)P(7, v6)T(11, v5)P(7, v4)P(11, v5)图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)P(2, v1)P(3, v1)P(3, v4)P(6, v3)P(7, v6)P(7, v4)P(11

20、, v5)二、逐次逼近法二、逐次逼近法 前面介绍的前面介绍的Dijkstra 算法，只适用于权算法，只适用于权为非负的赋权图中求最短路问题。逐次逼近为非负的赋权图中求最短路问题。逐次逼近法可用于存在负权，但无负有向回路的赋权法可用于存在负权，但无负有向回路的赋权图的最短路问题。图的最短路问题。 由于，如果由于，如果dj是从是从v1到到vj的最短路的长的最短路的长度，而这从条最短路的最后一条边为度，而这从条最短路的最后一条边为(vk, vj)，则从则从v1到到vj的最短路中，从的最短路中，从v1到到vk这一段，这一段，必然也是从必然也是从v1到到vk的最短路。若其长度记为的最短路。若其长度记为d

21、k，lk j表示边表示边(vk, vj)的权，那么的权，那么dj，dk和和lk j应满足下列方程：应满足下列方程： )(minkjkkjldd 逐次逼近法就是用迭代方法解这个逐次逼近法就是用迭代方法解这个方程。第一次逼近是找点方程。第一次逼近是找点v1到点到点vj由一由一条边所组成的最短路，其长记为条边所组成的最短路，其长记为dj(1)；第二次逼近是求从第二次逼近是求从v1到点到点vj不多于两条不多于两条边组成的最短路，其长记为边组成的最短路，其长记为dj(2)；以此；以此类推，第类推，第m次逼近是求从次逼近是求从v1到到vj不多于不多于m条边组成的最短路，其长记为条边组成的最短路，其长记为d

22、j(m)。因。因为图中，不含负有向回路，所以从为图中，不含负有向回路，所以从v1到到vj的最短路上最多有的最短路上最多有n-1条边。从而可知，条边。从而可知，最多做最多做n-1次逼近就可求出从次逼近就可求出从v1到到vj的最的最短路。短路。()(1)(2)min()(1,2, )mmjkkjkddljn逐次逼近法步骤如下：逐次逼近法步骤如下： (1) 首先令首先令dj(1)= l1j (j =1,2,n)，若，若v1 与与vj之间无边时，之间无边时，lij =+，而，而ljj =0；(3) 若对所有的若对所有的j，有，有dj(m)= dj(m-1)，则计算结束，则计算结束，dj(m) (j =

23、1,2,n)即为即为v1到到其它各点的最短路的长度，否则返回其它各点的最短路的长度，否则返回2）。）。例例4求下图中，求下图中，v1到其它各点的最短路。到其它各点的最短路。min)()1(ijkikjldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L1jjld)1(min)()1(ijkikjldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026min1)1()2(1iildd v1 1 3 9 5 3 83 6

24、 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjlddmin2)1()2(2iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2min3)1 ()2(3iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkik

25、jldd2 25min4)1()2(4iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510min5)1 ()2(5iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 25109min6)1()2(6iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v20131

26、03930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 25109)3(jdmin)2()3(ijijldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510902510810)3(jdmin)3()4(ijijldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min

27、)()1(ijkikjldd2 2510902510810)4(jd0251089)3(jdmin)4()5(ijijldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510902510810)4(jd0251089)5(jd0251089例例5求图求图7.24中，中，v1到其它各点的最短路。到其它各点的最短路。图图7.24v1v2v3v4v5v6v7v834-14-22545-3-2-4354jilijdj(1)dj(2)dj(3)dj(4

28、)dj(5)dj(6)v1v2v3v4v5v6v7v8v1034000000v20-1-24 4333333v305422222v4204511111v50-2375555v60 045333v7-3-40597777v8010877第四节最大流问题第四节最大流问题 给定一个有向图给定一个有向图G = (V,E)G = (V,E)，每条，每条边边(vi,vj)(vi,vj)给定一个非负数给定一个非负数cijcij称为边称为边(vi,vj)(vi,vj)容量。假设容量。假设G G中只有一个入度为零中只有一个入度为零的点的点vsvs称为发点，只有一个出度为零的点称为发点，只有一个出度为零的点vtv

29、t称为收点，其余点称为中间点，这样的称为收点，其余点称为中间点，这样的有向图称为容量网络，记为有向图称为容量网络，记为G = (V,E,C)G = (V,E,C)。 例如图例如图7.25就是一个容量网络。如果就是一个容量网络。如果vs表示表示油田，油田，vt表示炼油厂，图表示炼油厂，图7.25表示从油田到炼油表示从油田到炼油厂的输油管道网。边上的数字表示该管道的最大厂的输油管道网。边上的数字表示该管道的最大输油能力，中间点表示输油泵站。现在要问如何输油能力，中间点表示输油泵站。现在要问如何安排各管道输油量，才能使从安排各管道输油量，才能使从vs到到vt输油量最大？输油量最大？这就是本节所要介绍

30、的最大流问题。这就是本节所要介绍的最大流问题。 图图 7.25v1v2v3v4vsvt541425378一、基本概念一、基本概念 给定一个容量网络给定一个容量网络G = (V,E,C)，所谓网络，所谓网络G上的流，是指每条边上的流，是指每条边(vi,vj)上确定的一个数上确定的一个数f(vi,vj)，简记为简记为fij，称集合，称集合f=fij为网络为网络G上的一个流。上的一个流。 如果网络如果网络G表示一个输油管道网，则表示一个输油管道网，则cij表示表示管道输油能力，而管道输油能力，而fij表示管道当前的实际流量，表示管道当前的实际流量，因此应有因此应有0fijcij，即管道中的流量不能超

31、过该，即管道中的流量不能超过该管道的最大通过能力即管道的容量）。对网络管道的最大通过能力即管道的容量）。对网络G上的中间点表示一个转送泵站，因此对中间点上的中间点表示一个转送泵站，因此对中间点运出的总量与运进的总量应当相等。而对于发点运出的总量与运进的总量应当相等。而对于发点的净流出量和收点的净流入量必相等，并且就是的净流出量和收点的净流入量必相等，并且就是该运输方案的总输送量。该运输方案的总输送量。0kkijijffikktsiWff容量网络容量网络G = (V,E,C)中的一个流中的一个流f=fij满足下列满足下列条件，称条件，称f为可行流。为可行流。（1容量限制条件：对容量限制条件：对G

32、中每条边中每条边(vi,vj)， 有有 0fijcij。（2平衡条件：对于中间点平衡条件：对于中间点vi，有，有（即流出量流入量）。（即流出量流入量）。对于收点对于收点vt与发点与发点vs，有，有（即从（即从vs的净输出量与的净输出量与vt的净输入量相等）。的净输入量相等）。W称为可行流称为可行流f的流量。的流量。 可行流总是存在的，当所有边的流量可行流总是存在的，当所有边的流量fij =0时，时，就得到一个可行流，它的流量就得到一个可行流，它的流量W = 0。最大流问题。最大流问题就是在容量网络中，寻找流量最大的可行流。就是在容量网络中，寻找流量最大的可行流。 对于容量网络对于容量网络G给定

33、一个可行流给定一个可行流f=fij，当，当fij = cij时，称边时，称边(vi,vj)为饱和边，当为饱和边，当fij 0时，称边时，称边(vi,vj)为非零流边。为非零流边。 设设是网络是网络G中一条联结发点中一条联结发点vs和收点和收点vt的链。我们规定的链。我们规定的正方向从的正方向从vs到到vt，则链，则链上的边被分为两类：一类是边的方向与链上的边被分为两类：一类是边的方向与链的正方向一致，称它们为前向边，的正方向一致，称它们为前向边，上上前上上前向边的全体记为向边的全体记为+。另一类边与链的正方。另一类边与链的正方向相反，称它们为后向边，向相反，称它们为后向边，上后向边的全上后向边

34、的全体记为体记为-。v1v2v3v4v5vsvt(13,7) (5,5) (9,9) (4,4) (6,6) (5,2) (5,0) (4,0) (5,5) (4,4) (9,7) (10,5) 图图 7.26例如，在图例如，在图7.26中，其边上的两个数字分别表示中，其边上的两个数字分别表示边的容量和流量，即边的容量和流量，即(cij , fij)。(v2,v5)为饱和边，为饱和边，(vs,v1)为非饱和边，并且为非饱和边，并且(v2,v5)，(vs,v1)均为非均为非零流边，零流边，(v3,v5)是零流边。是零流边。例如图例如图7.26中，在联结中，在联结vs和和vt的链的链=vs, v1

35、, v2 ,v5, vt中，中，(vs,v1)，(v2,v5)，(v5, vt)为前向边，为前向边，(v1,v2)为后向边。即为后向边。即+=(vs,v1)，(v2,v5)，(v5, vt)，-=(v1,v2)。v1v2v3v4v5vsvt(13,7) (5,5) (9,9) (4,4) (6,6) (5,2) (5,0) (4,0) (5,5) (4,4) (9,7) (10,5) 图图 7.26设设f是网络是网络G上的一个可行流，上的一个可行流，是从是从vs到到vt的一的一条链，若对条链，若对上的任意一条边上的任意一条边(vi,vj)有有假设假设(vi,vj) +，则，则0fijcij，即

36、，即+中每一边中每一边是非饱和边。是非饱和边。假设假设(vi,vj) -，则，则0fijcij，即，即-中每一边是中每一边是非零流边。非零流边。则称则称是一条增广链。是一条增广链。例如图例如图7.26中，链中，链=vs, v1, v2, v3, v5, vt就是一就是一条增广链，因为条增广链，因为+=(vs,v1)，(v2,v3)，(v3,v5)，(v5,vt)中的边均为非饱和边，而中的边均为非饱和边，而-=(v1,v2)中中的边为非零流边。的边为非零流边。v1v2v3v4v5vsvt(13,7) (5,5) (9,9) (4,4) (6,6) (5,2) (5,0) (4,0) (5,5)

37、(4,4) (9,7) (10,5) 图图 7.26对于给定的网络对于给定的网络G = (V,E,C)，设，设S,TV，并且，并且ST=V，ST=，vs S，vt T，以，以S中点为始点，以中点为始点，以T中点中点为终点的边的集合，称为为终点的边的集合，称为G的割集，记为的割集，记为(S,T)。割集。割集(S,T)中所有边的容量之和称中所有边的容量之和称为割集为割集(S,T)的容量，记为的容量，记为C(S,T)，即，即(,) ( , )( , )ijijv vS TC S Tc例如图例如图7.26中中 ,设设S1=vs，T 1= v1, v2, v3, v4, v5, vt，那么，那么 (S1

38、, T1)= (vs,v1)，(vs,v2)，其容，其容量为量为C (S1, T1)=22。设设S2=vs,v1，T 2= v2, v3, v4, v5, vt那么那么(S2, T2)= (vs,v2)，(v1,v4)，其容量为，其容量为C (S2, T2)=20。v1v2v3v4v5vsvt(13,7) (5,5) (9,9) (4,4) (6,6) (5,2) (5,0) (4,0) (5,5) (4,4) (9,7) (10,5) 图图 7.26 如果从网络如果从网络G中去掉割集中去掉割集(S,T)中的边，从中的边，从vs就没有路可以到达就没有路可以到达vt。对于网络。对于网络G，它有许

39、，它有许多割集，我们可以找到容量最小割集。而网络多割集，我们可以找到容量最小割集。而网络G的最大流量一定不会超过容量最小割集的容的最大流量一定不会超过容量最小割集的容量，称网络量，称网络G中容量最小的割集为中容量最小的割集为G的最小割的最小割集。如果把网络集。如果把网络G看成各种粗细不同的管道网，看成各种粗细不同的管道网，而最小割集就相当于管道网中最细管道部分的而最小割集就相当于管道网中最细管道部分的总和。总和。二、最大流最小割集定理二、最大流最小割集定理 由上面例子可知，如果找到网络由上面例子可知，如果找到网络G的一个的一个可行流，其流量等于网络可行流，其流量等于网络G的最小割集容量，的最小

40、割集容量，则该可行流一定是最大流。下面最大流最小割则该可行流一定是最大流。下面最大流最小割集定理就是要说明这一点。集定理就是要说明这一点。定理定理1可行流可行流f *是最大流当且仅当是最大流当且仅当G中不存在中不存在关于关于f *的增广链。的增广链。推论在任意一个容量网络中，最大流的流量推论在任意一个容量网络中，最大流的流量等于最小割集的容量。等于最小割集的容量。三、求最大流的标号算法三、求最大流的标号算法由上面定理由上面定理1可知可行流可知可行流f是否是最大流，关键看是否是最大流，关键看网络网络G中是否存在关于可行流中是否存在关于可行流f的增广链，定理的增广链，定理1的的证明过程为我们提供了

41、寻找增广链的方法及改进证明过程为我们提供了寻找增广链的方法及改进可行流可行流f的方法。如果在网络的方法。如果在网络G中存在关于可行流中存在关于可行流f的增广链从的增广链从vs到到vt），则可按定理），则可按定理1证明中所给证明中所给的方法修改可行流的方法修改可行流f，得到一个新的可行流，得到一个新的可行流f ，而，而f 的流量大于的流量大于f的流量。如果在的流量。如果在G中不存在关于可行中不存在关于可行流流f的增广链，则可行流的增广链，则可行流f就是最大流。寻找关于可就是最大流。寻找关于可行流行流f的增广链可按下面介绍的标号法来实现。的增广链可按下面介绍的标号法来实现。求网络求网络G的最大流的

42、标号法分为两步，第的最大流的标号法分为两步，第1步步是标号过程，通过标号寻找增广链；第是标号过程，通过标号寻找增广链；第2步是调步是调整过程，沿增广链个性可行流整过程，沿增广链个性可行流f的流量。的流量。设设f是网络是网络G上的可行流初始可行流可取零流上的可行流初始可行流可取零流f=fij=0）。）。1标号过程标号过程（1首先给发点首先给发点vs标号标号(0,+)。（2选择一个已标号的顶点选择一个已标号的顶点vi，对所有与，对所有与vi相相邻而没有标号的顶点邻而没有标号的顶点vj按下列规则处理。按下列规则处理。（a假设假设(vi,vj)E，并且，并且fij0，则给顶点，则给顶点vj以标号以标号

43、(i,j)，其中，其中j =mini , cij- fji。重复过程重复过程2），可能出现两种结果，其一是），可能出现两种结果，其一是终点终点vt得到标号，说明存在一条增广链，则转到得到标号，说明存在一条增广链，则转到调整过程，其二是终点调整过程，其二是终点vt不能获得标号，说明不不能获得标号，说明不存在增广链，这时可行流存在增广链，这时可行流f即为最大流。即为最大流。2调整过程调整过程首先按终点首先按终点vt及其它顶点的第一个标号，用反及其它顶点的第一个标号，用反向追踪法在网络中找出增广链。例如设终点向追踪法在网络中找出增广链。例如设终点vt的的第一个标号为第一个标号为k，那么，那么(vk,

44、vt)是增广链上的边，是增广链上的边，然后根据然后根据vk的第一个标号，找到下一个顶点，的第一个标号，找到下一个顶点，即若即若vk的第一个标号为的第一个标号为j，那么，那么(vj,vk)（或者（或者(vk,vj)）是增广链上的边，直到用此方法找到）是增广链上的边，直到用此方法找到vs为止。这时就得到一条从为止。这时就得到一条从vs到到vt的增广链的增广链。最。最后按下式修改可行流后按下式修改可行流f。,ijtijtijijffff.),(,),(,),(jijijivvvvvv调整结束后，去掉所有标号，返回标号过程重调整结束后，去掉所有标号，返回标号过程重新进行标号过程。新进行标号过程。令令例

45、例10用标号法求下图中从用标号法求下图中从vs到到vt的最大流。的最大流。 vsvt v4 v2 v3 v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)解（解（I标号过程标号过程（1首先给发点首先给发点vs标以标以(0,+). vsvt v4 v2 v3 v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+) vsvt v4 v2 v3 v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+)（2检查与检查与vs相邻的顶点相邻的顶点v

46、1，v2，由于，由于(vs,v1)E，并且，并且fs1=40，所以，所以v2可以获得标号可以获得标号(v1,2)，其，其中中2 =min1, f21=min9,3=3。由于。由于(v1,v4)E，并且，并且f14=0c14=4，所以，所以v4可以获得标号可以获得标号(v1,4)，其中，其中4 =min9, 4-0=4。由于。由于(v1,v3)E，但，但f13=c13，所以，所以v3不能不能标号。标号。(vs,11)(v1,3)(v1,4) vsvt v4 v2 v3 v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+)（4检查与检查与v

47、2相邻且没有标号的顶点相邻且没有标号的顶点v3， 由于由于(v2,v3)E，并且，并且f23=1c23=5，所以，所以v3可以获得标可以获得标号号(v2,3)，其中，其中3 min2, c23-f23 =min3,5-1=3 。(vs,11)(v1,3)(v1,4)(v2,3) vsvt v4 v2 v3 v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+)(vs,11)(v1,3)(v1,4)(v2,3)（5由于与由于与v3相邻且没有标号的顶点为相邻且没有标号的顶点为vt，并且，并且vt也与已也与已标号的顶点标号的顶点v4相邻，所以相

48、邻，所以vt既可以以既可以以v3为基础获得标号为基础获得标号(v3,t)，也可以以，也可以以v4为基础获得标号为基础获得标号 (v4,t)。但为减少迭。但为减少迭代次数，应选择代次数，应选择1与与t两者较大的给两者较大的给vt标号。因为标号。因为t= min3, c3t-f3t=min 3,3=3, t = min4, c4t-f4t= min 4,5=4，所以，所以vt的标号应取的标号应取v4,4）。）。(v4,4) vsvt v4 v2 v3 v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(11,8)(4,0)(0,+)(vs,11)(v1,3)(v1,4)

49、(v2,3)(v4,4)（II调整过程调整过程由于由于vt的第一个标号为的第一个标号为v4，得到顶点，得到顶点v4，由，由v4的第一个标号为的第一个标号为v1，得到顶点，得到顶点v1，由，由v1的第一个的第一个标号为标号为vs，得到顶点，得到顶点vs ，由此得到关于可行流，由此得到关于可行流f的的增广链增广链=vs, v1, v4 , vt，其中，其中(vs,v1),(v1,v4) ,(v4,vt)为前向边。为前向边。 vsvt v4 v2 v3 v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+)(vs,11)(v1,3)(v1,4)

50、(v2,3)(v4,4)（II调整过程调整过程由于由于t=4，所以调整量为，所以调整量为4，即增广链，即增广链上的前上的前向边流量加向边流量加4。 vsvt v4 v2 v3 v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+)重新开始标号过程，重新开始标号过程， （I标号过程标号过程（1首先给发点首先给发点vs标以标以(0,+). vsvt v4 v2 v3 v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+)(vs,7)（2检查与检查与vs相邻的顶点相邻的顶点v1，v2，由于

51、，由于(vs,v1)E，并且，并且fs1=80，所以，所以v2可以获得标可以获得标号号(v1,2)，其中，其中2 =min1, f21=min9,3=3。由。由于于(v1,v3)E，但，但f13=c13，所以，所以v3不能标号。由不能标号。由于于(v1,v4)E，并且，并且f14=c14，所以，所以v4不能标号。不能标号。 vsvt v4 v2 v3 v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+)(vs,11)(v1,3)(v2,1)(v2,3)（5检查与检查与v2相邻且没有标号的顶点相邻且没有标号的顶点v3， v4，由于，由于(

52、v2,v3)E，并且，并且f23=1c23=5，所以，所以v3可以获得标号可以获得标号(v2,3)，其中，其中3 =min2, c23-f23=min3,4=3。由于。由于(v2,v4)E，并且，并且f24=5c24=6，所以，所以v4可以获得标号可以获得标号(v2,4)，其中，其中4 =min2, c23-f23 =min3, 6-5=1。 vsvt v4 v2 v3 v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+)(vs,7)(v1,3)(v2,1)(v2,3)(v3,3)（5由于与由于与v3相邻且没有标号的顶点为相邻且没有标号

53、的顶点为vt，并且，并且vt也与已也与已标号的顶点标号的顶点v4相邻，所以相邻，所以vt既可以以既可以以v3为基础获得标号为基础获得标号(v3,t)，也可以以，也可以以v4为基础获得标号为基础获得标号 (v4,t)。但为减少迭。但为减少迭代次数，应选择代次数，应选择1与与t两者较大的给两者较大的给vt标号。因为标号。因为t= min3, c3t-f3t=min 3,3=3, t = min4, c4t-f4t= min 1,1=1，所以，所以vt的标号应取的标号应取v3,3）。）。 vsvt v4 v2 v3 v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)(10,9)(11,8)(4,4)(0,+)(vs,11)(v1,3)(v1,4)(v2,3