1、第第5章章 图与网络分析图与网络分析(Graph Theory and Network Analysis)图的基本概念与模型图的基本概念与模型树树最短路问题最短路问题网络的最大流网络的最大流最小费用流最小费用流应用举例应用举例近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg城的七座桥，要求每座桥通过一次且仅通过一次。城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Euler1736年证明了不年证明了不可能存在这样的路线。可能存在这样的路线。第一节第一节 图的基本概念与模型图的基本
2、概念与模型例例1、有甲、乙、丙、丁、戊五个球队，、有甲、乙、丙、丁、戊五个球队，它们之间比赛的情况也可以用图表示出来。它们之间比赛的情况也可以用图表示出来。V1V2V3V4V5e5e4e1e2e3e6e7一、图基本概念一、图基本概念例例2 某单位储存八种化学药品，其中某些某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映药品是不能存放在同一个库房里的。为了反映这个情况可以用点这个情况可以用点V1,V2,V8分别代表这八分别代表这八种药品，若药品种药品，若药品Vi和药品和药品Vj是不能存放在同是不能存放在同一个库房的，则在一个库房的，则在Vi和和Vj之间连一条线。之间连一条
3、线。V1V2 V3 V4 V5 V8 V7 V6图的表示方法：一般地，当用图论研究一个实际问题时，一般地，当用图论研究一个实际问题时，常以顶点（常以顶点（Vertex）表示要研究的对象，以）表示要研究的对象，以它们之间的连线，表示某种关系，这种连线它们之间的连线，表示某种关系，这种连线称为边（称为边（Edge），目的是为了解决某个极值），目的是为了解决某个极值问题。图中的点用问题。图中的点用v表示，边用表示，边用e表示。对每表示。对每条边可用它所连接的点表示，条边可用它所连接的点表示，记作：记作：e1=v1,v1;e2=v1,v2;,EVG 强调点与点之间的关联关系，不讲究图的比例大小与形状；
4、每条边上赋有一个权；建立网络模型，求最大值或最小值。142653876 63162 7 433716v3e7e4e8e5e6e1e2e3v1v2v4v5 端点端点,关联边关联边,相邻相邻若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联边关联边。若点。若点vi、vj与同一条边关与同一条边关联，称点联，称点vi和和vj相邻；若边相邻；若边ei和和ej具具有公共的端点，称边有公共的端点，称边ei和和ej相邻相邻。二、关于图的另外一些名称和术语：二、关于图的另外一些名称和术语：环环,多重边多重边,简单图简单图如果边
5、如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。如右图中边。如右图中边e1为环。如果两个点为环。如果两个点之间多于一条，称为之间多于一条，称为多重边多重边，如右图，如右图中的中的e4和和e5，对无环、无多重边的图，对无环、无多重边的图称作称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5 次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为相关联的边的数目称为点点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)。右图中右图中d(v1),d(v3)=5,d(v5)=1。次。次为奇数的点称作为奇数的点称作奇点奇点，次为
6、偶数的，次为偶数的点称作点称作偶点偶点，次为，次为1的点称为的点称为悬挂点悬挂点，次为次为0的点称作的点称作孤立点孤立点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次:一个图的次等于各点的次之和。一个图的次等于各点的次之和。定理定理1 任何图中，顶点次数之和等于所有边数的任何图中，顶点次数之和等于所有边数的2倍。倍。定理定理2 任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的均被计算了两次，所以顶
7、点次数的总和等于边数的2倍。倍。证明：设证明：设V1和和V2分别为图分别为图G中奇点与偶点的集合。由定理中奇点与偶点的集合。由定理1可得：可得：mvdvdvdVvVvVv2)()()(21 2m为偶数，且偶点的次之和为偶数，且偶点的次之和 也为偶数，所以也为偶数，所以 必为偶必为偶数，即奇数点的个数必为偶数。数，即奇数点的个数必为偶数。2)(Vvvd 1)(Vvvd 链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其图中某些点和边的交替序列，若其中各边互不相同，且对任意中各边互不相同，且对任意vi,t-1和和vit均相邻称为均相邻称为链链。用。用 表示：表示：v3e7e4e8e5e6e
8、1e2e3v1v2v4v5,110kkvevev 起点与终点重合的链称作起点与终点重合的链称作圈圈。如。如果每一对顶点之间至少存在一条果每一对顶点之间至少存在一条链，称这样的图为链，称这样的图为连通图连通图，否则，否则称图不连通。称图不连通。子图，部分图子图，部分图(支撑子图支撑子图)图图G1=V1、E1和图和图G2=V2，E2如果有如果有 称称G1是是G2的一个的一个子图子图。若有若有 ，则称，则称G1是是G2的一的一个个部分图部分图(支撑子图支撑子图)。2121EEVV 和和2121EEVV，v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e
9、8e6e2e3v1v2v4v5(a)(b)（G图）图）网络（赋权图）网络（赋权图）赋权图）赋权图）:权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等。等等。无向网络无向网络:端点无序的赋权图称为端点无序的赋权图称为.有向网络有向网络:端点有序的赋权图称为端点有序的赋权图称为。910201571419256 图的矩阵描述：图的矩阵描述：邻接矩阵、关联矩阵、权矩阵等。邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵邻接矩阵对于图对于图G=（V，E），），|V|=n，|E|=m，有，有n n阶方矩阵阶方矩阵A=(aij)n n，其中，其中 其它其它之间有关联边时之间有关联边时与
10、与当且仅档当且仅档0vv1jiija图的基本概念与模型图的基本概念与模型v5v1v2v3v4v64332256437 010101101001010111101010001101111010 65432166654321vvvvvvAvvvvvv例例6.2 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如下对于赋权图对于赋权图G=(V,E),其中边其中边 有权有权 ,构造矩阵构造矩阵B=(bij)n n 其中：其中：),(jivvjiw EvvEvvwbjijijiji),(0),(654321654321 030303302004020576305020007204346
11、040vvvvvvvvvvvvB v5v1v2v3v4v64332256437例例6.4 下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下:G=(V,E)邻接矩阵邻接矩阵 关联矩阵关联矩阵边边e=u,v 关联边关联边 端点端点 环环多重边多重边 简单图简单图多重图多重图 0 1 奇数奇数 偶数偶数 子图子图子子图图生生成成子子图图孤孤立立点点悬悬挂挂点点奇奇点点偶偶点点顶点数顶点数p边数边数q点边关系点边关系各种链的概念各种链的概念欧拉图与中国邮路问题欧拉图与中国邮路问题欧拉图欧拉图Cabd哥尼斯堡七桥问题acbd(b)定理定理2 连通无向图连通无向图G为欧拉链的充要条件是它
12、恰含两个奇次为欧拉链的充要条件是它恰含两个奇次顶点。顶点。定义定义1.在连通无向图在连通无向图G中中,若存在经过每条边恰好一次的一个若存在经过每条边恰好一次的一个圈或一条链圈或一条链,就称此圈或链就称此圈或链 为欧拉圈或欧拉链。若图为欧拉圈或欧拉链。若图G含一条欧含一条欧拉圈，则称为欧拉图。拉圈，则称为欧拉图。定理定理1 连通无向图连通无向图G为欧拉图的充要条件是它的全部顶点都为欧拉图的充要条件是它的全部顶点都是偶次顶点。（是偶次顶点。（G中无奇次顶点）中无奇次顶点）欧拉链欧拉链欧拉图欧拉图中国邮路问题中国邮路问题定理定理3 使图使图G成为总权最小的欧拉图的充要条件是：成为总权最小的欧拉图的充
13、要条件是：（1）在有奇次顶点的图在有奇次顶点的图G中，通过加重复边的方法使图中，通过加重复边的方法使图不再包含奇次顶点，但原图的每条边最多只能加一条重不再包含奇次顶点，但原图的每条边最多只能加一条重复边。复边。（2）在图在图G的每个回路上，重复边之总权不超过该回路的每个回路上，重复边之总权不超过该回路非重复边之总权。（或回路总长的一半）非重复边之总权。（或回路总长的一半）例例1 试为图试为图4-13（a)构成总权最小的欧拉图。图中构成总权最小的欧拉图。图中线旁的数字为相应边的权。线旁的数字为相应边的权。124332124（a)图图4-13例例2 试为图试为图4-14（a）所示的街道规划最优投递
14、路线。）所示的街道规划最优投递路线。解：可按以上所述步骤进行，最终结果示于图解：可按以上所述步骤进行，最终结果示于图4-14（b)，总，总权等于权等于52，重复边的长度等于，重复边的长度等于10。1334333333222图图4-14（a）2413 333333 322 图图4-14（b）22第二节第二节 树树树是图论中结构最简单但又十分重要的图。在自然和社会领树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。域应用极为广泛。例例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。下图所示。AB CDEF GH运动员运
15、动员例例6.3 某企业的组织机构图也可用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科 树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n 个顶点的树必有个顶点的树必有n-1 条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任一条边，必变为不连通。：树连通，但去
16、掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。得到一个圈。v1v2v3v4v5v6 图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树的部分树（或支撑树）。树图的各条边称为树枝，一般图（或支撑树）。树图的各条边称为树枝，一般图G1含有多含有多个部分树，其中树枝总长最小的部分树，称为该图的最小个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v
17、5G1G2 例如，图例如，图4-18（a）是一个有四个顶点（）是一个有四个顶点（n=4）的连通图，它共有的连通图，它共有 nn-2=42=16个生成树。个生成树。V1V2V3V4图图4-18（a）破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=5v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=15避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不
18、能形成加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=153749346321Min C(T)=12Min C(T)=15254173314475答案：答案：34122323242Min C(T)=12213638534567454321Min C(T)=18 1某一点到另一点的最短路的某一点到另一点的最短路的Dijkstra法法2所有点对间的最短路所有点对间的最短路 返回返回第三节 最短路问题
19、就是从给定的网络图中找出一点到各点或任意两点之间就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路距离最短的一条路.有些问题，如选址、管道铺设时的选线、设备更新、投有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。路的问题。因此这类问题在生产实际中得到广泛应用。里特城里特城（Littletown）是一个乡村的小镇。它的）是一个乡村的小镇。它的消防队要为包括许多农场社区在内大片的地区提供消防队要为包括许多农场社区在内大片的地区提供服务
20、。在这个地区里有很多道路，从消防站到任何服务。在这个地区里有很多道路，从消防站到任何一个社区都有很多条路线。因为时间是一个到达火一个社区都有很多条路线。因为时间是一个到达火灾发生点的主要因素，所以消防队队长希望事先能灾发生点的主要因素，所以消防队队长希望事先能够确定从消防站到每一个农场社区的最短路。够确定从消防站到每一个农场社区的最短路。例子：里特城例子：里特城 的消防队问题的消防队问题最短路：最短路：O A B E F T 19 英里英里一、一、1、算法的基本思想、算法的基本思想一种标号的迭代过程具体算法是在图上进行的最短路是到的最短路是到则的最短路是到则的最短路经过点到终点若起点nnnnn
21、nnnnnsvvpvvvvvpvvvvvvpvvvvvvv,3333222321113212.有向图的狄克斯屈拉有向图的狄克斯屈拉(Dijkstra)标号算法步骤标号算法步骤点标号：点标号：p(vj)起点起点vs到点到点vj的最短路长；的最短路长；边标号：边标号：a(i，j)=p(i)+lij，步骤：步骤：(1)令起点的标号；令起点的标号；p(vs)0。先求有向图的最短路，设网络图的起点是先求有向图的最短路，设网络图的起点是vs,终点是终点是vt ,以以vi为起为起点点vj为终点的弧记为（为终点的弧记为（i，j）,距离为距离为lij(2)找出所有找出所有vi已标号已标号vj未标号的弧集合未标号
22、的弧集合 Ai=(i，j)，如果这，如果这样的弧不存在或样的弧不存在或vt已标号则计算结束；已标号则计算结束；(3)计算集合计算集合Ai中弧中弧的标号：的标号：a(i，j)=p(i)+lij(4)选一个点标号选一个点标号 返回到第返回到第(2)步。步。)(,),(|),(min)(kpvAijijiavpkjk处标号在终点610123214675811165图图519【例【例5-1】图】图51中的权中的权cij表示表示vi到到vj的距离（费用、时间），从的距离（费用、时间），从v1修一条公路或架设一条高压线到修一条公路或架设一条高压线到v7，如何选择一条路线使距离，如何选择一条路线使距离最短，
23、建立该问题的网络数学模型。最短，建立该问题的网络数学模型。【解】【解】设设xij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，不，不选择弧选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短路问题的网络模型：(,)12(,)(,)57131467min102,3,610(,)ijiji jEijkii jEk iEijZc xxxxxxixxxi jE或1，610123214675811165图图51961012920p(9,v2)18P（6,V1）16P(12,v1)17P(16,v3)2432P(18,v3)29P(29,v5)【例【例
24、5-1】用】用Dijkstra算法求图算法求图51 所示所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：的最短路为：p17=v1,v2,v3,v5,v7，最短路长为，最短路长为L17=29 14P（0,V1）610123214675811165图图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）从上例知，只要某点已标号，说明已找到起点从上例知，只
25、要某点已标号，说明已找到起点vs到该点的最短路到该点的最短路线及最短距离，因此可以将每个点标号，求出线及最短距离，因此可以将每个点标号，求出vs到任意点的最短到任意点的最短路线，如果某个点路线，如果某个点vj不能标号，说明不能标号，说明vs不可达不可达vj。【例【例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)所有点都已标号，点上的标号就是所有点都已标号，点上的标
26、号就是v1到该点的最短距离，最短路到该点的最短距离，最短路线就是红色的链。线就是红色的链。图图6-103.无向图最短路的求法无向图最短路的求法最短路算法的最短路算法的特点特点和和适应范围适应范围每次迭代只有一个节点获得标号，若有两个或两个以上节点的临时标号同时最小，可任选一个标号；标号Pj 表示 vs 到 vj 的最短路，第 k 次迭代得到的永久标号，最多有n1 次迭代；可以应用于简单有向图和混合图，在临时标号时，所谓相邻必须是箭头指向的节点；若第 n1 次迭代后仍有节点的标号为，则表明 vs 到该节点无有向路径；vs 到所有点的最短路也是一棵生成树，但不是最小生成树这个算法只设用于全部权为非
27、负情况,如果某边上权为负的,算法失效;当vi与vj两点之间至少有两条边相关联时，留下一条最短边，去掉其它关联边。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、写出图的权矩阵写出图的权矩阵 )()(不存在到的直达路线距离到jijiijijvvvvldnnijdD)(步骤：步骤：、输入权矩阵（）；、对n个顶点的图G,该
28、方法迭代n步结束，第k次迭代的矩阵Dk的元素dij(k)按下式选取 dij(k)=mindij(k-1),dik(k-1）+dkj(k-1）其中，i,j=1,2,3,n。但当i=k或j=k时，dij(k)=dij(k-1).。、（）中的元素就是到的最短路长。v1v3v4v2v5512310655228442例例 求下图所示网络图各点对间的最短路和最短路长求下图所示网络图各点对间的最短路和最短路长。044240628203221005215054321)0(vvvvvD0442403728203227605215041341221421354321)1(vvvvvD044274037252032
29、276057215052141341232521421312554321)2(vvvvvD04426403625203227605621405314134132325214213132513254321)4(vvvvvD04426403625203227605621405314134132325214213132513254321)3(vvvvvD04426403625203226605621405314134132325254213132513254321)5(vvvvvD04424037282032276052150111154321)1(vvvvvD23147 4 32 910例例 求下
30、图所示网络图各点对间的最短路和最短路长求下图所示网络图各点对间的最短路和最短路长。课堂练习：课堂练习：1.用用Dijkstra算法求下图从算法求下图从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：6521vvvv2.求从求从v1到到v8的最短路径的最短路径237184566134105275934682237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为10最短路问题的应用：
31、最短路问题的应用：例例6.7 电信公司准备在甲、乙两地沿路架设一条光缆线，问电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。图。权数表示两地间公路的长度（单位：公里）。v1（甲地）（甲地）1517624431065v2v7(乙地乙地)v3v4v5v6解：这是一个求无向图的最短路的问题。解：这是一个求无向图的最短路的问题。第四节第四节 网络最大流网络最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使生产地到销售地的产品输
32、送量最大。这就是一个网络最大流问题。这就是一个网络最大流问题。实例：实例：公司公司 的最大流问题的最大流问题 公司是欧洲一家生产豪华汽车的制造商。公司是欧洲一家生产豪华汽车的制造商。虽然它生产的汽车在所有发达国家的销量都不错，虽然它生产的汽车在所有发达国家的销量都不错，但是对于这家公司来说，出口到美国显得尤其重要。但是对于这家公司来说，出口到美国显得尤其重要。公司因为提供优质的服务而获得很好的公司因为提供优质的服务而获得很好的 声誉，保持这个声誉一个很重要的秘诀是它有着充裕的声誉，保持这个声誉一个很重要的秘诀是它有着充裕的汽车配件供应，从而能够随时供货给公司众多的经销商和汽车配件供应，从而能够
33、随时供货给公司众多的经销商和授权维修店。这些供应件主要存放在公司的配送中心里，授权维修店。这些供应件主要存放在公司的配送中心里，这样一有需求就可以立即送货。卡尔需要优先考虑的是改这样一有需求就可以立即送货。卡尔需要优先考虑的是改进这些配送中心的不足之处。进这些配送中心的不足之处。背背景景 该公司在美国有几个配送中心。但是，离洛杉矾中心最该公司在美国有几个配送中心。但是，离洛杉矾中心最近的一个配送中心却坐落在离洛杉矾近的一个配送中心却坐落在离洛杉矾1000 多英里的西雅图。多英里的西雅图。由于的汽车在加利福尼亚越来越受欢迎，所以保证由于的汽车在加利福尼亚越来越受欢迎，所以保证洛杉矾中心良好的供应
34、就显得尤为重要了。因此，现在那里洛杉矾中心良好的供应就显得尤为重要了。因此，现在那里的供应不断减少的现状成为了公司高层管理真正关心的问的供应不断减少的现状成为了公司高层管理真正关心的问题题正如现在卡尔深切领会到了一样。正如现在卡尔深切领会到了一样。大部分的汽车配件以及新车是在该公司坐落于德国斯图大部分的汽车配件以及新车是在该公司坐落于德国斯图加特的总厂和新车一起生产的。也就是这家工厂向洛杉矾加特的总厂和新车一起生产的。也就是这家工厂向洛杉矾中心供应汽车配件。由于其中的一些配件体积很大，某些中心供应汽车配件。由于其中的一些配件体积很大，某些配件的需求量很多，这就使得供应的总量非常庞大配件的需求量
35、很多，这就使得供应的总量非常庞大每每月有超过月有超过300，000立方英尺的配件需要运到。现在，下个立方英尺的配件需要运到。现在，下个月需要多得多的数量以补充正在减少的库存。月需要多得多的数量以补充正在减少的库存。卡尔需要尽快做出一个方案，使得下个月从总厂运送卡尔需要尽快做出一个方案，使得下个月从总厂运送到洛杉矾配送中心的供应件尽可能的多。他已经认识到了到洛杉矾配送中心的供应件尽可能的多。他已经认识到了这是个最大流问题这是个最大流问题一个使得从总厂运送到洛杉矾配送一个使得从总厂运送到洛杉矾配送中心的配件流最大的问题。因为总厂生产的配件量远远要中心的配件流最大的问题。因为总厂生产的配件量远远要大
36、于能够运送到配送中心的量，所以，可以运送多少配件大于能够运送到配送中心的量，所以，可以运送多少配件的限制条件就是该公司配送网络的容量。的限制条件就是该公司配送网络的容量。问题问题LASTLIROBONONY 806070405030507040BMZ的网络模型，图中的数字代表该弧的容量的网络模型，图中的数字代表该弧的容量 一一 基本概念基本概念二二 求最大流的标号法求最大流的标号法返回如图如图4-23 是联接某产品产地是联接某产品产地v1和销售地和销售地v6点点的交通网。的交通网。st4844122679st4，38,44,04,21,12,22,26,07,49,3一、基本概念：一、基本概念
37、：对网络上的每条弧对网络上的每条弧(vi,vj)都给出一个最大的通都给出一个最大的通过能力，称为该弧的过能力，称为该弧的，简记为，简记为cij。容量网络中通常规定。容量网络中通常规定一个一个(也称源点，记为也称源点，记为s)和一个和一个(也称汇点，记为也称汇点，记为t)，网络中其他点称为网络中其他点称为。st48441226792.网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流与可行流 流流是指加在网络各条弧上的实际流量，记为是指加在网络各条弧上的实际流量，记为fij。若若fij=0，称为零流。，称为零流。在
38、网络中满足下述条件的流为可行流：在网络中满足下述条件的流为可行流：（1 1）、容量限制条件：）、容量限制条件：0 0 f fij ij c cijij （2 2）、）、平衡条件：平衡条件：（终点）起点）titsisiffijijvBvjivAvijF,0(F)()(结论：任何网络上一定存在可行流。（零流即是结论：任何网络上一定存在可行流。（零流即是可行流）可行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使F值值达到最大。达到最大。割与割集割与割集割是指容量网络中的发点和收点分割开，并使割是指容量网络中的发点和收点分割开，
39、并使st的流中断的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用和，用 表示。表示。),(VVc ),(),(),(),(VVjijivvcVVc如下图中，如下图中，AA将网络上的点分割成将网络上的点分割成 两个集合。并两个集合。并有有 ，称弧的集合，称弧的集合=(vs,v3),(v2,v4),(v2,v5)是一个割。是一个割。VV,VtVs ,（S，）=(vs,v3),(v2,v4),(v2,v5)s割容量割容量是：是：9+6+5=20vsv2v3v4v5v6vt（4，0）（13，11）（5，5）（9，9）（5，4）（5，
40、5）（6，6）（5，2）（9，7）（4，4）（4，4）（10，9）在网络中在网络中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即：v(f)=c(V,V)在网络的发点和收点之间能找到一条链，在该链上所有在网络的发点和收点之间能找到一条链，在该链上所有指向为指向为st的弧，称为前向弧，记作的弧，称为前向弧，记作+,存在存在f0，则称这样的链为，则称这样的链为增广链。增广链。例如下图中，例如下图中，sv2v1v3v4t。网络网络N中的流中的流 F是最大流当且仅当是最大流当且仅当N中不包含任何增广中不包含任何增广链链二、求网络最大流的标号法二、求网络最大流的标号法由一个
41、流开始，系统地搜寻增广链，然后在此链上增流，由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。继续这个增流过程，直至不存在增广链。(1)找出第一个可行流，（例如所有弧的流量找出第一个可行流，（例如所有弧的流量fij=0。）。）(2)用标号的方法找一条增广链用标号的方法找一条增广链 首先给发点首先给发点s标号标号(),标号中的数字表示允许的最大调整量。标号中的数字表示允许的最大调整量。选择一个点选择一个点 vi 已标号并且另一端未标号的弧沿着某条链已标号并且另一端未标号的弧沿着某条链向收点检查：向收点检查：如果弧的起点为如果弧的起点为vi，并且有，并且有fij
42、0，则，则vj标号标号(fji)(3)重复第重复第(2)步，可能出现两种结局：步，可能出现两种结局：标号过程中断，标号过程中断，t无法标号，说明网络中不存在流量可增无法标号，说明网络中不存在流量可增链，目前流量为最大流。同时可以确定最小割集，链，目前流量为最大流。同时可以确定最小割集，记已标号记已标号的点集为的点集为V,未标号的点集合为未标号的点集合为V,(V,V)为网络的最小割。为网络的最小割。t得到标号，反向追踪在网络中找到一条从得到标号，反向追踪在网络中找到一条从s到到t得由标号得由标号点及相应的弧连接而成的流量可增链。继续第点及相应的弧连接而成的流量可增链。继续第(4)步步所有非增广链
43、上的弧对增广链上所有后向弧对增广链上所有前向弧FtFtFF)()(4)修改流量。设原图可行流为修改流量。设原图可行流为f，令，令得到网络上一个新的可行流得到网络上一个新的可行流F。(5)擦除图上所有标号，重复擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何步，直到图中找不到任何流量可增链，计算结束。流量可增链，计算结束。例例6.10 用标号算法求下图中用标号算法求下图中st的最大流量，并找出最小割。的最大流量，并找出最小割。v1v3v2v48,79,35,410,86,12,09,95,47,5解：解：(1)先给先给s标号标号()v1v3v2v48,79,35,410,86,12,0
44、9,95,47,5(0,)F0=12v1v3v2v48,79,35,410,86,12,09,95,47,5(0)(2)检查与检查与s点相邻的未标号的点，因点相邻的未标号的点，因fs1cs1，故对，故对v1标号标号=min,cs1-fs1=1,(s,1)v1v3v2v48,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)v1v3v2v48,79,35,410,86,12,09,95,47,5(0,)(s,1)(v1
45、,1)(3)检查与检查与v3点相邻的未标号的点，因点相邻的未标号的点，因f3t0，若，若cij-fij=0当作为反向弧使用时：当作为反向弧使用时：bij-=-bij，若，若fij0，若，若fij=0为了便于计算和检查，常在每条弧上依次注出以下四个数为了便于计算和检查，常在每条弧上依次注出以下四个数字：字：(1)弧容量弧容量cij；(2)弧流量弧流量fij；(3)bij+（作为正向弧使用时在（作为正向弧使用时在其上流过单位物品的费用）；其上流过单位物品的费用）；(4)bij-（作为反向弧使用时在其（作为反向弧使用时在其上流过单位物品的费用）。上流过单位物品的费用）。.以以bij+或或bij-弧弧
46、aij的权（弧长），用的权（弧长），用Dijkstra算法求算法求vsVi的最短路的最短路P。4.取增流量取增流量min=minijaijP对对P上的各弧增流，这里的上的各弧增流，这里的ij为弧为弧ij的流量可增值。的流量可增值。5.转回第转回第2步，直至每步，直至每3步求不出有限长的最短路为止。步求不出有限长的最短路为止。这时已得到最小费用的最大流。这时已得到最小费用的最大流。例例12求下图网络的最小费用最大流，各弧的容量（弧旁的求下图网络的最小费用最大流，各弧的容量（弧旁的第一个数字和通过单位物品的费用（弧旁的第二个数字）如图中第一个数字和通过单位物品的费用（弧旁的第二个数字）如图中所示。
47、所示。st4,16,65,22,33,26,46,3返回返回1、标号过程中，是否一定要对所有的顶点、标号过程中，是否一定要对所有的顶点全部逐个顺序标记？全部逐个顺序标记？2、如果可以同时得到若干条增广链是否可、如果可以同时得到若干条增广链是否可以同时调整流量？以同时调整流量？3、同一个问题每一次标号过程所寻找的、同一个问题每一次标号过程所寻找的增广链是否唯一？最大流是否唯一？最小增广链是否唯一？最大流是否唯一？最小割是否唯一？割是否唯一？4、对多发点、多收点的容量网络怎麽求、对多发点、多收点的容量网络怎麽求最大流？最大流？比赛安排问题比赛安排问题 有有5名运动员参加游泳比赛，下表给出了每位运名
48、运动员参加游泳比赛，下表给出了每位运动员参加的项目。问如何安排，才能使得每位运动动员参加的项目。问如何安排，才能使得每位运动员都不连续地参加比赛？员都不连续地参加比赛？第七节应用举例第七节应用举例游泳比赛运动员及参加项目游泳比赛运动员及参加项目运动员运动员 50m仰泳仰泳 50m蛙泳蛙泳 100m蝶泳蝶泳 100m自由泳自由泳 200m自由自由 泳泳A *B *v1v5v4v3v2 图图1 游泳比赛安排游泳比赛安排v4,v1,v2,v3,v5线路铺设问题线路铺设问题 下图是一个城镇的地图，现在要在该城镇的各地点间铺下图是一个城镇的地图，现在要在该城镇的各地点间铺设管道已知各点相互之间的铺设费用
49、（单位：千元），如何设管道已知各点相互之间的铺设费用（单位：千元），如何设计铺设线路，使各地互通的总铺设费用最少？设计铺设线路，使各地互通的总铺设费用最少？3871245257410679851其最小总费用为：其最小总费用为：31（千元）（千元）例例6.8 设备更新问题。某公司使用一台设备，在每年年初，设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，
50、但维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表设备每年年初的价格表年份年份12345年初价格年初价格1111121213设备维修费如下表设备维修费如下表使用年数使用年数0-11-22-33-44-5每年维修费用每年维修费用5681118解：解：将问题转化为最短路问题，如下图：用将问题转化为最短路问题，如下图：用vi表示表示“第第i年年年年初购进一台新设备初购进一台新设备
