第6章图论与统筹方法

1、Chapter 6 图论(GT)与网络计划本章主要内容本章主要内容n图的基本概念、术语图的基本概念、术语n图的矩阵表达方式图的矩阵表达方式(相邻和关联矩阵相邻和关联矩阵)n树的概念及其特点、最小生成树的求法树的概念及其特点、最小生成树的求法n最短路问题的算法最短路问题的算法n网络流的基本概念、求最大流的方法网络流的基本概念、求最大流的方法n最小费用最大流的求法最小费用最大流的求法1.网络图及其绘制、网络计划技术网络图及其绘制、网络计划技术Chap 6-1图的基本概念图论（Graph Theory，简称GT）。图是最直观的模型。Euler (1707-1783) 在1736年发表第一篇图论方面的

2、论文，奠基了图论中的一些基本定理，解决了哥尼斯堡七桥问题 (Knigsberg Bridge Problem)BACD1847年，基尔霍夫运用图论来分析电网络 1936年，匈牙利数学“有限图与无限图的理论”发表计算机的广泛应用，图论得到进一步发展。一、图的基本概念图通常用点代表研究对象，用点与点之间的联线表示这两个对象之间的特定关系。顶点 (Vertex)表示研究对象物理实体、事物、概念、一般用 vi 表示边 (Edge)点间的连线，表示有关系一般用 eij /ej表示图 (Graph)点和边的集合一般用 G(V,E) 表示点集 V=v1,v2, vn边集E=eij /ej ev1v5v4v3

3、v2e12e34e13e2422e13e45基本名词与术语阶：顶点的个数n称为图的阶。关联：若图中的某顶点与某边相连接，则称它们彼此关联； 孤立点：图中的顶点没有任何边与之关联，就称为孤立点；悬挂点：只与一条边关联的顶点 543e22v1vvvv2e12e34e13e24e13e456v543e22v1vvvv2e12e34e13e24e13e456v环：起点和终点为同一顶点的边；简单图：一个图中既没有多重边也没有环的图；完全图：图中的任一对顶点间都有边相连的无向简单图 多重边（平行边）：图中某两个顶点之间多于一条边； 多重图：具有多重边的图； 相邻：若两个顶点之间至少存在一条边，则称此两顶点

4、相邻；若两条边至少有一个共同的顶点，则称两条边相邻； n顶点的次数（度）：与某个顶点相关联的边的数目，记为dG(vi)；（孤立点为0次）；顶点分为奇点（次数为奇数）和偶点。悬挂点：次为1的顶点；悬挂点的关联边称为悬挂边。 v1v5v4v3v2e12e34e13e24e22e13e45顶点的次的性质：定理1：图G=（V,E）中，所有点的次之和是边数的两倍。 定理2：任一个图中，若存在奇点，奇点的个数为偶数。 二、有向图与无向图如果一个图的各边都未标明方向，这种图就称为无向图（有时简称为图）；如果一个图的各边都标明方向，这种图就称为有向图；为了区别无向图，把有向图中顶点间的联线称为弧（Arc），弧

5、的集合表示为A，有向图就可表示为：G=（V，A）。弧用 aij表示，i, j 的顺序是不能颠倒的，图中弧的方向用箭头标识。三、子图设有图G1=(V1，E1)和G2=(V2，E2)，若V2 V1，E2 E1，就称G2是G1的子图，记作 G2 G1；v1v5v4v3v2e12e34e13e24e22e13e45v1v4v3v2e12e34e13e24e1343v1v5vvv2e12e34e13e24e13e45其中而当V1= V2， E2 E1 ，就称G2是G1的生成子图（支撑子图）；四、 链、路、圈和回路在一个图中，以顶点起到顶点终的顶点和边的非空有限交替序列称为链。当链（圈）中的所有边均不相同

6、时，称其为简单链（圈）；v1v5v4v3v2e12e34e13e24e22e13e45如果某条链是闭的，即其起点和终点是合为一点时，则称其为圈。当链（圈）中的所有顶点均不相同时（对于圈来说，除第一个和最后一个顶点相同外），称其为初等链（圈）。初等链又称为路，路vi,，vj，记为(vi,vj)。初等圈又称为回路。 五、连通图与分离图五、连通图与分离图在图在图G中，若任何两点之间，至少存在一条链，中，若任何两点之间，至少存在一条链，则称则称G是连通图，否则称为分离图是连通图，否则称为分离图(或不连通图或不连通图)。 1625734e3e1e5e2e4e6e7不连通图的最大连通子图称为不连通图的最大

7、连通子图称为该图的一个连通部分或分图。该图的一个连通部分或分图。如果去掉图中某条边后，图的如果去掉图中某条边后，图的分图数增加，这样的边就称为割分图数增加，这样的边就称为割边。边。如果去掉图中一个点及与该点如果去掉图中一个点及与该点相连的边后，图的分图数增加，相连的边后，图的分图数增加，这样的点就称为割点这样的点就称为割点性质：如果连通图中包含有回性质：如果连通图中包含有回路，则移去回路中的任一边后，路，则移去回路中的任一边后，余下的子图仍是连通的。余下的子图仍是连通的。 一个图若由一个图若由k个分图组成，则称个分图组成，则称其为其为k部图。部图。六、图的同构设图G1=（V1，E1）和G2=（

8、V2，E2），是两个无向图，假如V1和V2、E1和E2中元素一一对应，并且一个图形中的两个顶点间的边对应于另一图形对应顶点间边，则称这两个图形是同构的，记作：G1 G2。即如果两图的点数相同、线数相同，且点对之间的联结相同，就称此两图同构。ABCDBACD七、加权图需要给定顶点和边的强弱程度，这时就需要给图需要给定顶点和边的强弱程度，这时就需要给图的边赋以某一数值（称之为线权），给顶点赋以某一的边赋以某一数值（称之为线权），给顶点赋以某一数值（称为点权）。数值（称为点权）。若仅给图的边或弧赋权，这种就称为边权图（弧若仅给图的边或弧赋权，这种就称为边权图（弧权图）；若仅给点赋权，就称之为点权图；

9、点权和线权图）；若仅给点赋权，就称之为点权图；点权和线权均有的图称为混合图。权均有的图称为混合图。赋有权的图称为加权图，或称为网络赋有权的图称为加权图，或称为网络(图图)。 点权化为弧权的方法：点权化为弧权的方法：将有点权的顶点将有点权的顶点vi分裂成起点分裂成起点vi1和终点和终点vi2将点权加给虚拟弧（将点权加给虚拟弧（vi1，vi2），），所有射入所有射入vi的弧均指向的弧均指向vi1，所有由，所有由vi射出射出的弧均从的弧均从vi2射出。射出。 22八、图的矩阵表示1. 权矩阵设给定图设给定图G（V，E），）， Vn，其边，其边(vi, vj)有权有权wij，用权矩阵用，用权矩阵用A表

10、示时，有表示时，有空格，其它Evvajiijij),( ,2. 邻接矩阵表示法邻接矩阵表示法邻接矩阵表示图中各点间相邻关系的一种矩邻接矩阵表示图中各点间相邻关系的一种矩阵表示方法。其行与列都与图的顶点对应。阵表示方法。其行与列都与图的顶点对应。设给定图设给定图G（V，E），），Vn，用邻接，用邻接矩阵矩阵B表示时，有：表示时，有：对于无向图：对于无向图：bij =连接顶点连接顶点vi和和vj的边数；的边数；对于有向图：对于有向图：bij =以顶点以顶点vi为起点，为起点，vj为终点为终点的弧数。的弧数。 结论：1.其主对角线上的元素为0（无环），若为简单图，则该矩阵的元素全为0或1。2.对于无

11、向图的相邻矩阵，其每一行或每一列元素值之和，等于与相应顶点相关联的边数；3.对于有向图，其每一行元素值之和等于该顶点射出的弧数，每一列元素值之和等于射入该顶点的弧数。v1v2v4v3v1v2v3v40 1 1 11 0 1 11 1 0 11 1 1 0 v v vv 4321v1v2v3v40 1 1 01 0 0 00 0 0 10 1 1 0 v v vv 4321v1v2v3v43.关联矩阵表示法关联矩阵表示图中的点与边（弧）的关联关系，其行对应于图中的顶点，列对应于图中的边(弧)。 设给定图G（V，E），Vn， Em，用关联矩阵Cnm表示时，有：相关联与边若顶点ji, 10,ijij

12、c若顶点 与边 不关联无向图1,ijjic若 弧 自 顶 点 射 出有 向 图 ij射向顶点若弧, 1不关联与顶点若弧ij, 0i2,vje 是 顶 点处 的 环v4v2v3v1e1e2e3e4e6e5v1v2v3v4a1a2a3a4a5a6 1 0 1 0 1 00 1 1 1 0 01 0 0 1 0 10 1 0 0 1 1 e6 e5 e4 e3 e2 e1 v1v2v3v4 1- 1 1 0 0 01 1- 0 1- 0 00 0 1- 0 1 1-0 0 0 1 1- 1 a6 a5 a4 a3 a2 a1 v1v2v3v4关联矩阵性质：1）由于每条边（弧）均有两个顶点，矩阵每列都

13、有两个非0元素；2）各行非0元素的个数为与该顶点相关联的边数。 作业：P1736.2(b)、6.3(1)、6.4(1)Chap 6-2 欧拉图和哈密尔顿回路 一、欧拉图一、欧拉图 在连通无向图在连通无向图G中，若存在经过每一条边恰好一中，若存在经过每一条边恰好一次的一个圈或一条链，就称此圈或链为欧拉圈或欧次的一个圈或一条链，就称此圈或链为欧拉圈或欧拉链。拉链。若图若图G仅含一条欧拉圈，则称之为欧拉图。仅含一条欧拉圈，则称之为欧拉图。定理定理1：连通无向图：连通无向图G为欧拉图的充要条件为为欧拉图的充要条件为G中无奇次点。中无奇次点。定理定理2：连通无向图：连通无向图G为欧拉链的充要条件为它为欧

14、拉链的充要条件为它恰含有两个奇次顶点。恰含有两个奇次顶点。定理定理3：连通有向图：连通有向图G为欧拉图的充要条件为为欧拉图的充要条件为G中每个顶点的出次等于其入次。中每个顶点的出次等于其入次。定理：连通有向图定理：连通有向图G为欧拉链的充要条件为有为欧拉链的充要条件为有其中两个顶点，一个出次比入次多其中两个顶点，一个出次比入次多1，一个出次比入，一个出次比入次少次少1，其余顶点的出次和入次相等。，其余顶点的出次和入次相等。因此，欧拉图、欧拉链因此，欧拉图、欧拉链 “一笔画出一笔画出”图图ABCDBACD二、哈密尔顿回路二、哈密尔顿回路定义：在一个图中，如果有一条链（圈）经定义：在一个图中，如果

15、有一条链（圈）经过每个顶点恰好一次，那么这条链（圈）就称过每个顶点恰好一次，那么这条链（圈）就称为哈密尔顿链（圈）。为哈密尔顿链（圈）。哈密尔顿回路是指经过每个顶点恰好一次，哈密尔顿回路是指经过每个顶点恰好一次，而欧拉图是指经过每条边恰好一次的路。而欧拉图是指经过每条边恰好一次的路。三、中国邮路问题三、中国邮路问题问题的提出：某邮递员从邮局出发，走过每条街道至问题的提出：某邮递员从邮局出发，走过每条街道至少一次去投递邮件，最后他回到邮局，他应走什么样的少一次去投递邮件，最后他回到邮局，他应走什么样的路线才能使总路程最短？路线才能使总路程最短？ 求解方法：求解方法：给邮路赋权给邮路赋权(标路长标

16、路长)，形成一连通赋权图，形成一连通赋权图G。 G可分两种情形：可分两种情形：若若G无奇次顶点，则无奇次顶点，则G就是欧拉图，因每边仅过一次，就是欧拉图，因每边仅过一次，故总权肯定最小；故总权肯定最小；若若G有奇次顶点，则不是欧拉图有奇次顶点，则不是欧拉图然而题设要求过每边最少一次，但未限制只有一次，然而题设要求过每边最少一次，但未限制只有一次，故总可以在这些奇次顶点上添加一些与原图的边相重复故总可以在这些奇次顶点上添加一些与原图的边相重复的边，使这些奇次顶点成为偶次顶点，从而得到一个将的边，使这些奇次顶点成为偶次顶点，从而得到一个将重复边看作是另一新边的欧拉图。重复边看作是另一新边的欧拉图。

17、定理定理5 ：使：使G成为总权最小的欧拉图的充要条件是：成为总权最小的欧拉图的充要条件是：a.在奇次顶点的图在奇次顶点的图G中，通过加重复边的方法使图中，通过加重复边的方法使图中不再含奇次顶点，但原图的每条边至多只能加一条中不再含奇次顶点，但原图的每条边至多只能加一条重复边；重复边；b.在在G的每个回路上，重复边之总权不超过该回路的每个回路上，重复边之总权不超过该回路非重复边之总权。非重复边之总权。 求总权最小的欧拉图步骤：求总权最小的欧拉图步骤：1.找奇次顶点；找奇次顶点；2.加重复边；加重复边；3.按定理按定理5判断是否最优，并调整判断是否最优，并调整举例：举例：P153例例1、2例例1：

18、四、旅行售货员问题四、旅行售货员问题(属于哈密尔顿回路属于哈密尔顿回路)问题的提出：一个旅行售货员想去某些城市售货，问题的提出：一个旅行售货员想去某些城市售货，然后回到他的出发点。各城市之间的路程是已知的，然后回到他的出发点。各城市之间的路程是已知的，问他应如何安排他的旅行路线，才能使他经过每个城问他应如何安排他的旅行路线，才能使他经过每个城市恰好一次，且总路程最短？市恰好一次，且总路程最短？用图论的术语来讲就是，在一个加权图中，找出一用图论的术语来讲就是，在一个加权图中，找出一条总权最小的哈密尔顿回路。条总权最小的哈密尔顿回路。 近似算法：近似算法：首先，任取一条哈密尔顿回路，首先，任取一条

19、哈密尔顿回路，设它经过的顶点序列为：设它经过的顶点序列为：v1,v2,vi, ,vjvn若对某一对顶点若对某一对顶点vi,vj，相应边权，相应边权存在以下关系：存在以下关系： w(vi,vj)+w(vi+1,vj+1)w(vi,vi+1)+w(vj,vj+1)则用边则用边(vi,vj)和边和边(vi+1,vj+1)替换边替换边(vi,vi+1)和边和边(vj,vj+1)，可得另一条哈密，可得另一条哈密尔顿回路，其权更少。尔顿回路，其权更少。用这种方法对哈密尔顿回路进行用这种方法对哈密尔顿回路进行若干次改进，即可获得较好的哈密尔若干次改进，即可获得较好的哈密尔顿回路。顿回路。作业：P1746.5

20、v1viVi+1vj+1vjChap 6-3 最小树一、树的定义一、树的定义树：无圈的无向连通图，用树：无圈的无向连通图，用T表示。表示。 24351v2v1v3v4v5v6v7v8树的性质：树的性质：1. 如树如树T的顶点数大于的顶点数大于2，则该，则该树至少有树至少有2个悬挂点。个悬挂点。2. 树树T的顶点树为的顶点树为n，则它的边数，则它的边数m=n-1。3. 树中任意两顶点间必有一条且仅有一条树中任意两顶点间必有一条且仅有一条链（通路）。链（通路）。4.在树中不相邻的任意两顶点间添一条边，在树中不相邻的任意两顶点间添一条边，必构成一个圈（或一条回路）。必构成一个圈（或一条回路）。5.树

21、中任去一条边，则图由连通变为分离。树中任去一条边，则图由连通变为分离。因此，树中每条边均是割边。因此，树中每条边均是割边。树的等价命题：树的等价命题：1.T连通且无回路；连通且无回路；2.T的每一对顶点间有唯一的一条通路；的每一对顶点间有唯一的一条通路；3.T连通且有连通且有n-1条边；条边；4.T有有n-1条边且无回路；条边且无回路；5.T没有回路，但在没有回路，但在T中任两个不相邻的顶中任两个不相邻的顶点间添上一条边恰好形成一条回路；点间添上一条边恰好形成一条回路；6.T连通，但去掉任一条边后就不连通，连通，但去掉任一条边后就不连通，即即T为连通且边数最小的图。为连通且边数最小的图。243

22、51二、支撑树二、支撑树/最小树最小树支撑树（生成树）：若图支撑树（生成树）：若图T是图是图G的一个生成子的一个生成子图，且图，且T又是一棵树，则称又是一棵树，则称T是图是图G的一个生成树的一个生成树（支撑树）。（支撑树）。最小树：赋权图最小树：赋权图G的所有支撑树中，边权之和的所有支撑树中，边权之和最小的一棵生成树，记为最小的一棵生成树，记为T*。三、最小树的求法三、最小树的求法1.破圈法（丢边法）破圈法（丢边法）作法：在连通无向图中，任取一圈，将圈中权作法：在连通无向图中，任取一圈，将圈中权最大的一条边去掉，在余下的圈中重复这一步骤，最大的一条边去掉，在余下的圈中重复这一步骤，直至不含圈为

23、止，这样就得到了最小树。直至不含圈为止，这样就得到了最小树。举例：举例：v1v4v6v3v5v2101081177169.51712919.5丢边法最小树长41.52.加边法（避圈法）加边法（避圈法）作法：从所有边中找出权最小边，并把它纳入作法：从所有边中找出权最小边，并把它纳入树；在余下的未选边中，再选出一条权最小且与已树；在余下的未选边中，再选出一条权最小且与已选入树中的边不构成圈的边，将其纳入树中；如此选入树中的边不构成圈的边，将其纳入树中；如此重复，直至树中含有重复，直至树中含有n-1条边为止，就得到了最小树。条边为止，就得到了最小树。举例：举例：v1v4v6v3v5v21010811

24、77169.51712919.5比较一下，上面两种方法求出的最小树，可得最小比较一下，上面两种方法求出的最小树，可得最小树非唯一解树非唯一解即使用同一种方法求出的最小树，由于图含有相同即使用同一种方法求出的最小树，由于图含有相同的最大边或最小边，可得出不同的最优解的最大边或最小边，可得出不同的最优解但最小树的长度是相等的。但最小树的长度是相等的。v1v4v6v3v5v2101081177169.51712919.5v1v4v6v3v5v2108779.5加边法总树长41.5作业：P1746.7(a)、(c)Chap 6-4 最短路问题最短路问题是重要的最优化方法之一，它不仅可以直接最短路问题是

25、重要的最优化方法之一，它不仅可以直接应用于解决生产实际中的许多问题，例如管道铺设、线路应用于解决生产实际中的许多问题，例如管道铺设、线路安排、厂区布局、设备更新等，而且经常被作为一个基本安排、厂区布局、设备更新等，而且经常被作为一个基本工具，用于解决其它的优化问题。工具，用于解决其它的优化问题。在动态规划中，曾叙述过最在动态规划中，曾叙述过最短路问题。短路问题。以该例可引出一般最短路问以该例可引出一般最短路问题，给定一个有向赋权图题，给定一个有向赋权图G(V,A)，对于每一条弧，对于每一条弧(vi,vj)的的权为权为wij，给定两个顶点，给定两个顶点vs和和vt，设设P是是G中从中从vs到到v

26、t的一条路，的一条路，路路P的权为的权为P中所有弧的权之和，中所有弧的权之和，最短路问题就是要在所有从最短路问题就是要在所有从vs到到vt的路，求一条权最小的路。的路，求一条权最小的路。2s5t63410749188152202302s5t6348一、某一点到另一点间的最短路1.权为非负（wij0）算法-Dijkstra算法（双标号法） 问题的提出：设赋权图G=（V，A），其中的边eij=（vi,vj）或弧aij=(vi,vj)的权为wij (wij0),现求起点vs到终点vt的最短路。 2.思路：根据最短路的性质设P是起点vs到终点vt的最短路,则vs沿P到P上任意中间点vk的路，也是起点v

27、s到该中间点vk的最短路因此可以先求起点vs到中间点的最短路，再逐步扩展到终点，求出起点vs到终点vt的最短路。 所有点对间的最短路短路某一点到另一点间的最最短路3.方法：1) 将图中的顶点分成两个集合：S=已求出到起点的最短路的点（已标号点），开始时S中仅含有vs点；T=尚未求出到起点最短路的点（未标号点），随着迭代工作的进行，S中的点逐渐增加，若终点已在S中，则计算结束，求出了起点到终点的最短路。2) 为便于计算，对已求出到起点最短路的点vk赋予标号（d(vs,vk),i ），其中i为vk到起点vs最短路上的前一点， d(vs,vk)为起点vs到vk的最短路长。 以上方法又称为双标号法。4

28、.计算步骤.起点vs赋予标号（0， ），并将vs置于集合S中，其它点置于集合T中。.对图G中起点在集合S中，而终点在集合T中的边边eij或弧或弧aij, 进行如下计算：(,)min(,)min,sjsiijijijd v vd v vwvS vT将vj标号（d(vs,vk),i ）,并将vk置于S中。 重复步骤2，直到vt被标号，计算结束。利用vt的第一个标号得到起点vs到终点vt的最短路长，利用vt的第二个标号进行反向追踪，得到起点vs到终点vt的最短路路径P。 s举例：求下图中s点到t点的最短路。 w,w,wmin),(mins4s3s2ssds2s5t634107491881522023

29、02s5t6348解：给s点标号(0,s),则Ss，T= 2,3,4,5,6,t，d(vs,vs)=0(0, )考虑顶点在S集终点在T集的边（即考虑与s点相邻的顶点2,3,4）计算 TjSiwisdksdijji,min),(min),(给点4标号（8,s)(8,s)88 15, min10,min0 Ss ,4，T = 2,3,5,6,t。s2s5t63410749188152202302s5t6348(8,s)考虑与s,4点相邻的顶点2，3，6。继续计算 ,min),(min),(TjSiwisdksdijji给点2标号(10,s)(10,s)w,wmin) 4 ,(,w,wmin),(m

30、in 4643s3s2svdssd 01 7 4,min8 , min10,15min0Ss , 2, 4，T = 3,5,6,t。(0, )s2s5t63410749188152202302s5t6348(0,s)(8,s)(10,s)考虑与s,2,4点相邻的顶点3,5,6计算TjSiwisdksdijji,min),(min),(给点5标号(11,2)(11,2)w,wmin)2 ,(,w,wmin)4 ,(,),(min232546433sdsdwssds 111,8min10 , 7 4,min15,80 minSs , 2, 4 ,5，T= 3,6,t。2s5t63410749188

31、152202302s5t6348(0,s)(8,s)(10,s)(11,2)考虑与s,2,4,5点相邻的顶点3,6,t计算 ,min),(min),(TjSiwisdksdijji给点3标号(4,12,)(12,4)w,w,min) 5 ,(,w)2 ,( ,w,wmin)4 ,(,),(min565t532346433wsdsdsdwssds 21min9,20,211 , 810 , 7 4,min15,8 min Ss , 2, 3, 4 ,5，T = 6,t。2s5t63410749188152202302s5t6348(0,s)(8,s)(10,s)(11,2)(12,4)考虑与s,

32、2,3,4,5点相邻的顶点6,t计算 ,min),(min),(TjSiwisdksdijji给点6标号(13,5)(13,5) w,wmin) 5 ,( d,w) 3 ,(,w) 4 ,(min565t3646ssdsd 31min20,211 , 212 , 78 minSs , 2, 3, 4 ,5 , 6， T = t。2s5t63410749188152202302s5t6348(0,s)(8,s)(10,s)(11,2)(12,4)(13,5)考虑与s,2,3,4,5,6点相邻的顶点t计算TtSiwisdtsditti,min),(min),(给点t标号(31,5)(31,5)w)

33、6 ,(,w)5 ,(min 6t5tsdsds 313013 , 2011 minSs , 2, 3, 4 ,5 , 6,t。标号结束2s5t63410749188152202302s5t6348(0,s)(8,s)(10,s)(11,2)(12,4)(13,5)(31,5)最短路径为：s25t 。最短路长=31对应的最短路径：S256 S25S4 S43 S2 P157 例6二、所有点对间的最短路作法：矩阵算法（Flody）计算步骤：1. 写出图的初始路长矩阵（相邻矩阵）D0=（dij）其中：dij为vi到vj直达距离（即弧长wij）,若不存在弧，则dij=M(足够大正数)； ，否 则ii

34、Miid0)(到点若不允许或不考虑点此外，2. 写出中间点矩阵C0=(cij) ,其元素全为i，表示i是线路vivj的中间点（vj的前一点）的下标。 3.考查是否应以顶点v1作为vi-vj(i,j= 2, 3 , ,n)的中间点，即将dij与（di1+d1j）比较：n若dij（di1+d1j），则说明vivj之间应经过中间点v1，即在下一个相邻矩阵中用（di1+d1j）替代元素dij,并同时修改中间点矩阵的相应元素，即将C0中的cij换为1。n若dij（di1+d1j），则不需要经过顶点v1，即不修改。 4.考查并修改完（若需要）完D0和C0中的所有元素后，即得到下一个相邻矩阵D1，C1，开始

35、下一步考查（是否应经过v2点）。比较dij与（di2+d2j）(i,j= 1, 3 , ,n)在关系？若dij（di2+d2j），则说明vivj之间应经过中间点v2，即在下一个相邻矩阵中用（di2+d2j）替代元素dij,并同时修改中间点矩阵的相应元素，即将C1中的cij换为2。若dij（di1+d1j），则不需要经过顶点v2，即不修改。按v3、v4的顺序进行考查、比较、修改当考查完所有中间点直到vn点后，即求出了任意点对间的最短路的路长矩阵和路径矩阵。对n个顶点的图，经n次迭代可求出最短路及其路径。第k次迭代公式：dij(k)=mindij(k-1),(dik+dkj)其中, i,j=1,2

36、,n。当i=k或j=k时，dij(k)=dij(k-1) ?求最短路的路径：假设寻找vi-vj的最短路径，先在Cn中找出cij，若ciji,由其最短路径为vi-vj；若cij i,设cijk,则其最短路径含vi-vk-vj 然后在cn中找出cik和ckj 若ciki，则说明vi-vk之间无其它中间点，若ckjk，则说明vk-vj之间无其它中间点；否则可如上方法确定一中间点，如此继续，直至找出vi-vj间所有中间点为止，即可得一完整的最短路径。举例：求下图各点对间的最短路长和路径。12347210934 M M M 109 M 4 M 3 M M M M 2 7 M D v v v v 0432

37、1v1v2v3v4 4 4 4 4 3 3 3 3 2 2 2 2 1 1 1 1 C v v v v 04321v1v2v3v4比较：dij?（di1+d1j）d42d41+d12=17d43d41+d13=12改为1 M 12 17 109 M 4 M 3 M M M M 2 7 M D v v v v 14321v1v2v3v4 4 1 1 4 3 3 3 3 2 2 2 2 1 1 1 1 C v v v v 14321v1v2v3v4比较：dij?（di2+d2j） 20 12 17 107 M 4 M 3 M M M 10 2 7 M D v v v v 24321v1v2v3v4

38、 2 1 1 4 2 3 3 3 2 2 2 2 2 1 1 1 C v v v v 24321v1v2v3v4比较：dij?（di3+d3j） 19 12 16 107 M 4 M 3 M M M 9 2 6 M D v v v v 34321v1v2v3v4 3 1 3 4 2 3 3 3 2 2 2 2 3 1 3 1 C v v v v 34321v1v2v3v4比较：dij?（di4+d4j） 19 12 16 107 19 4 17 3 15 19 13 9 2 6 19 D v v v v 44321v1v2v3v4 3 1 3 4 2 4 3 4 2 4 4 4 3 1 3 4

39、 C v v v v 44321v1v2v3v4路长的获取和路径的追踪可由最终的路长矩阵和路径矩阵得到。 19 12 16 107 19 4 17 3 15 19 13 9 2 6 19 D v v v v 44321v1v2v3v4 3 1 3 4 2 4 3 4 2 4 4 4 3 1 3 4 C v v v v 44321v1v2v3v4v1-v1：最短路长：19；v1v1v4v3c14=3c41=4C13=1C34=2v2C32=3C24=212347210934c11=4作业：P1746.96.11Chap 6-5 网络最大流问题一、基本概念流图：在网络图G=(V,A)中，V=n,

40、A=m有一个入次等于0的发点vs(或称源)有一个出次等于0的收点vt(或称汇)图中的每条弧(vi,vj)的权数均表示该弧所允许通过的最大流量，记为cij=w(vi,vj)0通过该弧的实际流量记为fij 。cij称为弧容量。st5342(4,0)(3,0)(2,0)(1,0)(1,0)(5,0)(3,0)(2,0)(5,0)(cij,fij)n可行流可行流 ：网络中满足下面两个条件的流称为可行流。：网络中满足下面两个条件的流称为可行流。容量限制条件：每段弧有：容量限制条件：每段弧有：0fijcij 平衡条件：对图中每个顶点，其流入的流量之和应平衡条件：对图中每个顶点，其流入的流量之和应等于流出的

41、流量之和。即无损失下的顶点流量应守衡。等于流出的流量之和。即无损失下的顶点流量应守衡。 n零流：令网络中所有弧的流量零流：令网络中所有弧的流量fij=0,则得到一个总流则得到一个总流量量Q=0的可行流，该可行流称为零流。的可行流，该可行流称为零流。 n正向弧和反向弧：正向弧和反向弧：网络可分解为若干条从起点网络可分解为若干条从起点vs到终点到终点vt的链，链上弧的链，链上弧的方向若与链的方向相同，则称这些弧为正向弧，其的方向若与链的方向相同，则称这些弧为正向弧，其集合记为集合记为u+；否则为反向弧，其集合记为否则为反向弧，其集合记为u-。 vsvt54325,11,11,13,05,3n饱和弧

42、和非饱和弧：弧上流量不能增加(或弧流量增加使网络流量减少)的弧为饱和弧，否则为非饱和弧。 n对正向弧：当fij = cij 时为饱和；n对反向弧： (?)st5342(4,0)(3,0)(2,0)(1,0)(1,0)(5,0)(3,0)(2,0)(5,0)流量可增量：正向非饱和弧：fij 0 其流量可以增加量ij=fji (cij,fij)对fji=0时为饱和。最大流：在给定的流图中由发点vs流经网络后至收点vt的最大流量。最大流问题实际上也是一个线性规划问题。以下讨论的流图的算法一般在有向图上讨论。st5342(4,0)(3,0)(2,0)(1,0)(1,0)(5,0)(3,0)(2,0)(

43、5,0)二、最大流的三个定理n流量可增链和流量可增链定理流量可增链：是从st的一条链，若链上所有弧均为非饱和弧（正向弧fij 0），则这条链的流量就可以增加，该链称为流量可增链。流量可增链的流量最大可以增加的量为流增量 =min链上各弧流量可以增加的量 。弧增量：正向弧 ij=cij -fij ；反向弧 ji =f ji 。st54325,11,11,13,05,3=4 =1=1=3=2=min4,1,1,3,2=1st54325,21,01,03,15,4流量可增链定理：一个st流是最大流的充要条件是，在已给定可行流fij的流图G中不存在任何一条流量可增链。2、 割和最大流最小割定理割：设V

44、是包含网络图G=（V，A）的起点vs在内的顶点的一个集合，V是包含终点vt的一个集合，且V=VV，则弧的集合(V,V)=(vi,vj)| viV,vjV称为分离vs和vt的一个割(cut)。即割是分离网络起点和终点的弧（由V指向V）的一个集合。一个割中所有弧的容量之和称为这个割的割容量。记为 C(V,V)= ), (),( VVvvijjics23t24134左图的割及其割容量分别列于下表中：割容量割VVss，2s，3s，2，32，3，t3，t2，tt（s，2），（），（s，3）(s，3)，(2，3)，(2，t)（s，2），（），（3，t）（2，t），（），（3，t） 5868 （s，2），（

45、），（s，3）5最大流最小割定理：任何一个网络中，由vs到vt可通过的最大流量等于分离vs到vt的最小割容量。 3、整数流定理如果在流图G中给出的所有弧的弧容量cij均为整数，则求得的最大流fij也一定是整数解。三、求最大流的标号法（Ford-Fulkerson算法） 算法原理：流量可增链定理、最大流最小割定理基本思路：在流图G中任找一可行流，从发点s出发，沿网络中的弧对有关顶点进行标号，以此来寻求一条st的流量可增链P。若收点t得到标号，就说明找到了一条流量可增链P，然后将组成该链的各弧的弧流量fij P按求得的流增量进行调整，并使总流量增大。不断反复这个过程，一直进行到在调整后的流图中再也

46、找不到一条流量可增链为止，这时就是最大流。此时最后一次标号的点组成V集，未标号的各点组成V集，该(V,V)截集就是最小割，max Q = min C（ V,V) 。算法步骤step1:标号过程（任一可行流上）顶点的标号包括两部分，即: vj(vi, j) j =min i, ij i为先行顶点vi的流量可增量， ij 为弧aij（或aji）的流量可增量。 从起点开始标号：vs(-,)，然后对未标号且与vs相邻的点vj进行检查：若若asj为正向弧，此时给vj 赋标号（s, csj-fsj）;若asj为反向弧，此时给vj 赋标号（-s, fis）。然后，假设从vs开始，现已使顶点vi获得标号，记已

47、获标号的顶点的集合为V，未获标号的顶点集合为V。任取一已获标号的顶点viV，对其未获标号邻点vjV进行检查，此时可能出现以下三种情况：表示vj的先行点；负号表示vj为弧起点，反向弧流量可增量n若aij为正向弧，且ij=cij-fij0，此时给vj赋标号（i, j）。nvi与vj由反向弧aji 相连，且fji0，这时给vj赋标号（-i, j），此时的 j =mini，fji。nij=0 （不管vi与vj之间是正向弧还是反向弧），这时不赋予vj标号。若为情形（1）或（2），则在V中增加了一个顶点，V中减少一个顶点。继续上述标号过程，直至V中包含终点vt。这时找到了一条由vs到vt的流量可增链（不一

48、定所有的顶点都获标号），然后转到一个过程。 Step 2 增流过程按终点vt的第一个标号反向追踪其先行顶点，再反向追踪下一个先行顶点，如此继续，直到vs，这就得到了一条流量可增链P。终点vt的第二个标号t ，给出了P的流量调整量，该链上各个弧调整后的流量为： P P 上的反向弧对上的正向弧对tijtijijfff不在P上的各弧流量不变。调整完之后得一新的可行流，再重新进入标号过程和调整过程，直到不存在流量可增链为止，这时就得到了最大流。 举例：求下图的最大流。s1243567t4269273033783654751224126045s1243567t4269273033783654751224

49、126045(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)s1243567t4269273033783654751224126045(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(-,)(s,42)(1,30)(3,30)(5,30)(30)(30)(30)(30)s1243567t4269273033783654751224126045(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(-,)(30)(30)(30)(30)(s,69)(2,69)(4,12)(7,12)(12)(1

50、2)(12)(12)s1243567t4269273033783654751224126045(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(30)(30)(30)(30)(12)(12)(12)(12)(-,)(s,12)(1,12)(2,12)(4,12)(6,12)(5,12)(12)(12)(12)(42)(42)s1243567t4269273033783654751224126045(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(30)(30)(30)(30)(12)(24)(12)(12)(-,)(12)

51、(12)(12)(42)(42)(s,57)(2,54)(4,54)(6,12)(5,12)(24)(36)(24)(24)(54)(24)(-,)s1243567t4269273033783654751224126045(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(30)(30)(30)(30)(12)(24)(12)(12)(12)(12)(12)(42)(42)(24)(36)(24)(24)(54)(s,45)(2,42)(4,42)(7,12)(6,12)(36)(48)(36)(12)(24)(-,)s1243567t426927303378

52、3654751224126045(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(0)(30)(30)(30)(30)(12)(24)(12)(12)(12)(12)(12)(42)(42)(24)(36)(24)(24)(54)(36)(48)(36)(12)(24)(s,33)(2,30)(+4,30)S(-2,12)四、具有多发点和多收点时的最大流模型ss1s2s3sn1t1t2t3tn2t解决的方法：虚设一个总发点s和一个总收点t，然后将s与s1,sn1用弧相连，将t1,tn2 与t用弧相连，新增的弧容量设为，这样就将图改造成为一个求s-t的最大流。举例：

53、有s1,s2,s3三个矿山，它们的日矿石产量分别为5000，10000，15000t。现供给t1,t2,t3,t4四个冶炼厂，它们的日需要量分别为4000，7000，9000，6000t。假定由三个矿山到四个冶炼厂的日运输能力受运输线路容量的限制，如下表所示，问怎样的调运方案才能使三个矿山尽可能满足冶炼厂的需要？t1t2t3t4S130001000500-S22000500015001000S3-100080004000s1s2s3t1t2t3t43010520501510104080st5010015040709060(-,)(s,50)(s1,30)(t1,30)(30)(30)(30)网

54、络最大流的应用：如零件加工、人员应聘的最大数量安排(最大匹配问题)举例：某单位招收懂俄、英、日、德、法文的翻译各一人，现有5人来应聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问此5人是否都能得到应聘？最多有几个得到应聘，应聘后每人从事哪一方面的翻译任务？ 作业：P175 6.12Chap 6-6 最小费用流最小费用流是指保证满足输送流量为Q的前提下使总输送费用最小的一个st流。一、无弧容量限制时的最小费用流1/a13/a32/a24/a4w12w14w23w34f12f32f34f14基本概念流向图：在网络图中画出表示（货物）流向的图。流向图中的流必须是可

55、行流。 f41最小费用最大流费用流无弧容量限制下的最小方框表示发货点方框表示发货点圆框表示收货点圆框表示收货点流量标注，满足流量标注，满足可行流、右行原则可行流、右行原则最优流向图：运输费用最低的流向图。内圈流线长(l内)：回路中内侧有流向箭头的各边边长(权)之和。外圈流线长(l外)：外侧有流向箭头的各边边长(权)之和。圈长(l): 回路各边边长之和。最优流向图定理：一个流向图是最优流向图的充要条件:1. 流向图中无对流；2. 对每一个回路，l外l/2; l内l/2求最优流向图的步骤求最优流向图的步骤n检查有无悬挂点，将其收发量并入相邻顶点；n给出一初始可行流；n检查有无对流，将其流量小者对消

56、；n检查每回路的l外、 l内，是否满足充要条件（2）；若不满足，则添加一相反流量，进行流量对消；（ l外l/2; l内内l/2 ）1.恢复悬挂点，并按其收发要求供销。2/65/71/33/24/36/51054861062/65/71/34/56/510586106例：63252/65/71/34/56/51058610663252532/65/71/34/56/5105861066325253332/65/71/33/24/36/51054861062/65/71/34/56/51058610663252533325332最小费用 z=99。二、最小费用最大流最小费用最大流就是要求一个最大流

57、f，使流的总运输费用最低。或者说，网络以最小费用通过某一可行流的情形，当网络上的流量达到最大时，这时的流称为最小费用最大流。计算思路：从一流量为f1的最小费用可行流F1开始，寻求最小费用流量可增链，并增流。对新的费用最小可行流寻求最小费用流量可增链，并增流，如此反复，直到得出最小费用最大流。迭代步骤：n任给一最小费用可行流（最简单的为零流）； 1.给网络的弧赋权，0c ,0c ,ijijijijijijffbb若若当作正向弧使用时： 当作反向弧使用时： 0 ,0 ,ijijijijffbb若若为了便于计算和检查，常在每条弧上依次注出以下四个数字(1)弧容量cij ；(2)弧流量fij ；(3)

58、 b+ij(作为正向弧使用时在其上流过单位物品的费用)；(4) b-ij (作为反向弧使用时在其上流过单位物品的费用)。 Cij、bij 流过单位物品的费用3. 以b+ij或b-ij为弧aij的权( 弧长)，用Dijkstra算法（双标号法）求vsVt的最短路P。 4. 取增流量对P上的各孤增流，这里的ij为孤aij的流量可增值 。 ijPvijminmin5. 转回第2步，直到第3步求不出有限长的最短路为止，这时已得到最小费用最大流。 举例：求下图的最小费用最大流，各弧的弧容量（第一个数字）和通过单位物品的费用（第二个数字）如图示。s234t6,44,13,26,36,62,35,26,0,

59、4,4,0,1, 3,0,2, 6,0,3, 6,0,6, 2,0,3, 5,0,2, s234t(0,s)(1,s)(3,2)(4,2)(6,4)6,0,4,4,2,1, -13,0,2, 6,0,3, 6,0,6, 2,2, ,-3s234t(0,s)522-2(1,s)(3,2)(7,2)(6,3)6,0,4,4,4, , -13,0,2, 6,0,3, 6,2,6, -62,2, ,-3s234t522-2(0,s)(4,s)(7,3)(9,4)4,4, , -13,0,2, 6,3,3, -36,2,6, -62,2, ,-3s234t55-2634-4(0,s)(4,s)(7,3)

60、(4,4)(4,4)(10,2)4,4, , -13,0,2, 6,5,3, -36,4,6, -62,0, -3, s234t55-2654-4(0,s)(4,s)(7,3)得到最小费用最大流最大流量5+49最小费用73例题：P169例12作业：P1756.136.14小节、举例一、设备更新问题某厂要考虑他们使用的一台设备在每年年初是否对它更新，假设只计算以下两项费用：设备的年初购置费a 和每年年内设备的使用费b 。试作出一个五年的设备更新计划，要求使得支付的费用最小。两费用的预测值为下表： 第i年1 2 3 4 5a10 11 12 13 14b5 6 8 11 1512354615212