图与网络分析(4课时)起讫点不同最短路最大流问题

1、运运 筹筹 学学( Operations Research )图的基本概念与模型图的基本概念与模型树与图的最小树树与图的最小树最短路问题最短路问题网络的最大流网络的最大流Page 3近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Euler1736年证明了不年证明了不可能存在这样的路线。可能存在这样的路线。Page 4图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边

2、构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的。曲直，对于反映对象之间的关系并不是重要的。若用点表示研究的对象，用边表示这些对象之间的联系，若用点表示研究的对象，用边表示这些对象之间的联系，则图则图G可以定义为点和边的集合，记作：可以定义为点和边的集合，记作：,EVG 其中其中: V点集点集 E边集边集 图图G区别于几何学中的图。这里只关心图中有多少个点以区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。及哪些点之间有连线。Page 5(v1)赵赵

3、(v2)钱钱孙孙(v3) 李李(v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来例如：在一个人群中，对相互认识这个关系我们可以用图来表示。表示。Page 6定义定义: 图中的点用图中的点用v表示，边用表示，边用e表示。对每条边可用它所连表示。对每条边可用它所连接的点表示，记作：接的点表示，记作：e1=v1,v1; e2=v1,v2; v3e7e

4、4e8e5e6e1e2e3v1v2v4v5 端点端点,关联边关联边,相邻相邻若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。若点。若点vi、vj与同一条边关与同一条边关联，称点联，称点vi和和vj相邻；若边相邻；若边ei和和ej具具有公共的端点，称边有公共的端点，称边ei和和ej相邻相邻。Page 7 环环, 多重边多重边, 简单图简单图如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如右图中边。如右图中边e1为环。如果两个点为环。如果两个点之间多于一条，称为之间多于一条，称为

5、多重边多重边，如右图，如右图中的中的e4和和e5，对无环、无多重边的图，对无环、无多重边的图称作称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5Page 8 次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为相关联的边的数目称为点点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)。右图中右图中d(v1),d(v3)=5,d(v5)=1。次。次为奇数的点称作为奇数的点称作奇点奇点，次为偶数的，次为偶数的点称作点称作偶点偶点，次为，次为1的点称为的点称为悬挂点悬挂点，次为次为0的点称作的点称作孤立点孤立点。v3e7e4e8e5e

6、6e1e2e3v1v2v4v5图的次图的次: 一个图的次等于各点的次之和。一个图的次等于各点的次之和。Page 9 链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其图中某些点和边的交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意vi,t-1和和vit均相邻称为均相邻称为链链。用。用 表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5,110kkvevev 起点与终点重合的链称作起点与终点重合的链称作圈圈。如。如果每一对顶点之间至少存在一条果每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则，否则称图不连通。称图不连通。Page 1

7、0 子图，部分图子图，部分图(支撑子图支撑子图)图图G1=V1、E1和图和图G2=V2，E2如果有如果有 称称G1是是G2的一个的一个子图子图。若有若有 ，则称，则称G1是是G2的一的一个个部分图部分图(支撑子图支撑子图)。2121EEVV 和和2121EEVV ，v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）图）Page 11 网络（赋权图）网络（赋权图）设图设图G（V，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标wij，wij称为边称为边(vi,vj)

8、的的权权,赋予权的图赋予权的图G称为网络称为网络(或或赋权图）赋权图）。权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等。等等。端点无序的赋权图称为端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有有向网络。向网络。910201571419256Page 12 出次与入次出次与入次 有向图中，以有向图中，以vi为始点的边数称为点为始点的边数称为点vi的的出次出次，用，用d+(vi)表表示；以示；以vi为终点的边数称为点为终点的边数称为点vi 的的入次入次，用表示，用表示d-(vi) ；vi 点点的出次和入次之和就是该点的次。的出次和入

9、次之和就是该点的次。 有向图中，所有顶点的入次之和等于所有顶点的出次之有向图中，所有顶点的入次之和等于所有顶点的出次之和。和。Page 13例例6.1 有甲有甲,乙乙,丙丙,丁丁,戊戊,己己6名运动员报名参加名运动员报名参加A,B,C,D,E,F 6个项目的比赛。下表中打个项目的比赛。下表中打的是各运动员报告参加的比赛项的是各运动员报告参加的比赛项目。问目。问6个项目的比赛顺序应如何安排，做到每名运动员都个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。不连续地参加两项比赛。ABCDEF甲甲乙乙丙丙丁丁戊戊己己Page 14解：用图来建模。把比赛项目作为研究对象，用点表示。如解

10、：用图来建模。把比赛项目作为研究对象，用点表示。如果果2个项目有同一名运动员参加，在代表这两个项目的点之个项目有同一名运动员参加，在代表这两个项目的点之间连一条线，可得下图。间连一条线，可得下图。ABCDEF在图中找到一个点序在图中找到一个点序列，使得依次排列的列，使得依次排列的两点不相邻，即能满两点不相邻，即能满足要求。如：足要求。如：1) A,C,B,F,E,D2) D,E,F,B,C,APage 15一个班级的学生共计选修一个班级的学生共计选修A、B、C、D、E、F六门六门课程，其中一部分人同时选修课程，其中一部分人同时选修D、C、A，一部分人同时，一部分人同时选修选修B、C、F，一部分

11、人同时选修，一部分人同时选修B、E，还有一部分人，还有一部分人同时选修同时选修A、B，期终考试要求每天考一门课，六天内考，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。试设计一个考试日程表。Page 16以每门课程为一个顶点，共同被选修的课程之间用边相以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试，因此，作图的补图，问题是邻顶点对应课程允许连续考试，因此，

12、作图的补图，问题是在图中寻找一条哈密顿道路，如在图中寻找一条哈密顿道路，如，就，就是一个符合要求的考试课程表。是一个符合要求的考试课程表。Page 17Page 18Page 19定理定理1 任何图中，顶点次数之和等于所有边数的任何图中，顶点次数之和等于所有边数的2倍。倍。定理定理2 任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的均被计算了两次，所以顶点次数的总和等于边数的2倍。倍。证明：设证明：设V1和和V2分别

13、为图分别为图G中奇点与偶点的集合。由定理中奇点与偶点的集合。由定理1可得：可得：mvdvdvdVvVvVv2)()()(21 2m为偶数，且偶点的次之和为偶数，且偶点的次之和 也为偶数，所以也为偶数，所以 必为偶必为偶数，即奇数点的个数必为偶数。数，即奇数点的个数必为偶数。 2)(Vvvd 1)(VvvdPage 20图的矩阵描述：图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：也根据所关心的问

14、题不同而有：邻接矩阵、关联矩阵、权矩阵等。邻接矩阵、关联矩阵、权矩阵等。1. 邻接矩阵邻接矩阵对于图对于图G=（V，E），），| V |=n， | E |=m，有，有n n阶方阶方矩阵矩阵A=(aij) n n，其中其中 其它其它之间有关联边时之间有关联边时与与当且仅档当且仅档0vv1jiijaPage 21v5v1v2v3v4v64332256437 010101101001010111101010001101111010 65432166654321 vvvvvvAvvvvvv例例6.2 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下Page 22对于赋权图对于赋权

15、图G=(V,E), 其中边其中边 有权有权 , 构造矩阵构造矩阵B=(bij) n n 其中：其中：对于图对于图G=(V,E), | V |=n, | E |=m, 有有m n阶阶矩阵矩阵M=(mij) m n，其中其中: 其他其他的一个端点的一个端点是边是边当且仅当当且仅当的两个端点的两个端点是边是边当且仅当当且仅当0ev1ev2jijiijm),(jivvjiw EvvEvvwbjijijiji),(0),(Page 231 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

16、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 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例例6.3 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵M如下如下:M=（mij）=Page 24654321654321 030303302004020576305020007204346

17、040vvvvvvvvvvvvB v5v1v2v3v4v64332256437例例6.4 下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下:Page 25树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。域应用极为广泛。例例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。下图所示。AB CDEF GH运动员运动员Page 26例例6.3 某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程

18、师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科Page 27 树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n 个顶点的树必有个顶点的树必有n-1 条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不相邻的两个点之间

19、加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6Page 28 图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一般图G1含有多含有多个部分树，其中树枝总长最小的部分树，称为该图的最小个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2Page 29Page 30Page 31Page 32Page 33Page 34Pa

20、ge 35部分树部分树Page 36v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5Page 37破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=5Page 38v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=15Page 39避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成加边的原

21、则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618Page 40v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15Page 41Page 42Page 43Page 44Page 45Page 46Page 47Page 48Page 49Page 50Page 51Page 52Page 53Page 54Page 55Page 56Page 57Page 58Page 59Page 60Page 613749346321Min C(T)=12Mi

22、n C(T)=15254173314475答案：答案：Page 6234122323242Min C(T)=12213638534567454321Min C(T)=18Page 63如何用最短的线路将三部电话连起来？如何用最短的线路将三部电话连起来？此问题可抽象为设此问题可抽象为设ABC为等边三角形，连接三顶点的为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如然是二边之和（如ABAC）。）。ABCPage 64ABCP但若增加一个周转站（新点但若增加一个周转站（新点P），连接），连接4点的新网络

23、的最短路点的新网络的最短路线为线为PAPBPC。最短新路径之长。最短新路径之长N比原来只连三点的最比原来只连三点的最短路径短路径O要短。这样得到的网络不仅比原来节省材料，而且要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。稳定性也更好。Page 65问题描述：问题描述：就是从给定的网络图中找出一点到各点或任意两点之间就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路距离最短的一条路 .有些问题，如选址、管道铺设时的选线、设备更新、投有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短资、某些整数规划和动态规划的问题，也可以

24、归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。路的问题。因此这类问题在生产实际中得到广泛应用。Page 66求最短路有两种算法求最短路有两种算法: 狄克斯屈拉狄克斯屈拉(Dijkstra)标号算法标号算法 逐次逼近算法逐次逼近算法Page 67若序列若序列 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的最

25、短路。的最短路。v1v2v3v4v5Page 68求网络图的最短路，设图的起点是求网络图的最短路，设图的起点是vs,终点是终点是vt ,以以vi为起点为起点vj为终点的弧记为为终点的弧记为 (i, j) 距离为距离为dij：b(j) 起点起点vs到点到点vj的最短路长；的最短路长；： k(i,j)=b(i)+dij，步骤：步骤： 1. 令起点的标号；令起点的标号；b(s)0。 2. 找出所有找出所有vi已标号已标号vj未标号的弧集合未标号的弧集合 B=(i, j) 如果这样的如果这样的弧不存在或弧不存在或vt已标号则计算结束；已标号则计算结束；3. 计算集合计算集合B中弧中弧k(i，j)=b(

26、i)+dij的标号的标号4. 选一个点标号选一个点标号 在终点在终点vl处标处标号号b(l), 返回到第返回到第2步。步。 ,),( | ),(min)(Bjijiklbj Page 69例例6.5 求下图求下图v1到到v7的最短路长及最短路线的最短路长及最短路线86252353421057086225441114751071211v7已标号，计算结束。从已标号，计算结束。从v1到到v7的最短路长是的最短路长是 11,最短路线：最短路线： v1 v4 v6 v7P标号标号T标号标号Page 70从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到到该点的最短路

27、线及最短距离，因此可以将每个点标该点的最短路线及最短距离，因此可以将每个点标号，求出号，求出vs到任意点的最短路线，如果某个点到任意点的最短路线，如果某个点vj不能不能标号，说明标号，说明vs不可达不可达vj 。注：无向图最短路的求法只将上述步骤注：无向图最短路的求法只将上述步骤2将弧改成边即可。将弧改成边即可。Page 71例例6.6 求下图求下图v1到各点的最短距离及最短路线。到各点的最短距离及最短路线。4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短到该

28、点的最短距离，最短路线就是红色的链。路线就是红色的链。Page 72课堂练习：课堂练习：1. 用用Dijkstra算法求下图从算法求下图从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：6521vvvvPage 732. 求从求从v1到到v8的最短路径的最短路径237184566134105275934682Page 74237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为10

29、Page 753. 求下图中求下图中v1点到另外任意一点的最短路径点到另外任意一点的最短路径v1v2v3v4v6v5322762133Page 76v1V2V3V4 V6V5322762133024714Page 77v1V2V3V4 V6V5322762133024714Page 78算法适用条件：算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近边上权为负的，算法失效。此时可采用逐次逼近算法。算法。例例6.7 如右图所示中按如右图所示中按dijkstra算算法可得法可得P(v1)=5为从为从vsv

30、1的最短的最短路长显然是错误的，从路长显然是错误的，从vsv2v1路长只有路长只有3。v2vsv15-58Page 79最短路问题的应用：最短路问题的应用：例例6.7 电信公司准备准备在甲、乙两地沿路架设一条光缆线，电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。通图。权数表示两地间公路的长度（单位：公里）。 v1 （甲地）（甲地）1517624431065v2v7 (乙地乙地)v3v4v5v6Page 80例例6.8 设备更新问题。某公司使用一

31、台设备，在每年年初，设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备每年年

32、初的价格表年份年份12345年初价格年初价格1111121213Page 81设备维修费如下表设备维修费如下表使用年数使用年数0-11-22-33-44-5每年维修费用每年维修费用5681118解：解：将问题转化为最短路问题，如下图：用将问题转化为最短路问题，如下图：用vi表示表示“第第i年年年年初购进一台新设备初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进的设备一年年初购进的设备一直使用到第直使用到第j年年初。年年初。v1v2v3v4v5v6Page 82把所有弧的权数计算如下表，把所有弧的权数计算如下表，把权数赋到图中，再用把权数赋到图中，再用Dijkstra算法求最短

33、路。算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723Page 83 最终得到下图，可知，最终得到下图，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条： v1v3v6和和 v1v4v6 V1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)Page 84如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使

34、生产地到销售地的产品输送量最大。这就是一个网络最大流问题。这就是一个网络最大流问题。Page 85基本概念：基本概念：对网络上的每条弧对网络上的每条弧(vi,vj)都给出一个最大的通都给出一个最大的通过能力，称为该弧的过能力，称为该弧的，简记为，简记为cij。容量网络中通常规定。容量网络中通常规定一个一个(也称源点，记为也称源点，记为s)和一个和一个(也称汇点，记为也称汇点，记为t)，网络中其他点称为网络中其他点称为。st4844122679Page 862. 网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3. 流与可行流流

35、与可行流 流流是指加在网络各条弧上的实际流量，对加在弧是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上上的负载量记为的负载量记为fij。若。若fij=0，称为零流。，称为零流。满足以下条件的一组流称为满足以下条件的一组流称为可行流可行流。 容量限制条件。容量网络上所有的弧满足：容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。中间点平衡条件。),(0),(),(tsivvfvvfijji 若以若以v(f)表示网络中从表示网络中从st的流量，则有：的流量，则有： 0),(),()(tjjsvvfvvffvPage 87结论：任何网络上一定存在可行流。（零流即是结论：任

36、何网络上一定存在可行流。（零流即是可行流）可行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。值达到最大。Page 88 割与割集割与割集割是指容量网络中的发点和收点分割开，并使割是指容量网络中的发点和收点分割开，并使st的流中断的流中断的一组的一组弧的集合弧的集合。割容量是组成割集合中的各条弧的容量之。割容量是组成割集合中的各条弧的容量之和，用和，用 表示。表示。),(VVc ),(),(),(),(VVjijivvcVVc如下图中，如下图中，AA将网络上的点分割成将网络上的点分割成 两个集合。并两个

37、集合。并有有 ，称弧的集合，称弧的集合(v1,v3),(v2,v4)是一个割，且是一个割，且 的流量为的流量为18。 VV ,VtVs ,VV Page 89v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABBPage 90 设网络设网络N中一个从中一个从 s 到到 t 的流的流 f 的流量为的流量为v(f )， (V, V )为任意一个割集，则为任意一个割集，则 v(f ) = f(V, V ) f(V , V) 对网络对网络 N中任意流量中任意流量v(f )和割集和割集 (V, V )，有，有v(f ) c(V, V )证明证明 w= f(V,

38、 V ) f(V , V) f(V, V ) c(V, V ) 最大流量最大流量v (f )不大于最小割集的容量，即：不大于最小割集的容量，即：v (f ) minc(V, V ) 在网络中在网络中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即： v (f ) = c (V, V ) Page 91在网络的发点和收点之间能找到一条链，在该链上所有在网络的发点和收点之间能找到一条链，在该链上所有指向为指向为st的弧，称为前向弧，记作的弧，称为前向弧，记作+,存在存在f0，则称这样的链为，则称这样的链为增广链。增广链。例如下图中，例如下图中，sv2v1v3v4t。

39、网络网络N中的流中的流 f 是最大流当且仅当是最大流当且仅当N中不包含任何增广中不包含任何增广链链Page 92v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)Page 93求网络最大流的标号算法：求网络最大流的标号算法：由一个流开始，系统地搜寻增广链，然后在此链上增流，由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。继续这个增流过程，直至不存在增广链。(1)找出第一个可行流，（例如所有弧的流量找出第一个可行流，（例如所有弧的流量fij =0。）。）(2)用标号的方法找一条增广链用标号的方法找一条增广链 首先给发点

40、首先给发点s标号标号(),标号中的数字表示允许的最大调整量。标号中的数字表示允许的最大调整量。 选择一个点选择一个点 vi 已标号并且另一端未标号的弧沿着某条链已标号并且另一端未标号的弧沿着某条链向收点检查：向收点检查：Page 94 如果弧的起点为如果弧的起点为vi，并且有，并且有fij0，则，则vj标号标号(fji)(3) 重复第重复第(2)步，可能出现两种结局：步，可能出现两种结局： 标号过程中断，标号过程中断，t无法标号，说明网络中不存在增广链，无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，目前流量为最大流。同时可以确定最小割集，记已标号的点记已标号的点集为

41、集为V,未标号的点集合为未标号的点集合为V,(V,V)为网络的最小割。为网络的最小割。 t得到标号，反向追踪在网络中找到一条从得到标号，反向追踪在网络中找到一条从s到到t得由标号得由标号点及相应的弧连接而成的增广链。继续第点及相应的弧连接而成的增广链。继续第(4)步步Page 95 所所有有非非增增广广链链上上的的弧弧对对增增广广链链上上所所有有后后向向弧弧对对增增广广链链上上所所有有前前向向弧弧ftftff)()(4) 修改流量。设原图可行流为修改流量。设原图可行流为f，令，令得到网络上一个新的可行流得到网络上一个新的可行流f。(5) 擦除图上所有标号，重复擦除图上所有标号，重复(1)-(4

42、)步，直到图中找不到任何步，直到图中找不到任何增广链，计算结束。增广链，计算结束。Page 96例例6.10 用标号算法求下图中用标号算法求下图中st的最大流量，并找出最小割。的最大流量，并找出最小割。v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)Page 97解：解：(1) 先给先给s标号标号()v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()Page 98v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(2) 检查与检查与s点相邻的未标号的点，因点相邻的未

43、标号的点，因fs1cs1，故对，故对v1标号标号=min, cs1-fs1=1,)1( (1)Page 99v1v3v2v48(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)3( (1)Page 100v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(1)(1)(3) 检查与检查与v3点相邻的未标号的点，因点相邻的未标号的点，因f3tc3t，故对，故对vt标号

44、标号=min1, c3t-f3t= min1, 1= 1)(t (1)找到一条增广链找到一条增广链sv1v3tPage 101(4) 修改增广链上的流量，非增广链上的流量不变，得到新的修改增广链上的流量，非增广链上的流量不变，得到新的可行流。可行流。v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)()(1)(1)(1)11 sf113 f13 tfPage 102(5) 擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。v1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7

45、(5)()(1)(1)(1)Page 103(5) 擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。v1v3v2v48(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=1Page 104(6) 修改增广链上的流量，非增广链上的流量不变，得到新的修改增广链上的流量，非增广链上的流量不变，得到新的可行流。可行流。v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)

46、9(9)5(3)7(5)()(2)(2)(2)(1)(1)12 sf121 f113 f134 f14 tfPage 105v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(2)(2)(2)(1)(1)(7) 擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。Page 106v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(1)(1)(1)(7) 擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。(2)=

47、min,1=1(1)=min1,2=1(3)=min1,4=1,4321VVtvVvvvsV 最小割为最小割为Page 107例例6.9 求下图求下图st的最大流，并找出最小割的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)Page 108stv1v2v3v4v54(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)Page 109(2) 修改增广链上的流量，非增广链上的流量不变，得到新的修改增广链上的流量，非增广链上的流量不变，得到新的可行流。可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2