图与网络分析精.ppt

《图与网络分析精.ppt》由会员分享，可在线阅读，更多相关《图与网络分析精.ppt（160页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、图与网络分析图与网络分析第1页，本讲稿共160页近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七城的七座桥，要求每座桥通过一次且仅通过一次。座桥，要求每座桥通过一次且仅通过一次。这就是著名的这就是著名的“哥尼斯哥尼斯堡堡 7 桥桥”难题。难题。Euler1736年证明了不可能存在这样的路线。年证明了不可能存在这样的路线。第一节第一节 图的基本概念与模型图的基本概念与模型KnigsbergKnigsberg桥对应的图桥对应的图第2页，本讲稿共160页例例1、有甲、乙、丙、丁、戊五个球队，、有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况

2、也可以用图表示出来。它们之间比赛的情况也可以用图表示出来。V1V2V3V4V5e5e4e1e2e3e6e7一、图基本概念一、图基本概念第3页，本讲稿共160页例例2 某单位储存八种化学药品，其中某些某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映药品是不能存放在同一个库房里的。为了反映这个情况可以用点这个情况可以用点V1,V2,V8分别代表这八分别代表这八种药品，若药品种药品，若药品Vi和药品和药品Vj是不能存放在同是不能存放在同一个库房的，则在一个库房的，则在Vi和和Vj之间连一条线。之间连一条线。V1V2 V3 V4 V5 V8 V7 V6第4页，本讲稿共160页图

3、的表示方法：一般地，当用图论研究一个实际问题时，一般地，当用图论研究一个实际问题时，常以顶点（常以顶点（Vertex）表示要研究的对象，以）表示要研究的对象，以它们之间的连线，表示某种关系，这种连线它们之间的连线，表示某种关系，这种连线称为边（称为边（Edge），目的是为了解决某个极值），目的是为了解决某个极值问题。图中的点用问题。图中的点用v表示，边用表示，边用e表示。对每表示。对每条边可用它所连接的点表示，条边可用它所连接的点表示，记作：记作：e1=v1,v1;e2=v1,v2;第5页，本讲稿共160页运筹学中研究的图具有下列特征:强调点与点之间的关联关系，不讲究图的比例大小与形状；每条边

4、上赋有一个权；建立网络模型，求最大值或最小值。第6页，本讲稿共160页下图可以提出很多极值问题142653876 63162 7 433716第7页，本讲稿共160页v3e7e4e8e5e6e1e2e3v1v2v4v5 端点端点,关联边关联边,相邻相邻若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联关联边边。若点。若点vi、vj与同一条边关联，称点与同一条边关联，称点vi和和vj相邻；若边相邻；若边ei和和ej具有公共的端点，具有公共的端点，称边称边ei和和ej相邻相邻。二、关于图的另外一些名称和术语：二、

5、关于图的另外一些名称和术语：第8页，本讲稿共160页 环环,多重边多重边,简单图简单图如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如右图中边如右图中边e1为环。如果两个点之间多于一为环。如果两个点之间多于一条，称为条，称为多重边多重边，如右图中的，如右图中的e4和和e5，对无，对无环、无多重边的图称作环、无多重边的图称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5第9页，本讲稿共160页 次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为点相关联的边的数目称为点vi的的次次（也叫做度），记作（也叫做度），记作d

6、(vi)。右图。右图中中d(v1),d(v3)=5,d(v5)=1。次为奇。次为奇数的点称作数的点称作奇点奇点，次为偶数的点称作，次为偶数的点称作偶偶点点，次为，次为1的点称为的点称为悬挂点悬挂点，次为，次为0的点的点称作称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次:一个图的次等于各点的次之和。一个图的次等于各点的次之和。第10页，本讲稿共160页定理定理1 任何图中，顶点次数之和等于所有边数的任何图中，顶点次数之和等于所有边数的2倍。倍。定理定理2 任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，

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

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

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

10、，|E|=m，有，有n n阶方阶方矩阵矩阵A=(aij)n n，其中其中第15页，本讲稿共160页图的基本概念与模型图的基本概念与模型v5v1v2v3v4v64332256437例例6.2 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下第16页，本讲稿共160页对于赋权图对于赋权图G=(V,E),其中边其中边 有权有权 ,构造矩阵构造矩阵B=(bij)n n 其中：其中：2.2.权矩阵权矩阵权矩阵权矩阵第17页，本讲稿共160页v5v1v2v3v4v64332256437例例6.4 下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下:第18页，本讲稿共1

11、60页G=(V,E)矩阵表示矩阵表示A A 邻接矩阵邻接矩阵B 关联矩阵关联矩阵边边e=u,v 关联边关联边 端点端点 重重重重合合合合环环多重边多重边 平行边平行边平行边平行边简单图简单图不含不含不含不含多重图多重图含含含含点的次点的次点的次点的次 0 1 奇数奇数 偶数偶数 子图子图子子图图生生成成子子图图孤孤立立点点悬悬挂挂点点奇奇点点偶偶点点顶点数顶点数p边数边数q点边关系点边关系各种链的概念各种链的概念第19页，本讲稿共160页欧拉图与中国邮路问题欧拉图与中国邮路问题欧拉图欧拉图哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，哥尼斯堡（现名加里宁格勒）是欧洲一个城市，Pre

12、geiPregei河把河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如（如A A）出发，经过各桥一次且仅一次最后回到原地呢？）出发，经过各桥一次且仅一次最后回到原地呢？第20页，本讲稿共160页Cab图图 4-10 ad哥尼斯堡七桥问题第21页，本讲稿共160页acbd(b)第22页，本讲稿共160页 定理定理2 连通无向图连通无向图G为欧拉链的充要条件是它恰含两个奇次为欧拉链的充要条件是它恰含两个奇次顶点。顶点

13、。定义定义1.在连通无向图在连通无向图G中中,若存在经过每条边恰好一次的一个若存在经过每条边恰好一次的一个圈或一条链圈或一条链,就称此圈或链就称此圈或链 为欧拉圈或欧拉链。若图为欧拉圈或欧拉链。若图G含一条欧含一条欧拉圈，则称为欧拉图。拉圈，则称为欧拉图。定理定理1 连通无向图连通无向图G为欧拉图的充要条件是它的全部顶点都为欧拉图的充要条件是它的全部顶点都是偶次顶点。（是偶次顶点。（G中无奇次顶点）中无奇次顶点）第23页，本讲稿共160页欧拉链欧拉链欧拉图欧拉图第24页，本讲稿共160页中国邮路问题中国邮路问题第25页，本讲稿共160页定理定理3 使图使图G成为总权最小的欧拉图的充要条件是：成

14、为总权最小的欧拉图的充要条件是：（1）在有奇次顶点的图在有奇次顶点的图G中，通过加重复边的方法使图不再中，通过加重复边的方法使图不再包含奇次顶点，但原图的每条边最多只能加一条重复边。包含奇次顶点，但原图的每条边最多只能加一条重复边。（2）在图在图G的每个回路上，重复边之总权不超过该回路非重复边之的每个回路上，重复边之总权不超过该回路非重复边之总权。（或回路总长的一半）总权。（或回路总长的一半）第26页，本讲稿共160页 例例1 试为图试为图4-13（a)构成总权最小的欧拉图。图中构成总权最小的欧拉图。图中线旁的数字为相应边的权。线旁的数字为相应边的权。124332124（a)图图4-13第27

15、页，本讲稿共160页例例2 试为图试为图4-14（a）所示的街道规划最优投递路线。）所示的街道规划最优投递路线。解：可按以上所述步骤进行，最终结果示于图解：可按以上所述步骤进行，最终结果示于图4-14（b)，总，总权等于权等于52，重复边的长度等于，重复边的长度等于10。1334333333222图图4-14（a）2第28页，本讲稿共160页413 333333 322 图图4-14（b）22第29页，本讲稿共160页第二节第二节 树树树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。广泛。例例6.2 乒乓求单打比

16、赛抽签后，可用图来表示相遇情况，如下乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。图所示。AB CDEF GH运动员运动员第30页，本讲稿共160页例例6.3 某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科第31页，本讲稿共160页 树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n 个顶点的树必有个顶点的树必

17、有n-1 条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。一个圈。v1v2v3v4v5v6第32页，本讲稿共160页 图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一

18、般图G1含有多个含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2第33页，本讲稿共160页 例如，图例如，图4-18（a）是一个有四个顶点（）是一个有四个顶点（n=4）的连通图，它共有的连通图，它共有 nn-2=42=16个生成树。个生成树。V1V2V3V4图图4-18（a）第34页，本讲稿共160页第35页，本讲稿共160页第36页，本讲稿共160页a ab bc cf fe ed dh hg gb bf fe ed d第37页，本讲稿共16

19、0页a ab bc cf fe ed dh hg gb bf fd dg g第38页，本讲稿共160页b bc ce ed da ab bc cf fe ed dh hg g第39页，本讲稿共160页a ab bc ch ha ab bc cf fe ed dh hg g第40页，本讲稿共160页a af fd dg ga ab bc cf fe ed dh hg g第41页，本讲稿共160页赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：

20、任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=5第42页，本讲稿共160页v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=15第43页，本讲稿共160页避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618第44页，本讲稿共160页v1v2v

21、3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15第45页，本讲稿共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636练习：练习：练习：练习：应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树第46页，本讲稿共160页v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23

22、=57第47页，本讲稿共160页课堂练习：课堂练习：课堂练习：课堂练习：3749346321Min C(T)=12Min C(T)=15254173314475答案：答案：第48页，本讲稿共160页34122323242Min C(T)=12213638534567454321Min C(T)=18第49页，本讲稿共160页 一一某一点到另一点的最短路的某一点到另一点的最短路的Dijkstra法法二二所有点对间的最短路所有点对间的最短路 返回返回第三节 最短路问题第50页，本讲稿共160页就是从给定的网络图中找出一点到各点或任意两点之就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一

23、条路间距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。短路的问题。因此这类问题在生产实际中得到广泛应用。第51页，本讲稿共160页 里特城里特城（Littletown）是一个乡村的小镇。它的消防队要）是一个乡村的小镇。它的消防队要为包括许多农场社区在内大片的地区提供服务。在这个地区为包括许多农场社区在内大片的地区提供服务。在这个地区里有很多道路，从消防站到任何一个社区都有很多条路线

24、。里有很多道路，从消防站到任何一个社区都有很多条路线。因为时间是一个到达火灾发生点的主要因素，所以消防队队因为时间是一个到达火灾发生点的主要因素，所以消防队队长希望事先能够确定从消防站到每一个农场社区的最短路。长希望事先能够确定从消防站到每一个农场社区的最短路。例子：里特城例子：里特城 的消防队问题的消防队问题第52页，本讲稿共160页第53页，本讲稿共160页最短路：最短路：O A B E F T 19 英里英里第54页，本讲稿共160页一、一、求最短路的Dijkstra算法 1、算法的基本思想、算法的基本思想第55页，本讲稿共160页2.有向图的狄克斯屈拉有向图的狄克斯屈拉(Dijkstr

25、a)标号算法步骤标号算法步骤点标号：点标号：p(vj)起点起点vs到点到点vj的最短路长；的最短路长；边标号：边标号：a(i，j)=p(i)+lij，步骤：步骤：(1)令起点的标号；令起点的标号；p(vs)0。先求有向图的最短路，设网络图的起点是先求有向图的最短路，设网络图的起点是vs,终点是终点是vt ,以以vi为起点为起点vj为终点的弧记为（为终点的弧记为（i，j）,距离为距离为lij(2)找出所有找出所有vi已标号已标号vj未标号的弧集合未标号的弧集合 Ai=(i，j)，如果这样的弧，如果这样的弧不存在或不存在或vt已标号则计算结束；已标号则计算结束；(3)计算集合计算集合Ai中弧中弧的

26、标号：的标号：a(i，j)=p(i)+lij(4)选一个点标号选一个点标号 返回到第返回到第(2)步。步。第56页，本讲稿共160页610123214675811165图图519【例【例5-1】图】图51中的权中的权cij表示表示vi到到vj的距离（费用、时间），从的距离（费用、时间），从v1修一修一条公路或架设一条高压线到条公路或架设一条高压线到v7，如何选择一条路线使距离最短，建立该，如何选择一条路线使距离最短，建立该问题的网络数学模型。问题的网络数学模型。第57页，本讲稿共160页【解】【解】设设xij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，

27、不选择弧，不选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短路问题的网络模型：第58页，本讲稿共160页610123214675811165图图51961012920p(9,v2)18P（6,V1）16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)【例【例5-1】用】用Dijkstra算法求图算法求图51 所示所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：的最短路为：p17=v1,v2,v3,v5,v7，最短路长为，最短路长为L17=29 14P（0,V1）第59页，本讲稿共160页6101232146758

28、11165图图51961012920p(9,v2)18P（6,V1）16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)v1 到到v7的最短路为：的最短路为：p17=v1,v2,v3,v5,v7，最短路长为，最短路长为L17=29 14P（0,V1）第60页，本讲稿共160页从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短到该点的最短路线及最短距离，因此可以将每个点标号，求出距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个到任意点的最短路线，如果某个点点vj不能标号，说明不能标号，说明vs

29、不可达不可达vj。第61页，本讲稿共160页【例【例6-5】求图】求图6-10所示所示v1到各点的最短路及最短距离到各点的最短路及最短距离452617839326121618P(0,v1)452P(2,v1)310P(3,v1)96126P(4,v1)11P(6,v3)P(6,v3)1881224P(8,v5)24P(18,v5)所有点都已标号，点上的标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是到该点的最短距离，最短路线就是红色的链。红色的链。图图6-103.无向图最短路的求法无向图最短路的求法第62页，本讲稿共160页Dijkstra最短路算法的最短路算法的特点特

30、点和和适应范围适应范围每次迭代只有一个节点获得标号，若有两个或两个以上节点的临时标号同时最小，可任选一个标号；标号Pj 表示 vs 到 vj 的最短路，第 k 次迭代得到的永久标号，最多有n1 次迭代；可以应用于简单有向图和混合图，在临时标号时，所谓相邻必须是箭头指向的节点；若第 n1 次迭代后仍有节点的标号为，则表明 vs 到该节点无有向路径；vs 到所有点的最短路也是一棵生成树，但不是最小生成树这个算法只设用于全部权为非负情况,如果某边上权为负的,算法失效;当vi与vj两点之间至少有两条边相关联时，留下一条最短边，去掉其它关联边。第63页，本讲稿共160页1024149135787v1v2

31、v3v4v5v6 例例 求下图所示网络之顶点求下图所示网络之顶点1至至6的最短路和最短路长。的最短路和最短路长。P（0，v1）P（10，v1）P（15，v2）P（22，v5）P（22，v5）P（23，v2）第64页，本讲稿共160页142653876 63162 7 433716第65页，本讲稿共160页二、所有点对间的最短路Floyd算法 1、写出图的权矩阵写出图的权矩阵 第66页，本讲稿共160页步骤：步骤：、输入权矩阵（）；、对n个顶点的图G,该方法迭代n步结束，第k次迭代的矩阵Dk的元素dij(k)按下式选取 dij(k)=mindij(k-1),dik(k-1）+dkj(k-1）其中

32、，i,j=1,2,3,n。但当i=k或j=k时，dij(k)=dij(k-1).。、（）中的元素就是到的最短路长。第67页，本讲稿共160页v1v3v4v2v5512310655228442例例 求下图所示网络图各点对间的最短路和最短路长求下图所示网络图各点对间的最短路和最短路长。第68页，本讲稿共160页第69页，本讲稿共160页第70页，本讲稿共160页第71页，本讲稿共160页第72页，本讲稿共160页23147 4 32 910例例 求下图所示网络图各点对间的最短路和最短路长求下图所示网络图各点对间的最短路和最短路长。第73页，本讲稿共160页课堂练习：课堂练习：1.用用Dijkstr

33、a算法求下图从算法求下图从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：第74页，本讲稿共160页2.求从求从v1到到v8的最短路径的最短路径237184566134105275934682第75页，本讲稿共160页237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为10第76页，本讲稿共160页最短路问题的应用：最短路问题的应用：例例6.7 电信公司准备在甲、乙两地沿路架设

34、一条光缆线，问电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。图。权数表示两地间公路的长度（单位：公里）。v1（甲地）（甲地）1517624431065v2v7(乙地乙地)v3v4v5v6第77页，本讲稿共160页解：这是一个求无向图的最短路的问题。解：这是一个求无向图的最短路的问题。第78页，本讲稿共160页第四节第四节 网络最大流网络最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使生产地到销售地的产品输送量最大。

35、这就是一个网络最大流问题。这就是一个网络最大流问题。第79页，本讲稿共160页实例：实例：公司公司 的最大流问题的最大流问题 公司是欧洲一家生产豪华汽车的制造商。公司是欧洲一家生产豪华汽车的制造商。虽然它生产的汽车在所有发达国家的销量都不错，虽然它生产的汽车在所有发达国家的销量都不错，但是对于这家公司来说，出口到美国显得尤其重要。但是对于这家公司来说，出口到美国显得尤其重要。公司因为提供优质的服务而获得很好的公司因为提供优质的服务而获得很好的 声誉，保持这个声誉一个很重要的秘诀是它有着充裕的声誉，保持这个声誉一个很重要的秘诀是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商和汽车配

36、件供应，从而能够随时供货给公司众多的经销商和授权维修店。这些供应件主要存放在公司的配送中心里，授权维修店。这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即送货。卡尔需要优先考虑的是改这样一有需求就可以立即送货。卡尔需要优先考虑的是改进这些配送中心的不足之处。进这些配送中心的不足之处。背背景景第80页，本讲稿共160页 该公司在美国有几个配送中心。但是，离洛杉矾中心最该公司在美国有几个配送中心。但是，离洛杉矾中心最近的一个配送中心却坐落在离洛杉矾近的一个配送中心却坐落在离洛杉矾1000 多英里的西雅图。多英里的西雅图。由于的汽车在加利福尼亚越来越受欢迎，所以保证由于的汽车在加利福尼亚

37、越来越受欢迎，所以保证洛杉矾中心良好的供应就显得尤为重要了。因此，现在那里洛杉矾中心良好的供应就显得尤为重要了。因此，现在那里的供应不断减少的现状成为了公司高层管理真正关心的问的供应不断减少的现状成为了公司高层管理真正关心的问题题正如现在卡尔深切领会到了一样。正如现在卡尔深切领会到了一样。大部分的汽车配件以及新车是在该公司坐落于德国斯图大部分的汽车配件以及新车是在该公司坐落于德国斯图加特的总厂和新车一起生产的。也就是这家工厂向洛杉矾加特的总厂和新车一起生产的。也就是这家工厂向洛杉矾中心供应汽车配件。由于其中的一些配件体积很大，某些中心供应汽车配件。由于其中的一些配件体积很大，某些配件的需求量很

38、多，这就使得供应的总量非常庞大配件的需求量很多，这就使得供应的总量非常庞大每每月有超过月有超过300，000立方英尺的配件需要运到。现在，下个立方英尺的配件需要运到。现在，下个月需要多得多的数量以补充正在减少的库存。月需要多得多的数量以补充正在减少的库存。第81页，本讲稿共160页 卡尔需要尽快做出一个方案，使得下个月从总厂运送卡尔需要尽快做出一个方案，使得下个月从总厂运送到洛杉矾配送中心的供应件尽可能的多。他已经认识到了到洛杉矾配送中心的供应件尽可能的多。他已经认识到了这是个最大流问题这是个最大流问题一个使得从总厂运送到洛杉矾配送一个使得从总厂运送到洛杉矾配送中心的配件流最大的问题。因为总厂

39、生产的配件量远远要中心的配件流最大的问题。因为总厂生产的配件量远远要大于能够运送到配送中心的量，所以，可以运送多少配件大于能够运送到配送中心的量，所以，可以运送多少配件的限制条件就是该公司配送网络的容量。的限制条件就是该公司配送网络的容量。问题问题第82页，本讲稿共160页第83页，本讲稿共160页LASTLIROBONONY 806070405030507040BMZ的网络模型，图中的数字代表该弧的容量的网络模型，图中的数字代表该弧的容量第84页，本讲稿共160页 一一 基本概念基本概念二二 求最大流的标号法求最大流的标号法返回第85页，本讲稿共160页如图如图4-23 是联接某产品产地是联

40、接某产品产地v1和销售地和销售地v6点点的交通网。的交通网。st4844122679第86页，本讲稿共160页st4，38,44,04,21,12,22,26,07,49,3第87页，本讲稿共160页一、基本概念：一、基本概念：1.1.容量网络：容量网络：容量网络：容量网络：对网络上的每条弧对网络上的每条弧(vi,vj)都给出一个最大的通都给出一个最大的通过能力，称为该弧的过能力，称为该弧的容量容量容量容量，简记为，简记为cij。容量网络中通常规定。容量网络中通常规定一个一个发点发点发点发点(也称源点，记为也称源点，记为s)和一个和一个收点收点收点收点(也称汇点，记为也称汇点，记为t)，网络中

41、其他点称为网络中其他点称为中间点中间点中间点中间点。st4844122679第88页，本讲稿共160页2.网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流与可行流 流流是指加在网络各条弧上的实际流量，记为是指加在网络各条弧上的实际流量，记为fij。若。若fij=0，称为零流。称为零流。第89页，本讲稿共160页在网络中满足下述条件的流为可行流：在网络中满足下述条件的流为可行流：（1 1）、容量限制条件：）、容量限制条件：0 0 f fij ij c cijij （2 2）、）、平衡条件：平衡条件：第90页，本讲

42、稿共160页结论：任何网络上一定存在可行流。（零流即是可结论：任何网络上一定存在可行流。（零流即是可行流）行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使F值达到最大。值达到最大。第91页，本讲稿共160页 割与割集割与割集割是指容量网络中的发点和收点分割开，并使割是指容量网络中的发点和收点分割开，并使st的流中断的一的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用组弧的集合。割容量是组成割集合中的各条弧的容量之和，用 表示。表示。如下图中，如下图中，AA将网络上的点分割成将网络上的点分割成 两个集合。

43、并有两个集合。并有 ，称弧的集合称弧的集合=(vs,v3),(v2,v4),(v2,v5)是一个割。是一个割。第92页，本讲稿共160页（S，）=(vs,v3),(v2,v4),(v2,v5)割容量割容量是：是：9+6+5=20第93页，本讲稿共160页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）第94页，本讲稿共160页定理定理定理定理1 1 在网络中在网络中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即：v(f)=c(V,V)第95页，本讲稿共160

44、页流量可增链流量可增链流量可增链流量可增链在网络的发点和收点之间能找到一条链，在该链上所在网络的发点和收点之间能找到一条链，在该链上所有指向为有指向为st的弧，称为前向弧，记作的弧，称为前向弧，记作+,存在存在f0，则称这样的链为，则称这样的链为增广链。例如下图中，增广链。例如下图中，sv2v1v3v4t。定理定理定理定理3 3 网络网络N中的流中的流 F是最大流当且仅当是最大流当且仅当N中不包含任何增广链中不包含任何增广链第96页，本讲稿共160页二、求网络最大流的标号法二、求网络最大流的标号法 基本思想基本思想基本思想基本思想 由一个流开始，系统地搜寻增广链，然后在此链上增由一个流开始，系

45、统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。流，继续这个增流过程，直至不存在增广链。基本方法基本方法基本方法基本方法(1)找出第一个可行流，（例如所有弧的流量找出第一个可行流，（例如所有弧的流量fij=0。）。）(2)用标号的方法找一条增广链用标号的方法找一条增广链 首先给发点首先给发点s标号标号(),标号中的数字表示允许的最大调整量。标号中的数字表示允许的最大调整量。选择一个点选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点已标号并且另一端未标号的弧沿着某条链向收点检查：检查：第97页，本讲稿共160页 如果弧的起点为如果弧的起点为vi，并且有，并且有f

46、ij0，则，则vj标号标号(fji)(3)重复第重复第(2)步，可能出现两种结局：步，可能出现两种结局：标号过程中断，标号过程中断，t无法标号，说明网络中不存在流量可增链，目无法标号，说明网络中不存在流量可增链，目前流量为最大流。同时可以确定最小割集，前流量为最大流。同时可以确定最小割集，记已标号的点集为记已标号的点集为V,未标号的点集合为未标号的点集合为V,(V,V)为网络的最小割。为网络的最小割。t得到标号，反向追踪在网络中找到一条从得到标号，反向追踪在网络中找到一条从s到到t得由标号点及相应的得由标号点及相应的弧连接而成的流量可增链。继续第弧连接而成的流量可增链。继续第(4)步步第98页

47、，本讲稿共160页(4)修改流量。设原图可行流为修改流量。设原图可行流为f，令，令得到网络上一个新的可行流得到网络上一个新的可行流F。(5)擦除图上所有标号，重复擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何流量可步，直到图中找不到任何流量可增链，计算结束。增链，计算结束。第99页，本讲稿共160页例例6.10 用标号算法求下图中用标号算法求下图中st的最大流量，并找出最小割。的最大流量，并找出最小割。stv1v3v2v48,79,35,410,86,12,09,95,47,5第100页，本讲稿共160页解：解：(1)先给先给s标号标号()stv1v3v2v48,79,35,410

48、,86,12,09,95,47,5(0,)F0=12第101页，本讲稿共160页stv1v3v2v48,79,35,410,86,12,09,95,47,5(0)(2)检查与检查与s点相邻的未标号的点，因点相邻的未标号的点，因fs1cs1，故对，故对v1标号标号=min,cs1-fs1=1,(s,1)第102页，本讲稿共160页stv1v3v2v48,79,35,410,86,12,0,9,95,47,6(0,)(s,1)(2)检查与检查与v1点相邻的未标号的点，因点相邻的未标号的点，因f13c13，故对，故对v3标号标号=min1,c13-f13=min1,6=1(v1,1)第103页，本讲

49、稿共160页stv1v3v2v48,79,35,410,86,12,09,95,47,5(0,)(s,1)(v1,1)(3)检查与检查与v3点相邻的未标号的点，因点相邻的未标号的点，因f3t0，若，若cij-fij=0当作为反向弧使用时：当作为反向弧使用时：bij-=-bij，若，若fij0，若，若fij=0为了便于计算和检查，常在每条弧上依次注出以下四个数字：为了便于计算和检查，常在每条弧上依次注出以下四个数字：(1)弧容量弧容量cij；(2)弧流量弧流量fij；(3)bij+（作为正向弧使用时在其上流过（作为正向弧使用时在其上流过单位物品的费用）；单位物品的费用）；(4)bij-（作为反向

50、弧使用时在其上流过单位物品（作为反向弧使用时在其上流过单位物品的费用）。的费用）。.以以bij+或或bij-弧弧aij的权（弧长），用的权（弧长），用Dijkstra算法求算法求vsVi的最短路的最短路P。4.取增流量取增流量min=minijaijP第121页，本讲稿共160页对对P上的各弧增流，这里的上的各弧增流，这里的ij为弧为弧ij的流量可增值。的流量可增值。5.转回第转回第2步，直至每步，直至每3步求不出有限长的最短路为止。步求不出有限长的最短路为止。这时已得到最小费用的最大流。这时已得到最小费用的最大流。例例12求下图网络的最小费用最大流，各弧的容量（弧旁的求下图网络的最小费用最大