第5章图与网络分析

《第5章图与网络分析》由会员分享，可在线阅读，更多相关《第5章图与网络分析（162页珍藏版）》请在金锄头文库上搜索。

1、第第5章章 图与网络分析图与网络分析( Graph Theory and Network Analysis )( Graph Theory and Network Analysis )图的基本概念与模型图的基本概念与模型树树最短路问题最短路问题网络的最大流网络的最大流最小费用流最小费用流应用举例应用举例近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。 这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Euler1736年证明了不年证明了不

2、可能存在这样的路线。可能存在这样的路线。第一节第一节 图的基本概念与模型图的基本概念与模型KnigsbergKnigsberg桥对应的图桥对应的图例例1、有甲、乙、丙、丁、戊五个球队，、有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况也可以用图表示出来。它们之间比赛的情况也可以用图表示出来。V1V2V3V4V5e5e4e1e2e3e6e7一、图基本概念一、图基本概念例例2 某单位储存八种化学药品，其中某些某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映药品是不能存放在同一个库房里的。为了反映这个情况可以用点这个情况可以用点V1,V2,V8分别代表这八分别代表这八种药品，

3、若药品种药品，若药品Vi和和药品药品Vj是不能存放在同是不能存放在同一个库房的，则在一个库房的，则在Vi和和Vj之间连一条线。之间连一条线。 V1V2 V3 V4 V5 V8 V7 V6图的表示方法： 一般地，当用图论研究一个实际问题时，一般地，当用图论研究一个实际问题时，常以顶点（常以顶点（Vertex）表示要研究的对象，以）表示要研究的对象，以它们之间的连线，表示某种关系，这种连线它们之间的连线，表示某种关系，这种连线称为边（称为边（Edge），目的是为了解决某个极值），目的是为了解决某个极值问题。图中的点用问题。图中的点用v表示，边用表示，边用e表示。对每表示。对每条边可用它所连接的点表

4、示，条边可用它所连接的点表示，记作：记作：e1=v1,v1; e2=v1,v2; 运筹学中研究的图具有下列特征: 强调点与点之间的关联关系，不讲究图的比例大小与形状；每条边上赋有一个权；建立网络模型，求最大值或最小值。下图可以提出很多极值问题142653876 63162 7 433716v3e7e4e8e5e6e1e2e3v1v2v4v5 端点端点,关联边关联边,相邻相邻若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。若点。若点vi、vj与同一条边关与同一条边关联，称点联，称点vi和和vj相邻；

5、若边相邻；若边ei和和ej具具有公共的端点，称边有公共的端点，称边ei和和ej相邻相邻。二、关于图的另外一些名称和术语：二、关于图的另外一些名称和术语： 环环, 多重边多重边, 简单图简单图如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如右图中边。如右图中边e1为环。如果两个点为环。如果两个点之间多于一条，称为之间多于一条，称为多重边多重边，如右图，如右图中的中的e4和和e5，对无环、无多重边的图，对无环、无多重边的图称作称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5 次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的

6、数目称为相关联的边的数目称为点点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)。右图中右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作次为奇数的点称作奇点奇点，次为偶数，次为偶数的点称作的点称作偶点偶点，次为，次为1的点称为的点称为悬挂悬挂点点，次为，次为0的点称作的点称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次: 一个图的次等于各点的次之和。一个图的次等于各点的次之和。定理定理1 任何图中，顶点次数之和等于所有边数的任何图中，顶点次数之和等于所有边数的2倍。倍。定理定理2 任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇

7、数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的均被计算了两次，所以顶点次数的总和等于边数的2倍。倍。证明：设证明：设V1和和V2分别为图分别为图G中奇点与偶点的集合。由定理中奇点与偶点的集合。由定理1可得：可得：2m为偶数，且偶点的次之和为偶数，且偶点的次之和 也为偶数，所以也为偶数，所以 必为偶必为偶数，即奇数点的个数必为偶数。数，即奇数点的个数必为偶数。 链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其图中某些点和边的交替序列，若其中各边互不相同，且对

8、任意中各边互不相同，且对任意vi,t-1和和vit均相邻称为均相邻称为链链。用。用 表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起点与终点重合的链称作起点与终点重合的链称作圈圈。如。如果每一对顶点之间至少存在一条果每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则，否则称图不连通。称图不连通。 子图，部分图子图，部分图(支撑子图支撑子图)图图G1=V1、E1和图和图G2=V2，E2如果有如果有 称称G1是是G2的一个的一个子图子图。若有若有 ，则称，则称G1是是G2的一的一个个部分图部分图(支撑子图支撑子图)。v3e7e4e8e5e6e1e2e3v

9、1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）图） 网络（赋权图）网络（赋权图）赋权图）赋权图）:权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等。等等。无向网络无向网络:端点无序的赋权图称为端点无序的赋权图称为.有向网络有向网络:端点有序的赋权图称为端点有序的赋权图称为。910201571419256 图的矩阵描述：图的矩阵描述： 邻接矩阵、关联矩阵、权矩阵等。邻接矩阵、关联矩阵、权矩阵等。1. 邻接矩阵邻接矩阵对于图对于图G=（V，E），），| V |=n， | E |=m，有，有n n阶方阶方矩阵

10、矩阵A=(aij) n n，其中其中图的基本概念与模型图的基本概念与模型v5v1v2v3v4v64332256437例例6.2 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下对于赋权图对于赋权图G=(V,E), 其中边其中边 有权有权 , 构造矩阵构造矩阵B=(bij) n n 其中：其中：2. 2. 权矩阵权矩阵权矩阵权矩阵v5v1v2v3v4v64332256437例例6.4 下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下:G=(V,E) 矩阵表示矩阵表示矩阵表示矩阵表示A A 邻接矩阵邻接矩阵B B 关联矩阵关联矩阵边边e=u,v 关联边关联边

11、 端点端点 重重重重合合合合环环多重边多重边 平行边平行边平行边平行边简单图简单图不含不含不含不含多重图多重图含含含含点的次点的次点的次点的次 0 1 奇数奇数 偶数偶数 子图子图子子图图生生成成子子图图孤孤立立点点悬悬挂挂点点奇奇点点偶偶点点顶点数顶点数p边数边数q点边关系点边关系各种链的概念各种链的概念欧拉图与中国邮路问题欧拉图与中国邮路问题欧拉图欧拉图哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，哥尼斯堡（现名加里宁格勒）是欧洲一个城市，PregeiPregei河把该城分成两部分，河中有两个小岛，十八世纪河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及

12、小岛之间共有七座桥，当时人们提出这样时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如的问题：有没有办法从某处（如A A）出发，经过各桥一次）出发，经过各桥一次且仅一次最后回到原地呢？且仅一次最后回到原地呢？Cab图图 4-10 ad哥尼斯堡七桥问题acbd(b) 定理定理2 连通无向图连通无向图G为欧拉链的充要条件是它恰含两个奇次为欧拉链的充要条件是它恰含两个奇次顶点。顶点。 定义定义1. 在连通无向图在连通无向图G中中,若存在经过每条边恰好一次的一个若存在经过每条边恰好一次的一个圈或一条链圈或一条链,就称此圈或链就称此圈或链 为欧拉圈或欧拉链。若图为欧拉圈或欧拉链

13、。若图G含一条欧含一条欧拉圈，则称为欧拉图。拉圈，则称为欧拉图。 定理定理1 连通无向图连通无向图G为欧拉图的充要条件是它的全部顶点都为欧拉图的充要条件是它的全部顶点都是偶次顶点。（是偶次顶点。（G中无奇次顶点）中无奇次顶点）欧拉链欧拉链欧拉图欧拉图中国邮路问题中国邮路问题定理定理3 使图使图G成为总权最小的欧拉图的充要条件是：成为总权最小的欧拉图的充要条件是： （1） 在有奇次顶点的图在有奇次顶点的图G中，通过加重复边的方法使图中，通过加重复边的方法使图不再包含奇次顶点，但原图的每条边最多只能加一条重不再包含奇次顶点，但原图的每条边最多只能加一条重复边。复边。 （2） 在图在图G的每个回路上

14、，重复边之总权不超过该回路的每个回路上，重复边之总权不超过该回路非重复边之总权。（或回路总长的一半）非重复边之总权。（或回路总长的一半） 例例1 试为图试为图4-13（a)构成总权最小的欧拉图。图中构成总权最小的欧拉图。图中线旁的数字为相应边的权。线旁的数字为相应边的权。124332124（a) 图图4-13例例2 试为图试为图4-14（a）所示的街道规划最优投递路线。所示的街道规划最优投递路线。 解：可按以上所述步骤进行，最终结果示于图解：可按以上所述步骤进行，最终结果示于图4-14（b)，总总权等于权等于52，重复边的长度等于，重复边的长度等于10。1334333333222图图4-14（

15、a）2413 333333 322 图图4-14（b）22第二节第二节 树树树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。域应用极为广泛。例例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。下图所示。AB CDEF GH运动员运动员例例6.3 某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售

16、科销售科检验科检验科动力科动力科 树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n 个顶点的树必有个顶点的树必有n-1 条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6 图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G

17、1的部分图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一般图G1含有多含有多个部分树，其中树枝总长最小的部分树，称为该图的最小个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2 例如，图例如，图4-18（a）是一个有四个顶点（是一个有四个顶点（n=4）的连通图，它共有的连通图，它共有 nn-2=42=16个生成树。个生成树。V1V2V3V4图图4-18（a）a ab bc cf fe ed dh h

18、g gb bf fe ed da ab bc cf fe ed dh hg gb bf fd dg gb bc ce ed da ab bc cf fe ed dh hg ga ab bc ch ha ab bc cf fe ed dh hg ga af fd dg ga ab bc cf fe ed dh hg g赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v684375261

19、8v1v2v3v4v5v643521边数边数n-1=5v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=15避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15v1v1v7v7v4v4v3v3v2v2v5v5v6v620201

20、5159 9161625253 3282817174 41 123233636练习：练习：练习：练习：应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174

21、 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 328281

22、7174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=57练习：练习：练习：练习：应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树v1v1v7v7v4v

23、4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v

24、5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=57课堂练习：课堂练习：课堂练习：课堂练习：3749346321Min C(T)=12Min C(T)=15254173314475答案：

25、答案：34122323242Min C(T)=12213638534567454321Min C(T)=18 一一某一点到另一点的最短路的某一点到另一点的最短路的Dijkstra法法二二所有点对间的最短路所有点对间的最短路 返回返回第三节 最短路问题就是从给定的网络图中找出一点到各点或任意两点之就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路间距离最短的一条路 .有些问题，如选址、管道铺设时的选线、设备更新、有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问

26、题在生产实际中得到广泛应用。短路的问题。因此这类问题在生产实际中得到广泛应用。 里特城里特城 （Littletown）是一个乡村的小镇。它的是一个乡村的小镇。它的消防队要为包括许多农场社区在内大片的地区提供服消防队要为包括许多农场社区在内大片的地区提供服务。在这个地区里有很多道路，从消防站到任何一个务。在这个地区里有很多道路，从消防站到任何一个社区都有很多条路线。因为时间是一个到达火灾发生社区都有很多条路线。因为时间是一个到达火灾发生点的主要因素，所以消防队队长希望事先能够确定从点的主要因素，所以消防队队长希望事先能够确定从消防站到每一个农场社区的最短路。消防站到每一个农场社区的最短路。例子：

27、里特城例子：里特城 的消防队问题的消防队问题最最短路：短路：O A B E F T 19 英里英里一、一、 求最短路的Dijkstra算法 1、算法的基本思想、算法的基本思想2、步骤：、步骤： （1）、给vs以P标号，P（vs）=0，其余各点均给T标号，T（vi）=+。（2）、若vi点为刚得到P标号的点，考虑这样的点vj：（vi，vj）属于E，且vj为T标号。对vj的T标号进行如下的更改： T(vj)=minT(vj),P(vi)+lij (3)、比较所有具有T标号的点，把最小者改为P标号，若全部点均为P标号则停止，否则转（2）。v1v8v7v6v5v4v3v24645675795414例、用

28、例、用Dijkstra算法求下图中算法求下图中v1v8点的最短路。点的最短路。 v1v8v7v6v5v4v3v24645675795414P（0，v1）T（）T（）T（）T（）T（）T（）T（）v1v8v7v6v5v4v3v24645675795414P（0，v1）T（）T（）T（）T（）T（）T（）T（）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）T（6）T（）T（）T（）T（）T（）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）T（6）T（）T（）T（）T（）T（）v1v8v7v6v5v4v3v2464567

29、5795414P（0，v1）P（v1,4）T（6）T（9）T（8）T（）T（）T（）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）T（8）T（）T（）T（）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）T（8）T（）T（）T（）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）P（8，v2）T（）T（）T（）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）

30、P（8，v2）T（）T（）T（）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）P（8，v2）T（14）T（13）T（）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）T（9）P（8，v2）T（14）T（13）T（）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（14）T（13）T（）P（9，v2）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（

31、14）T（13）T（）P（9，v2）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（14）T（）P（9，v2）P（13，v5）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（14）T（ ）P（9，v2）P（13，v5）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（14）T（ 17 ）P（9，v2）P（13，v5）v1v8v7v6v5v4v3v24645675795414P（0，v1）P

32、（4，v1）P（6，v1）P（8，v2）T（17）P（9，v2）P（13，v5）P（14，v5）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）T（15）P（9，v2）P（13，v5）P（14，v5）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）P（9，v2）P（13，v5）P（14，v5）P（15，v7）v1v8v7v6v5v4v3v24645675795414P（0，v1）P（4，v1）P（6，v1）P（8，v2）P（9，v2）P（13，v5）P（14，v5

33、）P（15，v7）Dijkstra最短路算法的最短路算法的特点特点和和适应范围适应范围每次迭代只有一个节点获得永久标号，若有两个或两个以上节点的临时标号同时最小，可任选一个永久标号；总是从一个新的永久标号开始新一轮的临时标号；永久标号Pj 表示 vs 到 vj 的最短路，第 k 次迭代得到的永久标号，最多有n1 次迭代；可以应用于简单有向图和混合图，在临时标号时，所谓相邻必须是箭头指向的节点；若第 n1 次迭代后仍有节点的标号为 ，则表明 vs 到该节点无有向路径；vs 到所有点的最短路也是一棵生成树，但不是最小生成树这个算法只设用于全部权为非负情况,如果某边上权为负的,算法失效;当vi与vj

34、两点之间至少有两条边相关联时，留下一条最短边，去掉其它关联边。1024149135787v1v2v3v4v5v6 例例 求下图所示网络之顶点求下图所示网络之顶点1至至6的最短路和最短路长。的最短路和最短路长。P（0，v1）P（10，v1）P（15，v2）P（22，v5）P（22，v5）P（23，v2）142653876 63162 7 433716二、 所有点对间的最短路Floyd算法 1、 写出图的权矩阵写出图的权矩阵 步骤：步骤：、输入权矩阵（）；、 对n个顶点的图G,该方法迭代n步结束，第k次迭代的矩阵Dk的元素dij(k)按下式选取 dij(k) =mindij(k-1),dik(k-

35、1）+dkj(k-1）其中，i,j=1,2,3,n。但当i=k或j=k时，dij(k)=dij(k-1).。、（）中的元素就是到的最短路长。v1v3v4v2v5512310655228442例例 求下图所示网络图各点对间的最短路和最短路长求下图所示网络图各点对间的最短路和最短路长。23147 4 32 910例例 求下图所示网络图各点对间的最短路和最短路长求下图所示网络图各点对间的最短路和最短路长。课堂练习：课堂练习：1. 用用Dijkstra算法求下图从算法求下图从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：2

36、. 求从求从v1到到v8的最短路径的最短路径237184566134105275934682237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为10最短路问题的应用：最短路问题的应用：例例6.7 电信公司准备准备在甲、乙两地沿路架设一条光缆线，电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。通图。权数表示两

37、地间公路的长度（单位：公里）。 v1 （甲地）甲地）1517624431065v2v7 (乙地乙地)v3v4v5v6解：这是一个求无向图的最短路的问题。解：这是一个求无向图的最短路的问题。例例6.8 设备更新问题。某公司使用一台设备，在每年年初，设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就低。如果继续使用旧设备，可以省去购置费，但维修

38、费用就高了。请设计一个五年之内的更新设备的计划，使得五年就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备每年年初的价格表年份年份12345年初价格年初价格1111121213设备维修费如下表设备维修费如下表使用年数使用年数0-11-22-33-44-5每年维修费用每年维修费用5681118解：解：将问题转化为最短路问题，如下图：用将问题转化为最短路问题，如下图：用vi表示表示“第第i年年年年初购进一台新设备初购进一台新设备”,弧（弧（vi,vj）表示第）表示第i年年初购进的设备一

39、年年初购进的设备一直使用到第直使用到第j年年初。年年初。v1v2v3v4v5v6把所有弧的权数计算如下表，把所有弧的权数计算如下表，把权数赋到图中，再用把权数赋到图中，再用Dijkstra算法求最短路。算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723 最终得到下图，可知，最终得到下图，可知，v1到到v6的距离是的距离是53，最短路径有两条：，最短路径有两条： v1v3v6和和 v1v4v6 V1（0,s）v3v4(41,1) v5v62230415916(22,

40、1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)第四节第四节 网络的最大流网络的最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。这就是一个网络最大流问题。实例：实例：公司公司 的最大流问题的最大流问题 公司是欧洲一家生产豪华汽车的制造商。公司是欧洲一家生产豪华汽车的制造商。 虽然它生产的汽车在所有发达国家的销量都不错，虽然它生产的汽车在所有发达国家的销量都不错， 但是对于这家公司来说，出口到美国显得尤其重要。但是对于这家公司来说，出口到美国显得尤其重要。 公

41、司因为提供优质的服务而获得很好的公司因为提供优质的服务而获得很好的 声誉，保持这个声誉一个很重要的秘诀是它有着充裕的声誉，保持这个声誉一个很重要的秘诀是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商和汽车配件供应，从而能够随时供货给公司众多的经销商和授权维修店。这些供应件主要存放在公司的配送中心里，授权维修店。这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即送货。卡尔需要优先考虑的是改这样一有需求就可以立即送货。卡尔需要优先考虑的是改进这些配送中心的不足之处。进这些配送中心的不足之处。 背背景景 该公司在美国有几个配送中心。但是，离洛杉矾中心最该公司在美国有几个配送中

42、心。但是，离洛杉矾中心最近的一个配送中心却坐落在离洛杉矾近的一个配送中心却坐落在离洛杉矾1000 多英里的西雅图。多英里的西雅图。由于的汽车在加利福尼亚越来越受欢迎，所以保证由于的汽车在加利福尼亚越来越受欢迎，所以保证洛杉矾中心良好的供应就显得尤为重要了。因此，现在那里洛杉矾中心良好的供应就显得尤为重要了。因此，现在那里的供应不断减少的现状成为了公司高层管理真正关心的问的供应不断减少的现状成为了公司高层管理真正关心的问题题正如现在卡尔深切领会到了一样。正如现在卡尔深切领会到了一样。 大部分的汽车配件以及新车是在该公司坐落于德国斯图大部分的汽车配件以及新车是在该公司坐落于德国斯图加特的总厂和新车

43、一起生产的。也就是这家工厂向洛杉矾加特的总厂和新车一起生产的。也就是这家工厂向洛杉矾中心供应汽车配件。由于其中的一些配件体积很大，某些中心供应汽车配件。由于其中的一些配件体积很大，某些配件的需求量很多，这就使得供应的总量非常庞大配件的需求量很多，这就使得供应的总量非常庞大每每月有超过月有超过300，000立方英尺的配件需要运到。现在，下个立方英尺的配件需要运到。现在，下个月需要多得多的数量以补充正在减少的库存。月需要多得多的数量以补充正在减少的库存。 卡尔需要尽快做出一个方案，使得下个月从总厂运送卡尔需要尽快做出一个方案，使得下个月从总厂运送到洛杉矾配送中心的供应件尽可能的多。他已经认识到了到

44、洛杉矾配送中心的供应件尽可能的多。他已经认识到了这是个最大流问题这是个最大流问题一个使得从总厂运送到洛杉矾配送一个使得从总厂运送到洛杉矾配送中心的配件流最大的问题。因为总厂生产的配件量远远要中心的配件流最大的问题。因为总厂生产的配件量远远要大于能够运送到配送中心的量，所以，可以运送多少配件大于能够运送到配送中心的量，所以，可以运送多少配件的限制条件就是该公司配送网络的容量。的限制条件就是该公司配送网络的容量。 问题问题LASTLIROBONONY 806070405030507040BMZ的网络模型，图中的数字代表该弧的容量的网络模型，图中的数字代表该弧的容量v1V2 5, 2v410,54,

45、1 3,38,3V3 6,3 v53,25,111,617,2图图4-23v6如图如图4-23 是联接某产品产地是联接某产品产地v1和销售地和销售地v6点的交通网。点的交通网。 一一 基本概念基本概念二二 求最大流的标号法求最大流的标号法返回v1V2 5, 2v410,54,0 3,38,3V3 6,2 v53,35,111,617,2图图4-23v6如图如图4-23 是联接某产品产地是联接某产品产地v1和销售地和销售地v6点点的交通网。的交通网。一、基本概念：一、基本概念：1. 1. 容量网络：容量网络：容量网络：容量网络：队网络上的每条弧队网络上的每条弧(vi,vj)都给出一个最大的通都给

46、出一个最大的通过能力，称为该弧的过能力，称为该弧的容量容量容量容量，简记为，简记为cij。容量网络中通常规定。容量网络中通常规定一个一个发点发点发点发点(也称源点，记为也称源点，记为s)和一个和一个收点收点收点收点(也称汇点，记为也称汇点，记为t)，网络中其他点称为，网络中其他点称为中间点中间点中间点中间点。st48441226792. 网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3. 流与可行流流与可行流 流流是指加在网络各条弧上的实际流量，对加在弧是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上上的负载量记为的

47、负载量记为fij。若。若fij=0，称为零流。，称为零流。满足以下条件的一组流称为满足以下条件的一组流称为可行流可行流。 容量限制条件。容量网络上所有的弧满足：容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。中间点平衡条件。 若以若以F表示网络中从表示网络中从st的流量，则有：的流量，则有：结论：任何网络上一定存在可行流。（零流即是结论：任何网络上一定存在可行流。（零流即是可行流）可行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使F值值达到最大。达到最大。 割与割集割与割集割是指容量网络中的发点和收

48、点分割开，并使割是指容量网络中的发点和收点分割开，并使st的流中断的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用和，用 表示。表示。如下图中，如下图中，AA将网络上的点分割成将网络上的点分割成 两个集合。并有两个集合。并有 ，称弧的集合，称弧的集合(v1,v3),(v2,v4)是一个割，且是一个割，且 的流量为的流量为18。 stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABB定理定理定理定理1 1 在网络中在网络中st的最大流量等于它的最小割集的容量，的最大流量等于它的最

49、小割集的容量，即：即： v (f ) = c (V, V) vsv2v3v4v5v6vt（4，0）（13，11）（5，5）（9，9）（5， 4）（5，5）（6，6）（5， 2）（9，7）（4，4）（4，4）（10，9）图图5-3 最大流量网络图（网络最大流图）最大流量网络图（网络最大流图） (-, )(vs+,2)于是得到于是得到最小割最小割为为:（S， ）=(vs,v3),(v2,v4),(v2,v5)最小割容量最小割容量是：是：9+6+5=20恰好恰好等于最大流流量。等于最大流流量。流量可增链流量可增链流量可增链流量可增链在网络的发点和收点之间能找到一条链，在该链上所在网络的发点和收点之间

50、能找到一条链，在该链上所有指向为有指向为st的弧，称为前向弧，记作的弧，称为前向弧，记作+,存在存在f0，则称这样的链，则称这样的链为增广链。为增广链。例如下图中，例如下图中，sv2v1v3v4t。定理定理定理定理3 3 网络网络N中的流中的流 F是最大流当且仅当是最大流当且仅当N中不包含任何增广中不包含任何增广链链二、求网络最大流的标号法二、求网络最大流的标号法 基本思想基本思想基本思想基本思想 由一个流开始，系统地搜寻增广链，然后在此链上增由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。流，继续这个增流过程，直至不存在增广链。 基本方法基本方法基本方法

51、基本方法 (1)找出第一个可行流，（例如所有弧的流量找出第一个可行流，（例如所有弧的流量fij =0。）。）(2)用标号的方法找一条增广链用标号的方法找一条增广链 首先给发点首先给发点s标号标号(),标号中的数字表示允许的最大调整标号中的数字表示允许的最大调整量。量。 选择一个点选择一个点 vi 已标号并且另一端未标号的弧沿着某条链已标号并且另一端未标号的弧沿着某条链向收点检查：向收点检查： 如果弧的起点为如果弧的起点为vi，并且有，并且有fij0，则，则vj标号标号(fji)(3) 重复第重复第(2)步，可能出现两种结局：步，可能出现两种结局： 标号过程中断，标号过程中断，t无法标号，说明网

52、络中不存在流量可增无法标号，说明网络中不存在流量可增链，目前流量为最大流。同时可以确定最小割集，链，目前流量为最大流。同时可以确定最小割集，记已标号记已标号的点集为的点集为V,未标号的点集合为未标号的点集合为V,(V,V)为网络的最小割。为网络的最小割。 t得到标号，反向追踪在网络中找到一条从得到标号，反向追踪在网络中找到一条从s到到t得由标号得由标号点及相应的弧连接而成的流量可增链。继续第点及相应的弧连接而成的流量可增链。继续第(4)步步(4) 修改流量。设原图可行流为修改流量。设原图可行流为f，令，令得到网络上一个新的可行流得到网络上一个新的可行流F。(5) 擦除图上所有标号，重复擦除图上

53、所有标号，重复(1)-(4)步，直到图中找不到任步，直到图中找不到任何流量可增链，计算结束。何流量可增链，计算结束。例例6.10 用标号算法求下图中用标号算法求下图中st的最大流量，并找出最小割。的最大流量，并找出最小割。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)网络的最大流网络的最大流解：解：(1) 先给先给s标号标号()stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()网络的最大流网络的最大流stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(

54、2) 检查与检查与s点相邻的未标号的点，因点相邻的未标号的点，因fs1cs1，故对，故对v1标号标号=min, cs1-fs1=1,(1)网络的最大流网络的最大流stv1v3v2v48(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(1)网络的最大流网络的最大流stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(1)(1)(3) 检查与检查与v3点相邻的未标号

55、的点，因点相邻的未标号的点，因f3tc3t，故对，故对vt标号标号=min1, c3t-f3t= min1, 1= 1(1)找到一条增广链找到一条增广链sv1v3t网络的最大流网络的最大流(4) 修改增广链上的流量，非增广链上的流量不变，得到新的修改增广链上的流量，非增广链上的流量不变，得到新的可行流。可行流。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)()(1)(1)(1)网络的最大流网络的最大流(5) 擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(8)9(4)5(

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

57、。stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)(2)(1)(1)网络的最大流网络的最大流stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(2)(2)(2)(1)(1)(7) 擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。网络的最大流网络的最大流stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(1)(1)(1)(7) 擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号

58、，重复上述标号过程，寻找另外的增广链。(2)=min,1=1(1)=min1,2=1(3)=min1,4=1网络的最大流网络的最大流例例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)网络的最大流网络的最大流stv1v2v3v4v54(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(

59、6)(3)=min6,2=2(2)(t)=min2,5=2(2)存在增广链存在增广链存在增广链存在增广链svsv2 2vv3 3 t t网络的最大流网络的最大流(2) 修改增广链上的流量，非增广链上的流量不变，得到新的修改增广链上的流量，非增广链上的流量不变，得到新的可行流。可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)()(6)(2)(2)网络的最大流网络的最大流(3) 擦除原标号，重新搜寻增广链。擦除原标号，重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5

60、(3)4(4)2(2)7(6)8(5)()(6)(2)(2)网络的最大流网络的最大流(4) 重新搜寻增广链。重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(2)=min,4=4(4)(1)(5)=min4,1=1(3)=min1,2=1(1)(1)(t)=min1,3=1存在增广链：存在增广链：存在增广链：存在增广链：svsv2 2vv5 5vv3 3 t t网络的最大流网络的最大流(5) 修改增广链上的流量，非增广链上的流量不变，得到新的可修改增广链上的流量，非增广链上的流量不变，得到新的可行流。

61、行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(4)(1)(1)(1)网络的最大流网络的最大流(6) 擦除原标号擦除原标号stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()(4)(1)(1)(1)网络的最大流网络的最大流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()(1)(1)(1)(5)=min,1=1(5)=min1,1=1(5)=min1,2=1(7

62、) 重新搜寻增广链。重新搜寻增广链。存在增广链：存在增广链：存在增广链：存在增广链：svsv5 5vv3 3 t t网络的最大流网络的最大流(8) 调整增广链上的流量，非增广链流量不变，得到新的可行流调整增广链上的流量，非增广链流量不变，得到新的可行流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()(1)(1)(1)网络的最大流网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)()(1)(1)(1)(9) 擦除原标号擦除原标号网络的最

63、大流网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)(10) 重新标号，搜索增广链重新标号，搜索增广链()(1)=min,1=1(1)(5)=min1,1=1(1)(4)=min1,1=1(1)(t)=min1,1=1(1)存在增广链：存在增广链：存在增广链：存在增广链：svsv1 1vv5 5vv4 4tt网络的最大流网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)()(1)(1)(1)(1)(11) 调整增广链上的流量，

64、非增广链流量不变，得到新的可行流调整增广链上的流量，非增广链流量不变，得到新的可行流网络的最大流网络的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)()(1)(1)(1)(1)(11) 擦除标号，在新的可行流上重新标号。擦除标号，在新的可行流上重新标号。网络的最大流网络的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)()(11) 擦除标号，在新的可行流上重新标号。擦除标号，在新的可行流上重新标号。(3)(1)=min,3=1无法标号，不存在增广链，此可行流已为最大流。最大流量为无法标号，不存在增广链，此可行流已为最大流。最大流量为14。