运筹学图与网络分析课件.ppt

1、 图的基本概念图的基本概念 网络分析网络分析最小支撑树问题最小支撑树问题 最短路径问题最短路径问题网络最大流问题网络最大流问题ABCDACBD图论起源：哥尼斯堡七桥问题图论起源：哥尼斯堡七桥问题问题：问题：一个散步者能否从任一块陆地出发，走过七一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？座桥，且每座桥只走过一次，最后回到出发点？结论：结论：每个结点关联的边数均为偶数每个结点关联的边数均为偶数1 1 图的基本概念图的基本概念由点和边组成，记作由点和边组成，记作G=(VG=(V，E)E)，其中，其中V=(vV=(v1 1，v v2 2，v vn n) )为结点的

2、集合，为结点的集合，E=(eE=(e1 1，e e2 2，e em m) ) 为边的集合。为边的集合。点表示研究对象点表示研究对象边表示研究对象之间的特定关系边表示研究对象之间的特定关系1. 1. 图图p114p114图图无向图，记作无向图，记作G=(VG=(V，E)E)有向图，记作有向图，记作D=(VD=(V，A A) )例例1 1：哥尼斯堡桥问题的图为一个无向图。：哥尼斯堡桥问题的图为一个无向图。有向图的边有向图的边称为称为弧弧。例例2：五个球队的比赛情况，：五个球队的比赛情况，v1v2表示表示v1胜胜v2。v1v2v3v4v52 2、图的分类、图的分类v1v2v3v4v5v6e1e2e3

3、e4e5e6e7e8e9e10例例 654321,vvvvvvV ,10987654321eeeeeeeeeeE， ,211vve ,212vve ,323vve ,434vve ,315vve ,536vve ,537vve ,658vve ,669vve ,6110vve 图图1 1v4v6v1v2v3v5V = v1 , v2 , v3 , v4 , v5 , v6 ，A = (v1 , v3 ) , (v2 , v1) , (v2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) 图图2 2v1

4、v2v3v4v53 3、链与路、圈与回路、链与路、圈与回路链链 点边交错的序列点边交错的序列圈圈起点起点=终点的链终点的链路路点弧交错的序列点弧交错的序列回路回路起点起点= =终点的路终点的路v1v2v3v4v5无向图：无向图：有向图：有向图： 链与路中的点均不相同，则称为链与路中的点均不相同，则称为初等链初等链 ( (路路) )类似可定义类似可定义初等圈（回路）初等圈（回路）4 4、连通图、连通图任何两点之间至少存在一条链的图称为连通图，任何两点之间至少存在一条链的图称为连通图，否则称为不连通图。否则称为不连通图。G1G2G G1 1为不连通图，为不连通图， G G2 2为连通图为连通图例例

5、 ：5 5、支撑子图、支撑子图图图G=(VG=(V，E)E)和和G=(V G=(V ，E )E )，若，若V =V V =V 且且E E E E ，则称，则称G G 为为G G的的支撑子图支撑子图。 G G2 2为为G G1 1的支撑子图的支撑子图v1v2v3v4v5G1v1v2v3v4v5G2例例 ：G2 G2 是是G1 G1 的子图；的子图；v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)v1v2v3v4v5v6v7e1e6e7e9e10e11(c)例例 ：6 6、赋权图（网络）、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，图的每条边都有一个表

6、示一定实际含义的权数，称为称为赋权图赋权图。记作。记作D=(VD=(V，A A，C)C)。55.5v1v2v3v4v53.57.5423例例 ：2 2 最小支撑树问题最小支撑树问题本节主要内容：本节主要内容：树树支撑树支撑树最小支撑树最小支撑树 例例今有煤气站今有煤气站A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并

7、求所需的总费用。3.5ABCDEFGHIJKS2222225452634531树：树：无圈的连通图，记为无圈的连通图，记为T T。一、树的概念与性质一、树的概念与性质树的性质：树的性质： （1 1）树的任）树的任2 2点间有且仅有点间有且仅有1 1链；链； （2 2）在树中任去掉）在树中任去掉1 1边，则不连通；故树是使图保持边，则不连通；故树是使图保持 连通且具有最少边数的一种图形连通且具有最少边数的一种图形 （3 3）在树中不相邻）在树中不相邻2 2点间添点间添1 1边，恰成边，恰成1 1圈；圈； （4 4）若树）若树T T有有m m个顶点，则个顶点，则T T有有m-1m-1条边。条边。(

8、A)(B)(C) 若一个图若一个图 G =G =（V , EV , E）的支撑子图）的支撑子图 T=T=（V , EV , E ） 构成树，则称构成树，则称 T T 为为G G的支撑树的支撑树，又称，又称生成树生成树。二、图的支撑树二、图的支撑树(G)(G1)(G2)(G3)(G4)例例 例例 某地新建某地新建5 5处居民点，拟修处居民点，拟修道路连接道路连接5 5处，经勘测其道路可铺处，经勘测其道路可铺成如图所示。为使成如图所示。为使5 5处居民点都有处居民点都有道路相连，问至少要铺几条路？道路相连，问至少要铺几条路？解：解：该问题实为求图该问题实为求图的支撑树问题，的支撑树问题，共需铺共需

9、铺4 4条路。条路。v1v2v3v4v5 图的支撑树的应用举图的支撑树的应用举例例v1v2v3v4v555.53.57.5423用破圈法求出下图的一个生成树。用破圈法求出下图的一个生成树。 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8最小支撑树：最小支撑树：求网络的支撑树，使其权和最小。求网络的支撑树，使其权和最小。三、最小支撑树问题三、最小支撑树问题算法算法1 1（破圈法）：（破圈法）：在给定的赋权的连通图上找一个圈；在给定的赋权的连通图上找一个圈；在所找的圈中去掉一条权数最大的边在所找的圈中去掉

10、一条权数最大的边( (若有两条若有两条或两条以上的边都是权数最大的边，则任意去掉或两条以上的边都是权数最大的边，则任意去掉其中一条其中一条) )：若所余下的图已不含圈，则计算结束，所余下的若所余下的图已不含圈，则计算结束，所余下的图即为最小支撑树，否则，返问图即为最小支撑树，否则，返问。55.5v1v2v3v4v53.57.5423 例例 求上例中的最小支撑树求上例中的最小支撑树解：解：55.5v1v2v3v4v53.57.542355.5v1v2v3v4v53.57.54233v12v4v545v23.5v3算法算法2 2（避圈法）：（避圈法）：从某一点开始，把边按权从小从某一点开始，把边按

11、权从小到大依次添入图中，若出现圈，则删去其中最大到大依次添入图中，若出现圈，则删去其中最大边，直至填满边，直至填满n-1n-1条边为止（条边为止（n n为结点数）为结点数） 。最小生成树举例：最小生成树举例：某六个城市之间的道路网如图某六个城市之间的道路网如图 所示，要求沿着已所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线知长度的道路联结六个城市的电话线网，使电话线的总长度最短。的总长度最短。 v1v2v3v4v5v66515723445v1v4v5v6v2v31234v v1 1v v2 2v v3 3v v4 4v v5 51 14 42 23 31 13 35 52 2 联

12、系联系 今有煤气站今有煤气站A A，将给一居民区供应煤气，居民区，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531 练习练习 今有煤气站今有煤气站A A，将给一居民区供应煤气，居民区，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所各用户所在位置

13、如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS222222452634531 例例 今有煤气站今有煤气站A A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并

14、求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS22222252634531 例例 今有煤气站今有煤气站A A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222222634531 例例 今有煤气站今有煤气站A A，将给一居民区

15、供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。ABCDEFGHIJKS2222222634531 例例 今有煤气站今有煤气站A A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边

16、上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。IABCDEFGHJKS222222234531 例例 今有煤气站今有煤气站A A，将给一居民区供应煤气，居民区各，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。一个最经济的煤气管道路线，并求所需的总费用。IJABCDEF

17、GHKS22222223431此即为最经济的煤气管道路线，所需的总费用为此即为最经济的煤气管道路线，所需的总费用为2525万元万元3 3最短路径问题最短路径问题n最短路问题是在一个网络（赋权有向图）中寻找从起最短路问题是在一个网络（赋权有向图）中寻找从起点到某个节点之间一条最短的路线。现欲求出点到某个节点之间一条最短的路线。现欲求出1 1至至6 6距离最短的路径。距离最短的路径。 1 2 3 4 6 5 250 300 200 400 275 150 100 150 100 基本思想：基本思想：从起点从起点v vs s开始，逐步给每个结点开始，逐步给每个结点v vj j标号标号ddj j ,v

18、,vi i ，其中，其中d dj j为起点为起点v vs s到到v vj j的最短距离，的最短距离， v vi i为该为该最短路线上的前一节点最短路线上的前一节点. . 若给终点若给终点v vt t标上号标上号ddt t ,v ,vi i, , 表示已求出表示已求出v v1 1至至v vt t的的最短路其最短路长为最短路其最短路长为 d dt t ，最短路径可根据标号，最短路径可根据标号 v vi i 反向追踪而得反向追踪而得最短路问题的最短路问题的DijstraDijstra解法解法 （狄克拉斯）（狄克拉斯）v2v1v3v4v5v6v7v8v9163222266133101044例题：例题：

19、 求网络中求网络中v1到到v9的最短路的最短路10v2v1v3v4v5v6v7v8v916322226613310440, v0, v1 1 1, v1, v1 1 (3)(3) 考虑所有这样的边考虑所有这样的边vvi i , v , vj j ，其中，其中v vi iVVA A， v vj jVVB B，挑，挑选其中与起点选其中与起点v v1 1距离最短（距离最短（mindmindi i+c+cijij ）的）的v vj j，对，对v vj j进行标号进行标号(4)(4) 重复重复(2)(2)、(3)(3)，直至终点，直至终点v vn n标上号标上号ddn n, v, vi i ，则，则d

20、dn n即为即为v v1 1 v vn n的最短距离，反向追踪可求出最短路。的最短距离，反向追踪可求出最短路。(1)(1)给起点给起点v v1 1标号标号0, v0, v1 1 (2)把顶点集把顶点集V分成分成VA:已标号点集已标号点集VB：未标号点集：未标号点集10v2v1v3v4v5v6v7v8v916322226613310440, v0, v1 1 1, v1, v1 1 (3)(3) 考虑所有这样的边考虑所有这样的边vvi i , v , vj j ，其中，其中v vi iVVA A， v vj jVVB B，挑，挑选其中与起点选其中与起点v v1 1距离最短（距离最短（mindmi

21、ndi i+c+cijij ）的）的v vj j，对，对v vj j进行标号进行标号(4)(4) 重复重复(2)(2)、(3)(3)，直至终点，直至终点v vn n标上号标上号ddn n, v, vi i ，则，则d dn n即为即为v v1 1 v vn n的最短距离，反向追踪可求出最短路。的最短距离，反向追踪可求出最短路。(1)(1)给起点给起点v v1 1标号标号0, v0, v1 1 (2)把顶点集把顶点集V分成分成VA:已标号点集已标号点集VB：未标号点集：未标号点集3, v3, v1 1 0, v0, v1 1 1, v1, v1 1 3, v3, v1 1 5, v5, v3 3

22、 10v2v1v3v4v5v6v7v8v916322226613310440, v0, v1 1 1, v1, v1 1 3, v3, v1 1 5, v5, v3 3 6, v6, v2 2 10v2v1v3v4v5v6v7v8v916322226613310440, v0, v1 1 1, v1, v1 1 3, v3, v1 1 5, v5, v3 3 6, v6, v2 2 9, v9, v5 5 10v2v1v3v4v5v6v7v8v916322226613310440, v0, v1 1 1, v1, v1 1 3, v3, v1 1 5, v5, v3 3 6, v6, v2 2

23、 9, v9, v5 5 10, v10, v5 5 10v2v1v3v4v5v6v7v8v916322226613310440, v0, v1 1 1, v1, v1 1 3, v3, v1 1 5, v5, v3 3 6, v6, v2 2 9, v9, v5 5 10, v10, v5 5 12, v12, v5 5 此时终点此时终点v v9 9已标号已标号12, v12, v5 5 ，则，则1212即为即为v v1 1 v vn n的最的最短距离，反向追踪可求出最短路短距离，反向追踪可求出最短路10v2v1v3v4v5v6v7v8v916322226613310440, v0, v1

24、1 1, v1, v1 1 3, v3, v1 1 5, v5, v3 3 6, v6, v2 2 9, v9, v5 5 10, v10, v5 5 12, v12, v5 5 v v1 1到到v v9 9的最短路为：的最短路为：v v1 1 v v3 3 v v2 2 v v5 5 v v9 9，最短距离为最短距离为121210v2v1v3v4v5v6v7v8v91632222661331044p119 5 5V5V5V2V24 45 54 41 1V6V61 12 24 45 55 5V4V4V1V1V8V82 23 38 8V7V7V3V37 7练习：用练习：用DijkstraDijk

25、stra算法求下图中算法求下图中V1V1至至V8V8的最短路的最短路及最短路长。及最短路长。关键线路：关键线路：1.V1-V2-V4-V6-V81.V1-V2-V4-V6-V82.V1-V2-V4V7-V82.V1-V2-V4V7-V8最短路长：最短路长：1212V3V3 5 5V5V5V2V24 45 54 41 1V6V61 12 24 45 55 5V4V4V1V1V8V82 23 38 8V7V77 7(0,V1)(1,V1)(2,V1)(6,V2)(5,V2)(9,V4)(7,V4)(12,V6/V7) 课堂练习课堂练习 无向图情形无向图情形求网络中求网络中v v1 1至至v v7

26、7的最短路。的最短路。v1v2v3v4v5v6v7225355715713 课堂练习课堂练习 无向图情形无向图情形v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 72 22 25 53 35 55 57 71 15 57 71 13 30,v0,v1 1 2,v2,v1 1 3,v3,v1 1 4,v4,v2 2/ v/ v4 4 7,v7,v3 3 8,v8,v5 5 13,v13,v6 6 课堂练习课堂练习 无向图情形无向图情形答案（答案（2 2）：）：v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6v v7 72 22 25 53

27、 35 55 57 71 15 57 71 13 30,v0,v1 1 2,v2,v1 1 3,v3,v1 1 4,v4,v2 2/ v/ v4 4 7,v7,v3 3 8,v8,v5 5 13,v13,v6 6 最短路模型的应用最短路模型的应用设备更新问题设备更新问题第第i年年12345价格价格ai1111121213使用寿命使用寿命0112233445费用费用bj5681118例例 某工厂使用一种设备，这种设备在一定的年限内随着时某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否间的推移逐渐损坏。所以工厂在每年年初都要决定设备是否更新。若购

28、置设备，每年需支付购置费用；若继续使用旧设更新。若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用。计划期（五年）内中每年的备，需要支付维修与运行费用。计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。运行费在内的总费用最小。 最短路模型的应用最短路模型的应用设备更新问题设备更新问题分析分析：结点结点：V=vV=v1 1，v v6 6 ， v vi i表示第表示第i i

29、年初；年初；弧弧： A=(vA=(vi i，v vj j) ) 表示第表示第i i年初购买，用至第年初购买，用至第j j年初；年初；i= 1,5; j= 2,6i= 1,5; j= 2,6权权c cijij： i i年初年初 j j年初的费用，即年初的费用，即c cijij= i= i年初购买费年初购买费+ +（j-ij-i）年里的维修费）年里的维修费通路：通路：表示一个更新策略。例如表示一个更新策略。例如v1-v2-v6v1-v2-v6表示第一年购表示第一年购买用到第二年更新，继续用至第五年末的一个更新策买用到第二年更新，继续用至第五年末的一个更新策略略最短路模型的应用最短路模型的应用设备更

30、新问题设备更新问题v2v1v3v4v5v6第第i年年12345价格价格ai1111121213使用寿命使用寿命0112233445费用费用bj56811180,v0,v1 1 16,v16,v1 1 22,v22,v1 1 30,v30,v1 1 41,v41,v1 1 53,v53,v3 3/v/v4 4 161630302222414159591616222230304141171723233131171723231818建模：建模：求解：求解：v2v1v3v4v5v60,v116,v122,v130,v141,v153,v3/v416302241591622304117233117231

31、8求得两个最优更新策略：求得两个最优更新策略：1.1. v1-v4-v6v1-v4-v6，即第一年购买设备，用到第四年更新，再用至第五年年末，即第一年购买设备，用到第四年更新，再用至第五年年末2.2. V1-v3-v6V1-v3-v6，即第一年购买设备，用到第三年更新，再用至第五年年末，即第一年购买设备，用到第三年更新，再用至第五年年末最优费用为最优费用为5353 计划期（五年）内中每年的购置费、维修费与运行费如计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行

32、费在内的总费用最小。案才能使包括购置费、维修费与运行费在内的总费用最小。 年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 01 11 12 22 23 33 34 44 45 5维修费维修费5 57 7121218182525练习：设备更新问题练习：设备更新问题年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 01 11 12 22 23 33 34 44 45 5维修费维修费5 57 71212181825252828v v1 1v v2 2v v3 3v v4 4v v

33、5 5v v6 623232525262629293030424260608585323244446262333345453030 算法的基本思路与步骤：算法的基本思路与步骤： 首先设任一点首先设任一点v vi i到任一点到任一点v vj j都有一条弧。无弧相连都有一条弧。无弧相连的点之间假设存在权为的点之间假设存在权为+ +的的弧相连。弧相连。 从从v v1 1到到v vj j的最短路是从的最短路是从v v1 1出发，沿着这条路到某出发，沿着这条路到某个点个点v vi i再沿弧再沿弧( (v vi i , ,v vj j) )到到v vj j。则。则v v1 1到到v vi i的这条路必然也

34、是的这条路必然也是v v1 1到到v vi i的所有路中的最短路。的所有路中的最短路。 设设P P1j1j表示从表示从v v1 1到到v vj j的最短路长，的最短路长，P P1i1i表示从表示从v v1 1到到v vi i的最短路长，则有下列方程：的最短路长，则有下列方程： min11jiiijlPP ( (二二) Ford) Ford法法( (逐次逼近法逐次逼近法) ) （权有负数）（权有负数） 开始时，令开始时，令 即用即用v v1 1到到v vj j的直接距离做初始解的直接距离做初始解。),2,1(1)1(1njlPjj ）（nklPPjikiikj,3,2min)1(1)(1 )(1

35、kjP）（njPPtjtj,2,1)1(1)(1 ）（njPtj,2,1)(1 从第二步起，使用递推公式：从第二步起，使用递推公式：求求 ，当进行到第，当进行到第t t步，若出现步，若出现即为即为v v1 1到各点的最短路长。到各点的最短路长。则停止计算，则停止计算，例例: : 18v1v2v3v4v52635135211211v6v7v837从第二步起，使用递推公式从第二步起，使用递推公式)4 , 3,2,1(1)1(1 jlPjjmin)1(1)2(1jiiijlPP 3; 21; 0)1(41)1(31)1(21)1(11 PPPP083; 61; 0minmin)4 , 2 , 1(m

36、in1)2(1114)1(41;12)1(21;11)1(11)2(111)1(1)2(11 iiiiiPlPlPlPPilPPj 18v1v2v3v4v52635135211211v6v7v837从第二步起，使用递推公式从第二步起，使用递推公式min)1(1)2(1jiiijlPP 3; 21; 0)1(41)1(31)1(21)1(11 PPPP5)3(2; 01);1(0minmin)3 , 2; 2(min)2(2132)1(31;22)1(21;21)1(11)2(212)1(1)2(21 iiiiiPlPlPlPPijlPP 18v1v2v3v4v52635135211211v6v

37、7v837 18v1v2v3v4v52635135211211v6v7v837v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23 0000v260 2 -1-5-5-5v3 -30-5 1 -2-2-2-2v48 0 2 3-7-7-7v5 -1 0 1-3-3v6 1017 -1-1-1v7 -1 0 5-5-5v8 -3 -50 66n 为了求出从为了求出从v1v1到各个点的最短路，一般采用反向追到各个点的最短路，一般采用反向追踪的方法：如果已知踪的方法：如果已知d d( (v vs s ,v,vj j),),那么寻求一个点那么寻求一个点v vk k , ,使

38、得使得d d( (v vs s,v,vk k)+)+w wkjkj= =d d( (v vs s ,v,vj j) ,) ,然后记录下然后记录下( (v vk k ,v,vj j) )；在看；在看d d( (v vs s ,v,vk k) ,) ,寻求一个点寻求一个点v vi i , ,使得使得d d( (v vs s ,v,vi i)+)+w wikik= =d d( (v vs s ,v,vk k)依次类推，一直到达为止。这样，从依次类推，一直到达为止。这样，从v vs s到到v vj j的最短路是的最短路是（v vs s ,v,vi i ,v,vk k ,v,vj j）v1v2v3v4v

39、5v6v7v8P(1)P(2)P(3)P(4)v10-1-23 0000v260 2 -1-5-5-5v3 -30-5 1 -2-2-2-2v48 0 2 3-7-7-7v5 -1 0 1-3-3v6 1017 -1-1-1v7 -1 0 5-5-5v8 -3 -50 66v1v2v3v4v5v6v7v8P(1)P(2)P(3)P(4)v10-1-23 0000v260 2 -1-5-5-5v3 -30-5 1 -2-2-2-2v48 0 2 3-7-7-7v5 -1 0 1-3-3v6 1017 -1-1-1v7 -1 0 5-5-5v8 -3 -50 66 d d( (v v1 1 ,v,

40、v8 8)=6, )=6, 由于由于d d( (v v1 1 ,v,v6 6)+)+w w6868=(-1)+7=(-1)+7记录下记录下v v6 6 由于由于d d( (v v1 1 ,v,v3 3)+)+w w3636= =d d( (v v1 1 ,v,v6 6) ,) , 记录下记录下v v3 3 由于由于d d( (v v1 1 ,v,v1 1)+)+w w1313= =d d( (v v1 1 ,v,v3 3),), 于是，从于是，从v v1 1到到v v8 8的最短路是的最短路是( (v v1 1 ,v,v3 3 ,v,v6 6 ,v,v8 8) )。 引例：下图为引例：下图为V

41、 V1 1到到V V6 6的一交通网，权表示相应运输线的最大的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从通过能力，制定一方案，使从V V1 1到到V V6 6的运输产品数量最多。的运输产品数量最多。v2v1v3v4v5v681041755311635312213362已知网络已知网络D D= =（V V，A A，C C），其中），其中V V为顶点集，为顶点集，A A为弧集，为弧集，C C=c cijij 为容量集，为容量集， c cijij 为弧（为弧（v vi i，v vj j ）上的容量。现）上的容量。现D D上要通过一上要通过一个个流流f f=f fijij ，其中，其中

42、f fijij 为弧（为弧（v vi i，v vj j ）上的流量。）上的流量。问题：问题：应如何安排流量应如何安排流量f fijij可使可使D D上通过的总流量上通过的总流量v v最大？最大？v2v1v3v4v5v681041755311635312213362一、一般提法一、一般提法max v=vmax v=v（f f） ijijcf 0 tsitifvsifvffjjjiij,0)()(容量约束容量约束平衡约束平衡约束s.t.v2Vsv3v4v5Vt81041755311635312213362P125P125满足上述所有约束条件的流成为满足上述所有约束条件的流成为可行流可行流。 （1

43、1）容量条件：对于每一个弧（）容量条件：对于每一个弧（v vi i ,v ,vj j）A A，有有0 0 f fijij c cijij 。 （2 2）平衡条件：）平衡条件： 对于发点对于发点v vs s，有，有 对于收点对于收点v vt t ，有，有 对于中间点，有对于中间点，有 为可行流为可行流f f 的流量的流量( (发点的净输出量或收点的净发点的净输出量或收点的净输入量输入量) ) AvvAvvsjjsjssjfvff),(),()( AvvAvvt jjtjttjfvff),(),()( AvvAvvi jjijiijff),(),(0)(fv1、称满足下列条件的流称满足下列条件的流

44、f f为可行流：为可行流： 可行流特征：可行流特征：（1 1）容量条件：每一个弧上的流量不能超过该弧的容量）容量条件：每一个弧上的流量不能超过该弧的容量。（2 2）每一个中间点的流入量与流出量的代数和为零。（）每一个中间点的流入量与流出量的代数和为零。（转运的作用）转运的作用）（3 3）出发点的总流出量与收点的总流入量必相等。）出发点的总流出量与收点的总流入量必相等。 任意一个网络上的可行流总是存在的。例如零流任意一个网络上的可行流总是存在的。例如零流v(f)=0,v(f)=0,就是满足以上条件的可行流。就是满足以上条件的可行流。 网络系统中最大流问题网络系统中最大流问题就是在给定的网络上寻求

45、一就是在给定的网络上寻求一个可行流个可行流f,f,其流量其流量v(f)v(f)达到最大值。达到最大值。可行流中可行流中 f fijijc cijij 的弧叫做的弧叫做饱和弧饱和弧； f fijijc cijij的弧叫做的弧叫做非饱和弧非饱和弧； f fijij0 0 的弧叫做的弧叫做非零流弧非零流弧； f fijij0 0 的弧叫做的弧叫做零流弧零流弧。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3） f f为一可行流，为一可行流，u u为为v vs s至至v vt t的链，令的链，令u u+ +=正向弧正向弧 ， u u- -

46、=反向弧反向弧 。若。若u u+ +中弧皆非饱，且中弧皆非饱，且u u- -中弧皆非零，则称中弧皆非零，则称u u为为关于关于f f的一条的一条增广链增广链。v2v1v3v4v5v681041755311635312213362v2v1v3v4v5v681041755311635312213362显然图中增广链不止一条显然图中增广链不止一条THANK YOUSUCCESS2022-5-15v2v1v3v4v5v681041755311635312213362 容量网络容量网络D =D =（V V，A A，C C），），v vs s为始点，为始点，v vt t为终点。为终点。如果把如果把V V分

47、成两个非空集合分成两个非空集合 使使 则 所 有 始 点 属 于则 所 有 始 点 属 于V V1 1， 而 终 点 属 于， 而 终 点 属 于 的 弧 的 集的 弧 的 集合合 ，称为分离，称为分离v vs s和和v vt t的的截集截集。11, VV11,VvVvts 1V),(11VV4 4、截集和截集的截量、截集和截集的截量截集是连接起点和终点的必经之路。截集是连接起点和终点的必经之路。 ),(11VV ),(),(1111),(VVvvijjicVVC截集截集 中所有弧的容量之和，称为这个截集的中所有弧的容量之和，称为这个截集的截量截量，记为记为vsv1v2v4v3vt374556

48、378V),(2vvVs ),(431tvvvvV ),(, ),( , ),(),(32421vvvvvvVVs 18567),(23241 cccVVCs2v1v3v4v5v6v7v 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1) ),(),(),(),(75423121vvvvvvVV 则截集为则截集为设设 5211,vvvV 76432,vvvvV 不不是是截截集集中中的的弧弧和和注注意意 ),( ),(5423vvvv容量为容量为24242v1v3v4v5v6v7v 13 (5)9 (3)4 (1)5 (3)

49、6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)设设 211,vvV 则截集为则截集为 765432,vvvvvV ),(),(),(),(52423121vvvvvvVV 容量为容量为2020任一可行流的流量都不会超过任一截集的截量任一可行流的流量都不会超过任一截集的截量v1vsv2v3vt（2 2，2 2）（4 4，3 3）（3 3，1 1）（1 1，0 0）（3 3，3 3）（5 5，2 2）（2 2，2 2）最大流最小截定理：最大流最小截定理：任一网络任一网络D D中，从中，从v v s s至至v v t t 的最大流的的最大流的流量等于分离流量等于分离

50、v v s s、v v t t 的最小截集的容量。的最小截集的容量。如图所示的网络中，弧旁数字为如图所示的网络中，弧旁数字为( (c cijij , ,f fij ij ) )v1vsv2v3vt（2 2，2 2）（4 4，3 3）（3 3，1 1）（1 1，0 0）（3 3，3 3）（5 5，2 2）（2 2，2 2）（1 1）确定所有的截集；）确定所有的截集；（2 2）求最小截集的容量；）求最小截集的容量；（3 3）证明图中的流为最大流；）证明图中的流为最大流；v1vsv2v3vt（2 2，2 2）（4 4，3 3）（3 3，1 1）（1 1，0 0）（3 3，3 3）（5 5，2 2）（