《第七章图与网络理论精选文档.ppt》由会员分享，可在线阅读，更多相关《第七章图与网络理论精选文档.ppt（84页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七章图与网络理论1本讲稿第一页，共八十四页第一节图的基本概念第一节图的基本概念 所谓图，就是顶点和边的集合，点的集合记为所谓图，就是顶点和边的集合，点的集合记为V=v1,v2,vn，边的集合记为，边的集合记为E=e1,e2,em ，vi称为称为图的顶点，图的顶点，ej称为图的边，若边称为图的边，若边ej联结联结vs和和vt，则记为，则记为(vs,vt)，即，即ej=(vs,vt)。则图可以表示为：则图可以表示为：G=(V,E)，点代表被研究的事物，边代表事物之间的联系，因点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端点。此，边不能离开点而独立存在，每
2、条边都有两个端点。在画图时，顶点的位置、边和长短形状都是无关紧要在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，则两个图相同。的，只要两个图的顶点及边是对应相同的，则两个图相同。2本讲稿第二页，共八十四页有些有些图图的的边带边带有方向，有方向，这样这样的的图图称称为为有向有向图图。而。而边边不不带带方向的方向的图图称称为为无向无向图图。图图7.7是一个无向是一个无向图图。图图7.8是一个有向是一个有向图图。v1v5v2v3v4e1e2e3e4e6e5e7图图7.7图图7.83本讲稿第三页，共八十四页 在一个图中，若在一个图中，若e=(u,v)，则称，则称u,
3、v是边是边e的的端点端点并并u,v称称相邻相邻称称e是点是点u（v及点）的及点）的关联关联边边。若边。若边ei,ej有一个公共的端点有一个公共的端点u，称边，称边ei,ej相邻相邻。若边若边e的两个端点是同一顶点，则称此边为的两个端点是同一顶点，则称此边为环环。若两顶点之间有多于一条的边，则这些边称若两顶点之间有多于一条的边，则这些边称为为多重边多重边。如图。如图7.7中，中，e7是环，是环，e1,e2是多重边。是多重边。一个不含环和多重边的图称为一个不含环和多重边的图称为简单图简单图。含。含有多重边的图称为有多重边的图称为多重图多重图。我们这里所说的图，。我们这里所说的图，如不特别指明，都是
4、简单图。如不特别指明，都是简单图。4本讲稿第四页，共八十四页 以点以点v为端点的边的条数称为点为端点的边的条数称为点v的的度度，记作，记作d(v),如图如图7.7中中d(v1)=3,d(v3)=1。度为零的点称为度为零的点称为弧立点弧立点，度为，度为1的点称为的点称为悬挂点悬挂点。悬挂点的边称为悬挂点的边称为悬挂边悬挂边。度为奇数的点称为。度为奇数的点称为奇点奇点，度，度为偶数的点称为为偶数的点称为偶点偶点。不难证明：在一个图中，顶点度数的总和等于不难证明：在一个图中，顶点度数的总和等于边数的倍，奇顶点的个数必为偶数。边数的倍，奇顶点的个数必为偶数。链：链：由两两相邻的点及其相关联的边构成的点
5、边序列由两两相邻的点及其相关联的边构成的点边序列;如如:v0,e1,v1,e2,v2,e3,v3,vn-1,en,vn;v0,vn分别为链的起点和终点；分别为链的起点和终点；简单链：简单链：链中所含的边均不相同；链中所含的边均不相同；初等链：初等链：链中所含的点均不相同；链中所含的点均不相同；圈：圈：在链中，若在链中，若 v0=vn 则称该链为圈；则称该链为圈；连通图：连通图：图中任意两点之间均至少有一图中任意两点之间均至少有一 条链相连条链相连，5本讲稿第五页，共八十四页第二节树第二节树 树是一类结构简单而又十分有用的图。一树是一类结构简单而又十分有用的图。一个不含圈的连通图称为树。个不含圈
6、的连通图称为树。设图设图T=(V,E)，含有，含有n个顶点，则下列命题是个顶点，则下列命题是等价的。等价的。（1）T是树。是树。（2）T的任意两顶点之间，有唯一的链相连。的任意两顶点之间，有唯一的链相连。（3）T连通且有连通且有n1条边。条边。（4）T无圈且有无圈且有n1条边。条边。（5）T无圈但添加一条边得唯一一圈。无圈但添加一条边得唯一一圈。（6）T连通但去掉一条边则不连通。连通但去掉一条边则不连通。6本讲稿第六页，共八十四页 给定图给定图G=(V,E)，若，若V V,E E，并，并且且E中的边的端点都属于中的边的端点都属于V ，则称，则称G=(V,E)是是G的一个子图。特别地，若的一个子
7、图。特别地，若V=V，则，则称称G为为G的支撑子图。的支撑子图。设设T是图是图G的一个支撑子图，若的一个支撑子图，若T是一树，则是一树，则称称T是是G的一个支撑树。的一个支撑树。给定图给定图G=(V,E),对于对于G的每一条边，可赋的每一条边，可赋以一个实数以一个实数w(e)，称为边，称为边e的权，图的权，图G连同它边上连同它边上的权称为赋权图。赋权图在图论的应用中经常出的权称为赋权图。赋权图在图论的应用中经常出现。根据实际问题的需要，权可以有不同的实际现。根据实际问题的需要，权可以有不同的实际含义，它可以表示距离、流量、时间、费用等。含义，它可以表示距离、流量、时间、费用等。7本讲稿第七页，
8、共八十四页 给定图给定图G=(V,E),设设T=(V,E)是是G的一个的一个支撑树，定义树支撑树，定义树T的权为的权为即支撑树即支撑树T上所有边的权的总和。图上所有边的权的总和。图G的最小的最小支撑树就是图支撑树就是图G中权最小的支撑树。中权最小的支撑树。求图求图G的最小支撑树的方法是建立在求图的最小支撑树的方法是建立在求图G的支撑树基础上，只需在求图的支撑树基础上，只需在求图G的支撑树的的支撑树的算法再加适当限制。因此，求最小支撑树方算法再加适当限制。因此，求最小支撑树方法也有相应的法也有相应的破圈法；避圈法破圈法；避圈法。8本讲稿第八页，共八十四页例例2分别用破圈法，避圈法求图分别用破圈法
9、，避圈法求图7.17的最小支撑树。的最小支撑树。图图7.17v1v5v2v3v42v6v7v834346236645859本讲稿第九页，共八十四页v1v5v2v3v42v6v7v83434623664585解破圈法解破圈法10本讲稿第十页，共八十四页v1v5v2v3v42v6v7v83434623664585避圈法：避圈法：11本讲稿第十一页，共八十四页第三节最短路问题第三节最短路问题 最短路问题，一般来说就是从给定的赋权图中，最短路问题，一般来说就是从给定的赋权图中，寻找两点之间权最小的链（链的权即链中所有边的权之寻找两点之间权最小的链（链的权即链中所有边的权之和）。许多优化问题都需要求图的
10、最短路，如选址、管和）。许多优化问题都需要求图的最短路，如选址、管道铺设、设备更新、整数规划等问题。由于所求问题不道铺设、设备更新、整数规划等问题。由于所求问题不同，需要使用不同的方法。下面我们介绍常用的算法。同，需要使用不同的方法。下面我们介绍常用的算法。一、一、Dijkstra算法算法 Dijkstra算法是求赋权有向图中，某两点之间最短算法是求赋权有向图中，某两点之间最短路的算法。实际上，它可以求某一点到其它各点的最短路的算法。实际上，它可以求某一点到其它各点的最短路。它是路。它是Dijkstra于于1959年提出。目前被认为是求非负权年提出。目前被认为是求非负权最短路的最好的算法。最短
11、路的最好的算法。12本讲稿第十二页，共八十四页 Dijkstra算法的基本思想是基于以下原理：若算法的基本思想是基于以下原理：若vs,vl,vj是是vs到到vj的最短路，的最短路，vi是此路中某一点，是此路中某一点，则则vs,vl,vi必是从必是从vs到到vi的最短路。此算法的基本的最短路。此算法的基本步骤是采用标号法，给图步骤是采用标号法，给图G每一个顶点一个标号。每一个顶点一个标号。标号分两种：一种是标号分两种：一种是T标号，一种是标号，一种是P标号。标号。T标号标号也称临时标号，它表示从也称临时标号，它表示从vs到这一点的最短路长度的到这一点的最短路长度的一个上界，一个上界，P标号也称固
12、定标号，它表示从标号也称固定标号，它表示从vs到这一到这一点的最短路的长度（这里最短路长度是指这条路上点的最短路的长度（这里最短路长度是指这条路上个边权的和）。算法每一步都把某点的个边权的和）。算法每一步都把某点的T标号改变标号改变为为P标号。当终点得到标号。当终点得到P标号，算法结束。若要求某标号，算法结束。若要求某点到其它各点的最短路，则最多经过点到其它各点的最短路，则最多经过n-1步算法结束。步算法结束。13本讲稿第十三页，共八十四页设设lij表示表示边边(vi,vj)的的权权，则则Dijkstra算法步算法步骤骤如下：如下：（1）给给始点以始点以P标标号号P（0,0），），给给其它各点
13、其它各点vj以以T标标号号T(dj,v1)，其中，其中，dj=l1j，（若，（若vj与与v1不相不相邻邻，则则令令l1j=+）。）。（2）在所有）在所有T标标号点中，若号点中，若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）。）
14、。14本讲稿第十四页，共八十四页例例3求图求图7.20中，中，v1到到v8的最短路。的最短路。图图 7.20v4v2v1v3v6v5v7v8983834256767109415本讲稿第十五页，共八十四页图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)T(9,v1)T(3,v1)T(8,v1)16本讲稿第十六页，共八十四页图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)T(9,v1)T(7,v3)T(3,v1)T(8,v1)P(3,v1)17本讲稿第十七页，共八十四页图图 7.20v4v2v1v3v6
15、v5v7v89838342567671094解解 P(0,0)T(9,v1)T(7,v3)T(8,v1)P(3,v1)P(7,v3)T(14,v6)T(16,v6)18本讲稿第十八页，共八十四页图图 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)T(17,v2)T(16,v6)19本讲稿第十九页，共八十四页图图 7.20v4v2v1v3v6v5v7v89838342567671094解解 P(0,0)P(3,v1)P(17,v2)P(7,v3)T(14
16、,v6)P(9,v1)P(8,v1)T(17,v2)T(16,v6)P(14,v6)P(16,v6)20本讲稿第二十页，共八十四页图图 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)21本讲稿第二十一页，共八十四页例例4 求求图图7.22中，中，v1到其它各点的最短路。到其它各点的最短路。图图 7.22v4v2v1v3v6v5v7v8354263441517498Dijkstra算法同样可用于求无向图的最短路。算法同样可用于求无向图的最短路。22本
17、讲稿第二十二页，共八十四页图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)T(3,v1)T(4,v1)T(2,v1)23本讲稿第二十三页，共八十四页图图 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)24本讲稿第二十四页，共八十四页图图 7.22v4v2v1v3v6v5v7v8354263441517498解解 P(0,0)P(2,v1)T(7,v4)T(3,v4)P(3,v1)T(
18、8,v2)T(9,v2)P(3,v4)T(6,v3)25本讲稿第二十五页，共八十四页图图 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)26本讲稿第二十六页，共八十四页图图 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)27本讲稿第二十七页，共
19、八十四页图图 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)28本讲稿第二十八页，共八十四页图图 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)29本讲稿第二十九页，共八十四页二、逐次逼近法二、逐次逼近法 前面介前面介绍绍的的Dijkstra 算法，只适用于算法，只适用于权为权为非非负负的的赋权图赋
20、权图中求最短路中求最短路问题问题。逐次逼近法可用于存在。逐次逼近法可用于存在负权负权，但无，但无负负有向回路的有向回路的赋权图赋权图的最短路的最短路问题问题。因因为为，如果，如果dj是从是从v1到到vj的最短路的的最短路的长长度，度，而而这这从条最短路的最后一条从条最短路的最后一条边为边为(vk,vj)，则则从从v1到到vj的最短路中，从的最短路中，从v1到到vk这这一段，必然也是从一段，必然也是从v1到到vk的最短路的最短路。若其若其长长度度记为记为dk，lk j表示表示边边(vk,vj)的的权权，那么，那么dj，dk和和lk j应满应满足下列方程：足下列方程：30本讲稿第三十页，共八十四页
21、 逐次逼近法就是用迭代方法解逐次逼近法就是用迭代方法解这这个方个方程。第一次逼近是找点程。第一次逼近是找点v1到点到点vj由一条由一条边边所所组组成的最短路，其成的最短路，其长记为长记为dj(1)；第二次逼近；第二次逼近是求从是求从v1到点到点vj不多于两条不多于两条边组边组成的最短路，成的最短路，其其长记为长记为dj(2)；以此；以此类类推，第推，第m次逼近是求从次逼近是求从v1到到vj不多于不多于m条条边组边组成的最短路，其成的最短路，其长记为长记为dj(m)。因因为图为图中，不含中，不含负负有向回路，所以有向回路，所以从从v1到到vj的最短路上最多有的最短路上最多有n-1条条边边。从而可
22、从而可知，最多做知，最多做n-1次逼近就可求出从次逼近就可求出从v1到到vj的最短的最短路。路。31本讲稿第三十一页，共八十四页逐次逼近法步逐次逼近法步骤骤如下：如下：(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）。）。32本讲稿第三十二页，共八十四页例例4求下图中，求下图中，v1到其它各点的最短路。到其它各点的
23、最短路。v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v233本讲稿第三十三页，共八十四页 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v202634本讲稿第三十四页，共八十四页 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v2026035本讲稿第三十五页，共八十四页 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v20260236本讲稿第三十六页，共八十四页 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v202602 2537本讲稿第三十七页，共八十四页 v1 1 3 9 5 3 83 6 2v6 v5 v
24、3 v4 v202602 251038本讲稿第三十八页，共八十四页 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v202602 2510939本讲稿第三十九页，共八十四页 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v202602 2510940本讲稿第四十页，共八十四页 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v202602 251090251081041本讲稿第四十一页，共八十四页 v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v202602 2510902510810025108942本讲稿第四十二页，共八十四页
25、v1 1 3 9 5 3 83 6 2v6 v5 v3 v4 v202602 25109025108100251089025108943本讲稿第四十三页，共八十四页例例5求图求图7.24中，中，v1到其它各点的最短路。到其它各点的最短路。图图7.24v1v2v3v4v5v6v7v834-14-22545-3-2-435444本讲稿第四十四页，共八十四页jilijdj(1)dj(2)dj(3)dj(4)dj(5)dj(6)v1v2v3v4v5v6v7v8v1034000000v20-1-24333333v305422222v4204511111v50-2375555v6045333v7-3-40
26、597777v801087745本讲稿第四十五页，共八十四页第四节最大流问题第四节最大流问题 给定一个有向图给定一个有向图G=(V,E)，每条边，每条边(vi,vj)给定一个非负数给定一个非负数cij称为边称为边(vi,vj)容量。假设容量。假设G中中只有一个入度为零的点只有一个入度为零的点vs称为发点，只有一个称为发点，只有一个出度为零的点出度为零的点vt称为收点，其余点称为中间点，称为收点，其余点称为中间点，这样的有向图称为容量网络，记为这样的有向图称为容量网络，记为G=(V,E,C)。46本讲稿第四十六页，共八十四页 例如例如图图7.25就是一个容量网就是一个容量网络络。如果。如果vs表
27、示油田，表示油田，vt表示表示炼炼油厂，油厂，图图7.25表示从油田到表示从油田到炼炼油厂的油厂的输输油管道油管道网。网。边边上的数字表示上的数字表示该该管道的最大管道的最大输输油能力，中油能力，中间间点点表示表示输输油油泵泵站。站。现现在要在要问问如何安排各管道如何安排各管道输输油量，才油量，才能使从能使从vs到到vt输输油量最大？油量最大？这这就是本就是本节节所要介所要介绍绍的最大的最大流流问题问题。图图 7.25v1v2v3v4vsvt54142537847本讲稿第四十七页，共八十四页一、基本概念一、基本概念 给定一个容量网络给定一个容量网络G=(V,E,C)，所谓网络，所谓网络G上的流
28、，上的流，是指每条边是指每条边(vi,vj)上确定的一个数上确定的一个数f(vi,vj)，简记为，简记为fij，称集合，称集合f=fij为网络为网络G上的一个流。上的一个流。如果网络如果网络G表示一个输油管道网，则表示一个输油管道网，则cij表示管道表示管道输油能力，而输油能力，而fij表示管道当前的实际流量，因此应有表示管道当前的实际流量，因此应有0 fij cij，即管道中的流量不能超过该管道的最大通过能，即管道中的流量不能超过该管道的最大通过能力（即管道的容量）。对网络力（即管道的容量）。对网络G上的中间点表示一个转送上的中间点表示一个转送泵站，因此对中间点运出的总量与运进的总量应当相等
29、。泵站，因此对中间点运出的总量与运进的总量应当相等。而对于发点的净流出量和收点的净流入量必相等，并且就而对于发点的净流出量和收点的净流入量必相等，并且就是该运输方案的总输送量。是该运输方案的总输送量。48本讲稿第四十八页，共八十四页容量网容量网络络G=(V,E,C)中的一个流中的一个流f=fij满满足下列条件，足下列条件，称称f为为可行流。可行流。（1）容量限制条件：）容量限制条件：对对G中每条中每条边边(vi,vj)，有有 0 fij cij。（2）平衡条件：）平衡条件：对对于中于中间间点点vi，有，有（即流出量流入量）。（即流出量流入量）。对对于收点于收点vt与与发发点点vs，有，有（即从
30、（即从vs的的净输净输出量与出量与vt的的净输净输入量相等）。入量相等）。W称称为为可行流可行流f的流量。的流量。可行流可行流总总是存在的，当所有是存在的，当所有边边的流量的流量fij=0时时，就得，就得到一个可行流，它的流量到一个可行流，它的流量W=0。最大流。最大流问题问题就是在容就是在容量网量网络络中，中，寻寻找流量最大的可行流。找流量最大的可行流。49本讲稿第四十九页，共八十四页 对对于容量网于容量网络络G给给定一个可行流定一个可行流f=fij，当，当fij=cij时时，称，称边边(vi,vj)为饱为饱和和边边，当，当fij 0时时，称，称边边(vi,vj)为为非零流非零流边边。设设是
31、网是网络络G中一条中一条联结发联结发点点vs和收点和收点vt的的链链。我我们规们规定定的正方向从的正方向从vs到到vt，则链则链上的上的边边被分被分为为两两类类：一：一类类是是边边的方向与的方向与链链的正方向一致，称的正方向一致，称它它们为们为前向前向边边，上上前向上上前向边边的全体的全体记为记为+。另另一一类边类边与与链链的正方向相反，称它的正方向相反，称它们为们为后向后向边边，上后向上后向边边的全体的全体记为记为-。50本讲稿第五十页，共八十四页v1v2v3v4v5vsvt(13,7)(5,5)(9,9)(4,4)(6,6)(5,2)(5,0)(4,0)(5,5)(4,4)(9,7)(10
32、,5)图图 7.26例如，在例如，在图图7.26中，其中，其边边上的两个数字分上的两个数字分别别表示表示边边的容量的容量和流量，即和流量，即(cij,fij)。(v2,v5)为饱为饱和和边边，(vs,v1)为为非非饱饱和和边边，并且，并且(v2,v5)，(vs,v1)均均为为非零流非零流边边，(v3,v5)是零流是零流边边。51本讲稿第五十一页，共八十四页例如例如图图7.26中，在中，在联结联结vs和和vt的的链链=vs,v1,v2,v5,vt中，中，(vs,v1)，(v2,v5)，(v5,vt)为为前向前向边边，(v1,v2)为为后向后向边边。即即+=(vs,v1)，(v2,v5)，(v5,
33、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.2652本讲稿第五十二页，共八十四页设设f是网是网络络G上的一个可行流，上的一个可行流，是从是从vs到到vt的一条的一条链链，若若对对上的任意一条上的任意一条边边(vi,vj)有有若若(vi,vj)+，则则0 fijcij，即，即+中每一中每一边边是非是非饱饱和和边边。若若(vi,vj)-，则则0fij cij，即，即-中每一中每一边边是非零流是非零流边边。则则称称是一条是一条增广增广链链。53本讲稿第五十
34、三页，共八十四页例如例如图图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)(4,4)(9,7)(10,5)图图 7.2654本讲稿第五十四页，共八十四页对对于于给给定的网定的网络络G=(V,E,C)，设设S,TV V，并且，并且ST=V V，ST=，vs S，vt T
35、，以，以S中点中点为为始点，以始点，以T中点中点为终为终点的点的边边的的集合，称集合，称为为G的割集，的割集，记为记为(S,T)。割集。割集(S,T)中所有中所有边边的容量之和称的容量之和称为为割集割集(S,T)的容量，的容量，记记为为C(S,T)，即，即55本讲稿第五十五页，共八十四页例如例如图图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(
36、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.2656本讲稿第五十六页，共八十四页 如果从网如果从网络络G中去掉割集中去掉割集(S,T)中的中的边边，从，从vs就就没有路可以到达没有路可以到达vt。对对于网于网络络G，它有，它有许许多割集，我多割集，我们们可以找到容量最小割集。而网可以找到容量最小割集。而网络络G的最大流量一定的最大流量一定不会超不会超过过容量最小割集的容量，称网容量最小割集的容量，称网络络G中容量最小中容量最小的割集的割集为为G的最小割集。如
37、果把网的最小割集。如果把网络络G看成各种粗看成各种粗细细不同的管道网，而最小割集就相当于管道网中最不同的管道网，而最小割集就相当于管道网中最细细管管道部分的道部分的总总和。和。二、最大流最小割集定理二、最大流最小割集定理 由上面例子可知，如果找到网由上面例子可知，如果找到网络络G的一个可行的一个可行流，其流量等于网流，其流量等于网络络G的最小割集容量，的最小割集容量，则该则该可行可行流一定是最大流。下面最大流最小割集定理就是要流一定是最大流。下面最大流最小割集定理就是要说说明明这这一点。一点。57本讲稿第五十七页，共八十四页定理定理1可行流可行流f*是最大流当且是最大流当且仅仅当当G中不存在关
38、于中不存在关于f*的增广的增广链链。推推论论在任意一个容量网在任意一个容量网络络中，最大流的流量等于最小中，最大流的流量等于最小割集的容量。割集的容量。三、求最大流的标号算法三、求最大流的标号算法由上面定理由上面定理1可知可行流可知可行流f是否是最大流，关是否是最大流，关键键看网看网络络G中是否存在关于可行流中是否存在关于可行流f的增广的增广链链，定理，定理1的的证证明明过过程程为为我我们们提供了提供了寻寻找增广找增广链链的方法及改的方法及改进进可行流可行流f的方的方法。如果在网法。如果在网络络G中存在关于可行流中存在关于可行流f的增广的增广链链（从（从vs到到vt），），则则可按定理可按定理
39、1证证明中所明中所给给的方法修改可行流的方法修改可行流f，得到一个新的可行流，得到一个新的可行流f，而，而f 的流量大于的流量大于f的流量。的流量。如果在如果在G中不存在关于可行流中不存在关于可行流f的增广的增广链链，则则可行流可行流f就就是最大流。是最大流。寻寻找关于可行流找关于可行流f的增广的增广链链可按下面介可按下面介绍绍的的标标号法来号法来实现实现。58本讲稿第五十八页，共八十四页求网求网络络G的最大流的的最大流的标标号法分号法分为为两步，第两步，第1步是步是标标号号过过程，通程，通过标过标号号寻寻找增广找增广链链；第；第2步是步是调调整整过过程，沿程，沿增广增广链链个性可行流个性可行
40、流f的流量。的流量。设设f是网是网络络G上的可行流（初始可行流可取零流上的可行流（初始可行流可取零流f=fij=0）。）。1标标号号过过程程（1）首先）首先给发给发点点vs标标号号(0,+)。（2）选择选择一个已一个已标标号的号的顶顶点点vi，对对所有与所有与vi相相邻邻而而没有没有标标号的号的顶顶点点vj按下列按下列规则处规则处理。理。（a）若）若(vi,vj)E，并且，并且fij0，则给顶则给顶点点vj以以标标号号(i,j)，其中，其中j=mini,cij-fji。59本讲稿第五十九页，共八十四页重复重复过过程（程（2），可能出），可能出现现两种两种结结果，其一是果，其一是终终点点vt得到
41、得到标标号，号，说说明存在一条增广明存在一条增广链链，则转则转到到调调整整过过程，其程，其二是二是终终点点vt不能不能获获得得标标号，号，说说明不存在增广明不存在增广链链，这时这时可可行流行流f即即为为最大流。最大流。2调调整整过过程程首先按首先按终终点点vt及其它及其它顶顶点的第一个点的第一个标标号，用反向追号，用反向追踪法在网踪法在网络络中找出增广中找出增广链链。例如。例如设终设终点点vt的第一个的第一个标标号号为为k，则则(vk,vt)是增广是增广链链上的上的边边，然后根据，然后根据vk的第一的第一个个标标号，找到下一个号，找到下一个顶顶点，即若点，即若vk的第一个的第一个标标号号为为j
42、，则则(vj,vk)（或者（或者(vk,vj)）是增广）是增广链链上的上的边边，直到用此，直到用此方法找到方法找到vs为为止。止。这时这时就得到一条从就得到一条从vs到到vt的增广的增广链链。最后按下式修改可行流。最后按下式修改可行流f。60本讲稿第六十页，共八十四页调调整整结结束后，去掉所有束后，去掉所有标标号，返回号，返回标标号号过过程重程重新新进进行行标标号号过过程。程。令令61本讲稿第六十一页，共八十四页例例10用用标标号法求下号法求下图图中从中从vs到到vt的最大流。的最大流。vsvt v4 v2 v3 v1(15,4)(9,9)(3,3)(5,1)(6,5)(7,7)(10,5)(
43、11,8)(4,0)62本讲稿第六十二页，共八十四页解（解（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,+)63本讲稿第六十三页，共八十四页 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相相邻邻的的顶顶点点v1，v2，因，因为为(vs,v1)E，并且，并且fs1=40，所以，所以v2可以获得标号可以获得标号(v1,2)
44、，其中，其中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)65本讲稿第六十五页，共八十四页 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
45、=1c23=5，所以，所以v3可以可以获获得得标标号号(v2,3)，其中，其中3 min2,c23-f23=min3,5-1=3。(vs,11)(v1,3)(v1,4)(v2,3)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,+)(vs,11)(v1,3)(v1,4)(v2,3)（5）由于与）由于与v3相相邻邻且没有且没有标标号的号的顶顶点点为为vt，并且，并且vt也与已也与已标标号的号的顶顶点点v4相相邻邻，所以，所以vt既可以以既可以以v3为为基基础获础获得得标标号号(
46、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)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)(v1,3)(v1,4)(v2,3)(v4,4)（II）调调整整过
47、过程程由于由于vt的第一个的第一个标标号号为为v4，得到，得到顶顶点点v4，由，由v4的第一的第一个个标标号号为为v1，得到，得到顶顶点点v1，由，由v1的第一个的第一个标标号号为为vs，得，得到到顶顶点点vs，由此得到关于可行流，由此得到关于可行流f的增广的增广链链=vs,v1,v4,vt，其中，其中(vs,v1),(v1,v4),(v4,vt)为为前向前向边边。68本讲稿第六十八页，共八十四页 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)(v4,4
48、)（II）调调整整过过程程由于由于t=4，所以，所以调调整量整量为为4，即增广，即增广链链上的前向上的前向边边流量加流量加4。69本讲稿第六十九页，共八十四页 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,+).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,+)(vs,7)（2）检
49、查检查与与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不能不能标标号。号。72本讲稿第七十二页，共八十四页 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）检查检
50、查与与v2相相邻邻且没有标号且没有标号的的顶顶点点v3，v4，因为因为(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。73本讲稿第七十三页，共八十四页 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)(v