1、1第七章图与网络理论第七章图与网络理论例例1 哥尼斯堡七桥问题哥尼斯堡七桥问题ABCDABCD 哥尼斯堡七桥问题哥尼斯堡城中有一条哥尼斯堡七桥问题哥尼斯堡城中有一条河，河上有七座连结着两岸和河中的两个小岛，河，河上有七座连结着两岸和河中的两个小岛，如图如图7.1所示。问题是一个人能否从一点出发，所示。问题是一个人能否从一点出发，经过每座桥一次且仅一次，回到原出发点。经过每座桥一次且仅一次，回到原出发点。图图7.12第一节图的基本概念第一节图的基本概念 所谓图，就是顶点和边的集合，点的集合记为所谓图，就是顶点和边的集合，点的集合记为V=v1,v2,vn，边的集合记为，边的集合记为E=e1,e2,
2、em ，vi称为图的顶点，称为图的顶点，ej称为图的边，若边称为图的边，若边ej联结联结vs和和vt，则记为则记为(vs,vt)，即，即ej=(vs,vt)。则图可以表示为：则图可以表示为：G=(V,E)，点代表被研究的事物，边代表事物之间的联系，点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个因此，边不能离开点而独立存在，每条边都有两个端点。端点。在画图时，顶点的位置、边和长短形状都是无在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。则两个图相同。3123451
3、234567115215312422524645734,(,),(,),(,),(,),(,),(,),(,)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.84 在一个图中，若在一个图中，若e=(u,v)，则称，则称u,v是边是边e的的端点端点并并u,v称称相邻相
4、邻称称e是点是点u（v及点）及点）的的关联边关联边。若边。若边ei,ej有一个公共的端点有一个公共的端点u，称，称边边ei,ej相邻相邻。若边。若边e的两个端点是同一顶点，的两个端点是同一顶点，则称此边为则称此边为环环。若两顶点之间有多于一条的。若两顶点之间有多于一条的边，则这些边称为边，则这些边称为多重边多重边。如图。如图7.7中，中，e7是是环，环，e1,e2是多重边。是多重边。一个不含环和多重边的图称为一个不含环和多重边的图称为简单图简单图。含有多重边的图称为含有多重边的图称为多重图多重图。我们这里所说。我们这里所说的图，如不特别指明，都是简单图。的图，如不特别指明，都是简单图。5 以点
5、以点v为端点的边的条数称为点为端点的边的条数称为点v的的度度，记作，记作d(v),如图如图7.7中中d(v1)=3,d(v3)=1。度为零的点称为度为零的点称为弧立点弧立点，度为，度为1的点称为的点称为悬挂悬挂点点。悬挂点的边称为。悬挂点的边称为悬挂边悬挂边。度为奇数的点称为。度为奇数的点称为奇点奇点，度为偶数的点称为，度为偶数的点称为偶点偶点。不难证明：在一个图中，顶点度数的总和等不难证明：在一个图中，顶点度数的总和等于边数的倍，奇顶点的个数必为偶数。于边数的倍，奇顶点的个数必为偶数。链：链：由两两相邻的点及其相关联的边构成的点边序由两两相邻的点及其相关联的边构成的点边序列列;如如:v0,e
6、1,v1,e2,v2,e3,v3,vn-1,en,vn;v0,vn分别为链的起点和终点；分别为链的起点和终点；简单链：简单链：链中所含的边均不相同；链中所含的边均不相同；初等链：初等链：链中所含的点均不相同；链中所含的点均不相同；圈：圈：在链中，若在链中，若 v0=vn 则称该链为圈；则称该链为圈；连通图：连通图：图中任意两点之间均至少有一图中任意两点之间均至少有一 条链相连条链相连，6第二节树第二节树 树是一类结构简单而又十分有用的图。树是一类结构简单而又十分有用的图。一个不含圈的连通图称为树。一个不含圈的连通图称为树。设图设图T=(V,E)，含有，含有n个顶点，则下列命个顶点，则下列命题是
7、等价的。题是等价的。（1）T是树。是树。（2）T的任意两顶点之间，有唯一的链相连。的任意两顶点之间，有唯一的链相连。（3）T连通且有连通且有n1条边。条边。（4）T无圈且有无圈且有n1条边。条边。（5）T无圈但添加一条边得唯一一圈。无圈但添加一条边得唯一一圈。（6）T连通但去掉一条边则不连通。连通但去掉一条边则不连通。7 给定图给定图G=(V,E)，若，若V V,E E，并且并且E中的边的端点都属于中的边的端点都属于V ，则称，则称G=(V,E)是是G的一个子图。特别地，若的一个子图。特别地，若V=V，则称，则称G为为G的支撑子图。的支撑子图。设设T是图是图G的一个支撑子图，若的一个支撑子图，
8、若T是一树，是一树，则称则称T是是G的一个支撑树。的一个支撑树。给定图给定图G=(V,E),对于对于G的每一条边，可的每一条边，可赋以一个实数赋以一个实数w(e)，称为边，称为边e的权，图的权，图G连同连同它边上的权称为赋权图。赋权图在图论的应它边上的权称为赋权图。赋权图在图论的应用中经常出现。根据实际问题的需要，权可用中经常出现。根据实际问题的需要，权可以有不同的实际含义，它可以表示距离、流以有不同的实际含义，它可以表示距离、流量、时间、费用等。量、时间、费用等。8 给定图给定图G=(V,E),设设T=(V,E)是是G的一的一个支撑树，定义树个支撑树，定义树T的权为的权为即支撑树即支撑树T上
9、所有边的权的总和。图上所有边的权的总和。图G的的最小支撑树就是图最小支撑树就是图G中权最小的支撑树。中权最小的支撑树。求图求图G的最小支撑树的方法是建立在求的最小支撑树的方法是建立在求图图G的支撑树基础上，只需在求图的支撑树基础上，只需在求图G的支的支撑树的算法再加适当限制。因此，求最小撑树的算法再加适当限制。因此，求最小支撑树方法也有相应的支撑树方法也有相应的破圈法；避圈法破圈法；避圈法。E)()(eewTw9例例2分别用破圈法，避圈法求图分别用破圈法，避圈法求图7.17的最小支撑树。的最小支撑树。图图7.17v1v5v2v3v42v6v7v8343462366458510v1v5v2v3v
10、42v6v7v83434623664585解破圈法解破圈法11v1v5v2v3v42v6v7v83434623664585避圈法：避圈法：12第三节最短路问题第三节最短路问题 最短路问题，一般来说就是从给定的赋权最短路问题，一般来说就是从给定的赋权图中，寻找两点之间权最小的链（链的权即链中图中，寻找两点之间权最小的链（链的权即链中所有边的权之和）。许多优化问题都需要求图的所有边的权之和）。许多优化问题都需要求图的最短路，如选址、管道铺设、设备更新、整数规最短路，如选址、管道铺设、设备更新、整数规划等问题。由于所求问题不同，需要使用不同的划等问题。由于所求问题不同，需要使用不同的方法。下面我们介
11、绍常用的算法。方法。下面我们介绍常用的算法。一、一、Dijkstra算法算法 Dijkstra算法是求赋权有向图中，某两点算法是求赋权有向图中，某两点之间最短路的算法。实际上，它可以求某一点到之间最短路的算法。实际上，它可以求某一点到其它各点的最短路。它是其它各点的最短路。它是Dijkstra于于1959年提出。年提出。目前被认为是求非负权最短路的最好的算法。目前被认为是求非负权最短路的最好的算法。13 Dijkstra算法的基本思想是基于以下原理：算法的基本思想是基于以下原理：若若vs,vl,vj是是vs到到vj的最短路，的最短路，vi是此路中某一是此路中某一点，则点，则vs,vl,vi必是
12、从必是从vs到到vi的最短路。此算法的最短路。此算法的基本步骤是采用标号法，给图的基本步骤是采用标号法，给图G每一个顶点每一个顶点一个标号。标号分两种：一种是一个标号。标号分两种：一种是T标号，一种标号，一种是是P标号。标号。T标号也称临时标号，它表示从标号也称临时标号，它表示从vs到到这一点的最短路长度的一个上界，这一点的最短路长度的一个上界，P标号也称标号也称固定标号，它表示从固定标号，它表示从vs到这一点的最短路的长到这一点的最短路的长度（这里最短路长度是指这条路上个边权的度（这里最短路长度是指这条路上个边权的和）。算法每一步都把某点的和）。算法每一步都把某点的T标号改变为标号改变为P标
13、标号。当终点得到号。当终点得到P标号，算法结束。若要求某标号，算法结束。若要求某点到其它各点的最短路，则最多经过点到其它各点的最短路，则最多经过n-1步算法步算法结束。结束。14设设lij表示边表示边(vi,vj)的权，则的权，则Dijkstra算法步骤如下：算法步骤如下：（1）给始点以）给始点以P标号标号P（0,0），给其它各点），给其它各点vj以以T标号标号T(dj,v1)，其中，其中，dj=l1j，（若，（若vj与与v1不相不相邻，则令邻，则令l1j=+）。）。（2）在所有）在所有T标号点中，若标号点中，若vk的的T标号最小，标号最小，则把则把vk的的T标号改为标号改为P标号标号。若最小
14、的若最小的T标号不止标号不止一个，则可任取一个改为一个，则可任取一个改为P标号。标号。（3）修改所有）修改所有T标号标号T(dj,vt)；dj=min dj,dk+lk j,若若dk+lk jdj vt=vk否则不变。否则不变。（4）当终点或全部顶点都得到）当终点或全部顶点都得到P标号，标号，算法结束，否则返回（算法结束，否则返回（2）。）。15例例3求图求图7.20中，中，v1到到v8的最短路。的最短路。图图 7.20v4v2v1v3v6v5v7v8983834256767109416图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)T(9,v1
15、)T(3,v1)T(8,v1)17图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)T(9,v1)T(7,v3)T(3,v1)T(8,v1)P(3,v1)18图图 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)19图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)T(9,v1)T(8,v1)P(3,v1)P(7,v3)T(14,v6)P(9,v1)P(8,v1
16、)T(17,v2)T(16,v6)20图图 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)21图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)P(3,v1)P(17,v2)P(7,v3)P(9,v1)P(8,v1)P(14,v6)P(16,v6)22例例4 求图求图7.22中，中，v1到其它各点的最短路。到其它各点的最短路。图图 7.22v4v2v1v3
17、v6v5v7v8354263441517498Dijkstra算法同样可用于求无向图的最短路。算法同样可用于求无向图的最短路。23图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)T(3,v1)T(4,v1)T(2,v1)24图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)T(3,v1)T(4,v1)T(2,v1)P(2,v1)T(7,v4)T(3,v4)P(3,v1)T(8,v2)T(9,v2)25图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)P(2,v1
18、)T(7,v4)T(3,v4)P(3,v1)T(8,v2)T(9,v2)P(3,v4)T(6,v3)26图图 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)27图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 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)28图图 7.22v4v2v1v
19、3v6v5v7v8354263441517498解解 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)29图图 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,v5)30二、逐次逼近法二、逐次逼近法 前面介绍的前面介绍的Dijkstra 算法，只适用于权算法，只适用于权为非负的赋权图中求最短路问题。逐次逼近为非负的赋权图中求最短路问题。逐次逼近法可用于存在负权，但无负有向回路的赋权法
20、可用于存在负权，但无负有向回路的赋权图的最短路问题。图的最短路问题。因为，如果因为，如果dj是从是从v1到到vj的最短路的长度的最短路的长度，而这从条最短路的最后一条边为，而这从条最短路的最后一条边为(vk,vj)，则从则从v1到到vj的最短路中，从的最短路中，从v1到到vk这一段，必这一段，必然也是从然也是从v1到到vk的最短路的最短路。若其长度记为若其长度记为dk，lk j表示边表示边(vk,vj)的权，那么的权，那么dj，dk和和lk j应满足应满足下列方程：下列方程：)(minkjkkjldd31 逐次逼近法就是用迭代方法解这个逐次逼近法就是用迭代方法解这个方程。第一次逼近是找点方程。
21、第一次逼近是找点v1到点到点vj由一条由一条边所组成的最短路，其长记为边所组成的最短路，其长记为dj(1)；第二；第二次逼近是求从次逼近是求从v1到点到点vj不多于两条边组成不多于两条边组成的最短路，其长记为的最短路，其长记为dj(2)；以此类推，第；以此类推，第m次逼近是求从次逼近是求从v1到到vj不多于不多于m条边组成条边组成的最短路，其长记为的最短路，其长记为dj(m)。因为图中，不因为图中，不含负有向回路，所以从含负有向回路，所以从v1到到vj的最短路上的最短路上最多有最多有n-1条边条边。从而可知，最多做从而可知，最多做n-1次逼近就可求出从次逼近就可求出从v1到到vj的最短路。的最
22、短路。32()(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=1,2,n)即为即为v1到其它各到其它各点的最短路的长度，否则返回（点的最短路的长度，否则返回（2）。）。33例例4求下图中，求下图中，v1到其它各点的最短路。到其它各点的最短路。min)()1(ijkikjldd v1 1 3 9 5 3 83 6
23、2v6 v5 v3 v4 v2013103930583503698302620654321L1jjld)1(34min)()1(ijkikjldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd02635min1)1()2(1iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd36min2)1()2(2iildd v1 1 3 9 5 3 83 6 2v6
24、 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd237min3)1()2(3iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2538min4)1()2(4iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ij
25、kikjldd2 251039min5)1()2(5iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510940min6)1()2(6iildd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510941)3(jdmin)2()3(ijijldd v1 1 3 9 5 3 83 6 2v6
26、 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 251090251081042)3(jdmin)3()4(ijijldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2013103930583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510902510810)4(jd025108943)3(jdmin)4()5(ijijldd v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v201310393
27、0583503698302620654321L)1(jd026)2(jd0min)()1(ijkikjldd2 2510902510810)4(jd0251089)5(jd025108944例例5求图求图7.24中，中，v1到其它各点的最短路。到其它各点的最短路。图图7.24v1v2v3v4v5v6v7v834-14-22545-3-2-435445jilijdj(1)dj(2)dj(3)dj(4)dj(5)dj(6)v1v2v3v4v5v6v7v8v1034000000v20-1-24333333v305422222v4204511111v50-2375555v6045333v7-3-405
28、97777v801087746第四节最大流问题第四节最大流问题 给定一个有向图给定一个有向图G=(V,E)，每条边，每条边(vi,vj)给定一个非负数给定一个非负数cij称为边称为边(vi,vj)容量。容量。假设假设G中只有一个入度为零的点中只有一个入度为零的点vs称为发点称为发点，只有一个出度为零的点，只有一个出度为零的点vt称为收点，其余称为收点，其余点称为中间点，这样的有向图称为容量网点称为中间点，这样的有向图称为容量网络，记为络，记为G=(V,E,C)。47 例如图例如图7.25就是一个容量网络。如果就是一个容量网络。如果vs表示表示油田，油田，vt表示炼油厂，图表示炼油厂，图7.25
29、表示从油田到炼油表示从油田到炼油厂的输油管道网。边上的数字表示该管道的最大厂的输油管道网。边上的数字表示该管道的最大输油能力，中间点表示输油泵站。现在要问如何输油能力，中间点表示输油泵站。现在要问如何安排各管道输油量，才能使从安排各管道输油量，才能使从vs到到vt输油量最大？输油量最大？这就是本节所要介绍的最大流问题。这就是本节所要介绍的最大流问题。图图 7.25v1v2v3v4vsvt54142537848一、基本概念一、基本概念 给定一个容量网络给定一个容量网络G=(V,E,C)，所谓网络，所谓网络G上的流，是指每条边上的流，是指每条边(vi,vj)上确定的一个数上确定的一个数f(vi,v
30、j)，简记为，简记为fij，称集合，称集合f=fij为网络为网络G上的一个流。上的一个流。如果网络如果网络G表示一个输油管道网，则表示一个输油管道网，则cij表示管表示管道输油能力，而道输油能力，而fij表示管道当前的实际流量，因表示管道当前的实际流量，因此应有此应有0 fij cij，即管道中的流量不能超过该管道，即管道中的流量不能超过该管道的最大通过能力（即管道的容量）的最大通过能力（即管道的容量）。对网络对网络G上上的中间点表示一个转送泵站，因此对中间点运出的中间点表示一个转送泵站，因此对中间点运出的总量与运进的总量应当相等的总量与运进的总量应当相等。而对于发点的净而对于发点的净流出量和
31、收点的净流入量必相等，并且就是该运流出量和收点的净流入量必相等，并且就是该运输方案的总输送量。输方案的总输送量。490kkijijffikktsiWff容量网络容量网络G=(V,E,C)中的一个流中的一个流f=fij满足下列满足下列条件，称条件，称f为可行流。为可行流。（1）容量限制条件：对）容量限制条件：对G中每条边中每条边(vi,vj)，有有 0 fij cij。（2）平衡条件：对于中间点）平衡条件：对于中间点vi，有，有（即流出量流入量）。（即流出量流入量）。对于收点对于收点vt与发点与发点vs，有，有（即从（即从vs的净输出量与的净输出量与vt的净输入量相等）。的净输入量相等）。W称为
32、可行流称为可行流f的流量。的流量。可行流总是存在的，当所有边的流量可行流总是存在的，当所有边的流量fij=0时时，就得到一个可行流，它的流量，就得到一个可行流，它的流量W=0。最大流问。最大流问题就是在容量网络中，寻找流量最大的可行流。题就是在容量网络中，寻找流量最大的可行流。50 对于容量网络对于容量网络G给定一个可行流给定一个可行流f=fij，当，当fij=cij时，称边时，称边(vi,vj)为饱和边，当为饱和边，当fij 0时，称边时，称边(vi,vj)为为非零流边。非零流边。设设是网络是网络G中一条联结发点中一条联结发点vs和收点和收点vt的的链链。我们规定我们规定的正方向从的正方向从
33、vs到到vt，则链，则链上上的边被分为两类：一类是边的方向与链的的边被分为两类：一类是边的方向与链的正方向一致，称它们为前向边，正方向一致，称它们为前向边，上上前向上上前向边的全体记为边的全体记为+。另一类边与链的正方向另一类边与链的正方向相反，称它们为后向边，相反，称它们为后向边，上后向边的全体上后向边的全体记为记为-。51v1v2v3v4v5vsvt(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中，其边上的两个数字分别表示中，其边上的两个数字分别表示边的容量和流量，即边的
34、容量和流量，即(cij,fij)。(v2,v5)为饱和边，为饱和边，(vs,v1)为非饱和边，并且为非饱和边，并且(v2,v5)，(vs,v1)均为非零流均为非零流边，边，(v3,v5)是零流边。是零流边。52例如图例如图7.26中，在联结中，在联结vs和和vt的链的链=vs,v1,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
35、)(4,4)(9,7)(10,5)图图 7.2653设设f是网络是网络G上的一个可行流，上的一个可行流，是从是从vs到到vt的一的一条链，若对条链，若对上的任意一条边上的任意一条边(vi,vj)有有若若(vi,vj)+，则，则0 fijcij，即，即+中每一边是非中每一边是非饱和边。饱和边。若若(vi,vj)-，则，则0fij cij，即，即-中每一边是非零中每一边是非零流边。流边。则称则称是一条是一条增广链增广链。54例如图例如图7.26中，链中，链=vs,v1,v2,v3,v5,vt就是一条就是一条增广链，因为增广链，因为+=(vs,v1)，(v2,v3)，(v3,v5)，(v5,vt)中
36、的边均为非饱和边，而中的边均为非饱和边，而-=(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.2655对于给定的网络对于给定的网络G=(V,E,C)，设，设S,T V V，并且，并且S T=V V，S T=，vs S，vt T，以，以S中点为始点，以中点为始点，以T中点为终点中点为终点的边的集合，称为的边的集合，称为G的割集，记为的割集，记为(S,T)。割集割集(S,T)中所有边的容量之和称为割集中所有边的容量之和称为割集(S,T)
37、的容量，记为的容量，记为C(S,T)，即，即(,)(,)(,)ijijv vS TC S Tc56例如图例如图7.26中中,设设S1=vs，T 1=v1,v2,v3,v4,v5,vt，则，则(S1,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.265
38、7 如果从网络如果从网络G中去掉割集中去掉割集(S,T)中的边，从中的边，从vs就没有路可以到达就没有路可以到达vt。对于网络。对于网络G，它有许，它有许多割集，我们可以找到容量最小割集。而网络多割集，我们可以找到容量最小割集。而网络G的最大流量一定不会超过容量最小割集的容的最大流量一定不会超过容量最小割集的容量，称网络量，称网络G中容量最小的割集为中容量最小的割集为G的最小割的最小割集。如果把网络集。如果把网络G看成各种粗细不同的管道网，看成各种粗细不同的管道网，而最小割集就相当于管道网中最细管道部分的而最小割集就相当于管道网中最细管道部分的总和。总和。二、最大流最小割集定理二、最大流最小割
39、集定理 由上面例子可知，如果找到网络由上面例子可知，如果找到网络G的一个的一个可行流，其流量等于网络可行流，其流量等于网络G的最小割集容量，的最小割集容量，则该可行流一定是最大流。下面最大流最小割则该可行流一定是最大流。下面最大流最小割集定理就是要说明这一点。集定理就是要说明这一点。58定理定理1可行流可行流f*是最大流当且仅当是最大流当且仅当G中不存在中不存在关于关于f*的增广链。的增广链。推论在任意一个容量网络中，最大流的流量推论在任意一个容量网络中，最大流的流量等于最小割集的容量。等于最小割集的容量。三、求最大流的标号算法三、求最大流的标号算法由上面定理由上面定理1可知可行流可知可行流f
40、是否是最大流，关键看是否是最大流，关键看网络网络G中是否存在关于可行流中是否存在关于可行流f的增广链，定理的增广链，定理1的的证明过程为我们提供了寻找增广链的方法及改进证明过程为我们提供了寻找增广链的方法及改进可行流可行流f的方法。如果在网络的方法。如果在网络G中存在关于可行流中存在关于可行流f的增广链（从的增广链（从vs到到vt），则可按定理），则可按定理1证明中所给的证明中所给的方法修改可行流方法修改可行流f，得到一个新的可行流，得到一个新的可行流f，而，而f 的流量大于的流量大于f的流量。如果在的流量。如果在G中不存在关于可行中不存在关于可行流流f的增广链，则可行流的增广链，则可行流f就
41、是最大流。寻找关于可就是最大流。寻找关于可行流行流f的增广链可按下面介绍的标号法来实现。的增广链可按下面介绍的标号法来实现。59求网络求网络G的最大流的标号法分为两步，第的最大流的标号法分为两步，第1步步是标号过程，通过标号寻找增广链；第是标号过程，通过标号寻找增广链；第2步是调步是调整过程，沿增广链个性可行流整过程，沿增广链个性可行流f的流量。的流量。设设f是网络是网络G上的可行流（初始可行流可取零流上的可行流（初始可行流可取零流f=fij=0）。）。1标号过程标号过程（1）首先给发点）首先给发点vs标号标号(0,+)。（2）选择一个已标号的顶点）选择一个已标号的顶点vi，对所有与，对所有与
42、vi相相邻而没有标号的顶点邻而没有标号的顶点vj按下列规则处理。按下列规则处理。（a）若）若(vi,vj)E，并且，并且fij0，则给顶点，则给顶点vj以标以标号号(i,j)，其中，其中j=mini,cij-fji。60重复过程（重复过程（2），可能出现两种结果，其一是），可能出现两种结果，其一是终点终点vt得到标号，说明存在一条增广链，则转到得到标号，说明存在一条增广链，则转到调整过程，其二是终点调整过程，其二是终点vt不能获得标号，说明不不能获得标号，说明不存在增广链，这时可行流存在增广链，这时可行流f即为最大流。即为最大流。2调整过程调整过程首先按终点首先按终点vt及其它顶点的第一个标号
43、，用反及其它顶点的第一个标号，用反向追踪法在网络中找出增广链。例如设终点向追踪法在网络中找出增广链。例如设终点vt的的第一个标号为第一个标号为k，则，则(vk,vt)是增广链上的边，然后是增广链上的边，然后根据根据vk的第一个标号，找到下一个顶点，即若的第一个标号，找到下一个顶点，即若vk的第一个标号为的第一个标号为j，则，则(vj,vk)（或者（或者(vk,vj)）是增广）是增广链上的边，直到用此方法找到链上的边，直到用此方法找到vs为止。这时就得为止。这时就得到一条从到一条从vs到到vt的增广链的增广链。最后按下式修改可行。最后按下式修改可行流流f。61,ijtijtijijffff.),
44、(,),(,),(jijijivvvvvv调整结束后，去掉所有标号，返回标号过程重调整结束后，去掉所有标号，返回标号过程重新进行标号过程。新进行标号过程。令令62例例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)63解（解（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,+)64 vs
45、vt 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相邻的顶点相邻的顶点v1，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)(
46、v1,4)66 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）检查与）检查与v2相邻相邻且没有标号且没有标号的顶点的顶点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)67 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
47、)(v1,3)(v1,4)(v2,3)（5）由于与）由于与v3相邻且没有标号的顶点为相邻且没有标号的顶点为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 4,5=4，所以，所以vt的标号应取（的标号应取（v4,4）。）。(v4,4)68 vsvt v
48、4 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)(v4,4)（II）调整过程）调整过程由于由于vt的第一个标号为的第一个标号为v4，得到顶点，得到顶点v4，由，由v4的的第一个标号为第一个标号为v1，得到顶点，得到顶点v1，由，由v1的第一个标号的第一个标号为为vs，得到顶点，得到顶点vs，由此得到关于可行流，由此得到关于可行流f的增广的增广链链=vs,v1,v4,vt，其中，其中(vs,v1),(v1,v4),(v4,vt)为前向为前向边。边。69 vsvt v4
49、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)(v4,4)（II）调整过程）调整过程由于由于t=4，所以调整量为，所以调整量为4，即增广链，即增广链上的前上的前向边流量加向边流量加4。70 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,+).71 vsvt v4 v2 v3
50、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，因为，因为(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不能标号。不能标号。73 vsvt v4 v2 v3 v1(15,8)(9,9)(3,3)(5,1)(6,5)(7,7)
