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

第5章 图论与网络分析Ø  图的基本概念图的基本概念   网络分析网络分析Ø最小支撑树问题最小支撑树问题Ø  最短路径问题最短路径问题Ø网络最大流问题网络最大流问题ABCDACBD图论起源：哥尼斯堡七桥问题图论起源：哥尼斯堡七桥问题问题：问题：一个散步者能否从任一块陆地出发，走过七一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？座桥，且每座桥只走过一次，最后回到出发点？结论：结论：每个结点关联的边数均为偶数每个结点关联的边数均为偶数§§1 1 图的基本概念图的基本概念由点和边组成，记作由点和边组成，记作G=(VG=(V，，E)E)，其中，其中V=V=(v(v1 1，，v v2 2，，…………，，v vn n) )为结点的集合，为结点的集合，E=E=(e(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胜胜v2v1v2v3v4v52 2、图的分类、图的分类v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例图图1 1v4v6v1v2v3v5V = {v1 , v2 , v3 , v4 , v5 , v6 }，A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) }图图2 2v1v2v3v4v53 3、链与路、圈与回路、链与路、圈与回路链链 点边交错的序列点边交错的序列圈圈起点起点=终点的链终点的链路路点弧交错的序列点弧交错的序列回路回路起点起点= =终点的路终点的路v1v2v3v4v5无向图：无向图：有向图：有向图： 链与路中的点均不相同，则称为链与路中的点均不相同，则称为初等链初等链 ( (路路) )类似可定义类似可定义初等圈（回路）初等圈（回路）4 4、连通图、连通图任何两点之间至少存在一条链的图称为连通图，任何两点之间至少存在一条链的图称为连通图，否则称为不连通图。

否则称为不连通图G1G2G G1 1为不连通图，为不连通图， G G2 2为连通图为连通图例例 ：：5 5、支撑子图、支撑子图图图G=(VG=(V，，E)E)和和G G' '=(V =(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、赋权图（网络）、赋权图（网络）图的每条边都有一个表示一定实际含义的权数，图的每条边都有一个表示一定实际含义的权数，称为称为赋权图赋权图记作D=(VD=(V，，A A，，C)C)55.5v1v2v3v4v53.57.5423例例 ：：§§2 2 最小支撑树问题最小支撑树问题本节主要内容：本节主要内容：树树支撑树支撑树最小支撑树最小支撑树 [例例]今今有有煤煤气气站站A，，将将给给一一居居民民区区供供应应煤煤气气，，居居民民区区各各用用户户所所在在位位置置如如图图所所示示，，铺铺设设各各用用户户点点的的煤煤气气管管道道所所需需的的费费用用（（单单位位：：万万元元））如如图图边边上上的的数数字字所所示示。

要要求求设设计计一个最经济的煤气管道路线，并求所需的总费用一个最经济的煤气管道路线，并求所需的总费用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条边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处居民点都有处居民点都有道路相连，问至少要铺几条路？道路相连，问至少要铺几条路？解：解：该问题实为求图该问题实为求图的支撑树问题，的支撑树问题，共需铺共需铺4 4条路v1v2v3v4v5 图的支撑树的应用举图的支撑树的应用举例例v1v2v3v4v555.53.57.5423用破圈法求出下图的一个生成树用破圈法求出下图的一个生成树 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8最小支撑树：最小支撑树：求网络的支撑树，使其权和最小求网络的支撑树，使其权和最小三、最小支撑树问题三、最小支撑树问题算法算法1 1（破圈法）：（破圈法）：①①在给定的赋权的连通图上找一个圈；在给定的赋权的连通图上找一个圈；②②在所找的圈中去掉一条权数最大的边在所找的圈中去掉一条权数最大的边( (若有两条或若有两条或两条以上的边都是权数最大的边，则任意去掉其两条以上的边都是权数最大的边，则任意去掉其中一条中一条) )：：③③若所余下的图已不含圈，则计算结束，所余下的若所余下的图已不含圈，则计算结束，所余下的图即为最小支撑树，否则，返问图即为最小支撑树，否则，返问①①。

55.5v1v2v3v4v53.57.5423[ [例例] ] 求上例中的最小支撑树求上例中的最小支撑树解：解：55.5v1v2v3v4v53.57.542355.5v1v2v3v4v53.57.54233v12v4v545v23.5v3算法算法2 2（避圈法）：（避圈法）：从某一点开始，把边按权从小从某一点开始，把边按权从小到大依次添入图中，若出现圈，则删去其中最大到大依次添入图中，若出现圈，则删去其中最大边，直至填满边，直至填满n-1n-1条边为止（条边为止（n n为结点数）为结点数） 最小生成树举例：最小生成树举例：某六个城市之间的道路网如图某六个城市之间的道路网如图 所示，要求沿着已所示，要求沿着已知长度的道路联结六个城市的线网，使线知长度的道路联结六个城市的线网，使线的总长度最短的总长度最短 v1v2v3v4v5v66515723445v1v4v5v6v2v31234v v1 1v v2 2v v3 3v v4 4v v5 51 14 42 23 31 13 35 52 2 [ [联联系系] ]今今有有煤煤气气站站A A，，将将给给一一居居民民区区供供应应煤煤气气，，居居民民区区各各用用户户所所在在位位置置如如图图所所示示，，铺铺设设各各用用户户点点的的煤煤气气管管道道所所需需的的费费用用（（单单位位：：万万元元））如如图图边边上上的的数数字字所所示示。

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

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

要要求求设设计计一个最经济的煤气管道路线，并求所需的总费用一个最经济的煤气管道路线，并求所需的总费用IJABCDEFGHKS22222223431此即为最经济的煤气管道路线，所需的总费用为此即为最经济的煤气管道路线，所需的总费用为2525万元万元§§3 3最短路径问题最短路径问题n最短路问题是在一个网络（赋权有向图）中寻找从起最短路问题是在一个网络（赋权有向图）中寻找从起点到某个节点之间一条最短的路线现欲求出点到某个节点之间一条最短的路线现欲求出υυ1 1至至υυ6 6距离最短的路径距离最短的路径 基本思想：基本思想：从起点从起点v vs s开始，逐步给每个结点开始，逐步给每个结点v vj j标号标号[d[dj j ,v,vi i] ]，其中，其中d dj j为起点为起点v vs s到到v vj j的最短距离，的最短距离， v vi i为该最短为该最短路线上的前一节点路线上的前一节点. . 若给终点若给终点v vt t标上号标上号[d[dt t ,v ,vi i], ], 表示已求出表示已求出v v1 1至至v vt t的最的最短路其最短路长为短路其最短路长为 d dt t ，最短路径可根据标号，最短路径可根据标号 v vi i 反反向追踪而得向追踪而得最短路问题的最短路问题的DijstraDijstra解法解法 （狄克拉斯）（狄克拉斯）v2v1v3v4v5v6v7v8v9163222266133101044例题：例题： 求网络中求网络中v1到到v9的最短路的最短路10v2v1v3v4v5v6v7v8v91632222661331044[0, v[0, v1 1] ][1, v[1, v1 1] ](3)(3) 考虑所有这样的边考虑所有这样的边[v[vi i , v , vj j] ]，其中，其中v vi i∈V∈VA A，， v vj j∈V∈VB B，挑，挑选其中与起点选其中与起点v v1 1距离最短（距离最短（min{dmin{di i+c+cijij} }）的）的v vj j，对，对v vj j进行标号进行标号(4)(4) 重复重复(2)(2)、、(3)(3)，直至终点，直至终点v vn n标上号标上号[d[dn n, v, vi i] ]，则，则d dn n即为即为v v1 1→ v→ vn n的最短距离，反向追踪可求出最短路。

的最短距离，反向追踪可求出最短路1)(1)给起点给起点v v1 1标号标号[0, v[0, v1 1] ](2)把顶点集把顶点集V分成分成VA:已标号点集已标号点集VB：未标号点集：未标号点集10v2v1v3v4v5v6v7v8v91632222661331044[0, v[0, v1 1] ][1, v[1, v1 1] ](3)(3) 考虑所有这样的边考虑所有这样的边[v[vi i , v , vj j] ]，其中，其中v vi i∈V∈VA A，， v vj j∈V∈VB B，挑，挑选其中与起点选其中与起点v v1 1距离最短（距离最短（min{dmin{di i+c+cijij} }）的）的v vj j，对，对v vj j进行标号进行标号(4)(4) 重复重复(2)(2)、、(3)(3)，直至终点，直至终点v vn n标上号标上号[d[dn n, v, vi i] ]，则，则d dn n即为即为v v1 1→ v→ vn n的最短距离，反向追踪可求出最短路的最短距离，反向追踪可求出最短路1)(1)给起点给起点v v1 1标号标号[0, v[0, v1 1] ](2)把顶点集把顶点集V分成分成VA:已标号点集已标号点集VB：未标号点集：未标号点集[3, v[3, v1 1] ][0, v[0, v1 1] ][1, v[1, v1 1] ][3, v[3, v1 1] ][5, v[5, v3 3] ]10v2v1v3v4v5v6v7v8v91632222661331044[0, v[0, v1 1] ][1, v[1, v1 1] ][3, v[3, v1 1] ][5, v[5, v3 3] ][6, v[6, v2 2] ]10v2v1v3v4v5v6v7v8v91632222661331044[0, v[0, v1 1] ][1, v[1, v1 1] ][3, v[3, v1 1] ][5, v[5, v3 3] ][6, v[6, v2 2] ][9, v[9, v5 5] ]10v2v1v3v4v5v6v7v8v91632222661331044[0, v[0, v1 1] ][1, v[1, v1 1] ][3, v[3, v1 1] ][5, v[5, v3 3] ][6, v[6, v2 2] ][9, v[9, v5 5] ][10, v[10, v5 5] ]10v2v1v3v4v5v6v7v8v91632222661331044[0, v[0, v1 1] ][1, v[1, v1 1] ][3, v[3, v1 1] ][5, v[5, v3 3] ][6, v[6, v2 2] ][9, v[9, v5 5] ][10, v[10, v5 5] ][12, v[12, v5 5] ]此时终点此时终点v v9 9已标号已标号[12, v[12, v5 5] ]，则，则1212即为即为v v1 1→ v→ vn n的最的最短距离，反向追踪可求出最短路短距离，反向追踪可求出最短路10v2v1v3v4v5v6v7v8v91632222661331044[0, v[0, v1 1] ][1, v[1, v1 1] ][3, v[3, v1 1] ][5, v[5, v3 3] ][6, v[6, v2 2] ][9, v[9, v5 5] ][10, v[10, v5 5] ][12, v[12, 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练习：用练习：用DijkstraDijkstra算法求下图中算法求下图中V1V1至至V8V8的最短路的最短路及最短路长。

及最短路长关键线路：关键线路：1.V1--V2--V4--V6--V81.V1--V2--V4--V6--V82.V1--V2--V42.V1--V2--V4——V7--V8V7--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 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 3[0,v[0,v1 1] ][2,v[2,v1 1] ][3,v[3,v1 1] ][4,v[4,v2 2/ v/ v4 4] ][7,v[7,v3 3] ][8,v[8,v5 5] ][13,v[13,v6 6] ][ [课堂练习课堂练习] ] 无向图情形无向图情形答案（答案（2 2）：）：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 3[0,v[0,v1 1] ][2,v[2,v1 1] ][3,v[3,v1 1] ][4,v[4,v2 2/ v/ v4 4] ][7,v[7,v3 3] ][8,v[8,v5 5] ][13,v[13,v6 6] ] 最短路模型的应用最短路模型的应用————设备更新问题设备更新问题第第i年年12345价格价格ai1111121213使用寿命使用寿命0~11~22~33~44~5费用费用bj5681118例例 某工厂使用一种设备，这种设备在一定的年限内随着时某工厂使用一种设备，这种设备在一定的年限内随着时间的推移逐渐损坏。

所以工厂在每年年初都要决定设备是否间的推移逐渐损坏所以工厂在每年年初都要决定设备是否更新若购置设备，每年需支付购置费用；若继续使用旧设更新若购置设备，每年需支付购置费用；若继续使用旧设备，需要支付维修与运行费用计划期（五年）内中每年的备，需要支付维修与运行费用计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小运行费在内的总费用最小 最短路模型的应用最短路模型的应用————设备更新问题设备更新问题分析分析：：结点结点：：V={vV={v1 1，，……，，v v6 6} }，， v vi i表示第表示第i i年初；年初；弧弧：： A={(vA={(vi i，，v vj j)} )} 表示第表示第i i年初购买，用至第年初购买，用至第j j年初；年初；i= 1,i= 1,……,5; j= 2,,5; j= 2,……,6,6权权c cijij：： i i年初年初~ j~ j年初的费用，即年初的费用，即c cijij= i= i年初购买费年初购买费+ +（（j-ij-i）年里的维修费）年里的维修费通路：通路：表示一个更新策略。

例如表示一个更新策略例如v1-v2-v6v1-v2-v6表示第一年购表示第一年购买用到第二年更新，继续用至第五年末的一个更新策买用到第二年更新，继续用至第五年末的一个更新策略略最短路模型的应用最短路模型的应用————设备更新问题设备更新问题v2v1v3v4v5v6第第i年年12345价格价格ai1111121213使用寿命使用寿命0~11~22~33~44~5费用费用bj5681118[0,v[0,v1 1] ][16,v[16,v1 1] ][22,v[22,v1 1] ][30,v[30,v1 1] ][41,v[41,v1 1] ][53,v[53,v3 3/v/v4 4] ]161630302222414159591616222230304141171723233131171723231818建模：建模：求解：求解：v2v1v3v4v5v6[0,v1][16,v1][22,v1][30,v1][41,v1][53,v3/v4]163022415916223041172331172318求得两个最优更新策略：求得两个最优更新策略：1.1.v1-v4-v6v1-v4-v6，即第一年购买设备，用到第四年更新，再用至第五年年末，即第一年购买设备，用到第四年更新，再用至第五年年末2.2.V1-v3-v6V1-v3-v6，即第一年购买设备，用到第三年更新，再用至第五年年末，即第一年购买设备，用到第三年更新，再用至第五年年末最优费用为最优费用为5353 计划期（五年）内中每年的购置费、维修费与运行费如计划期（五年）内中每年的购置费、维修费与运行费如表所示，工厂要制定今后五年设备更新计划，问采用何种方表所示，工厂要制定今后五年设备更新计划，问采用何种方案才能使包括购置费、维修费与运行费在内的总费用最小。

案才能使包括购置费、维修费与运行费在内的总费用最小 年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 0~1 11 1~2 22 2~3 33 3~4 44 4~5 5维修费维修费5 57 7121218182525练习：设备更新问题练习：设备更新问题年份年份1 12 23 34 45 5购置费购置费18182020212123232424使用年数使用年数0 0~1 11 1~2 22 2~3 33 3~4 44 4~5 5维修费维修费5 57 71212181825252828v v1 1v v2 2v v3 3v v4 4v v5 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的的这这条条路路必必然然也也是是v v1 1到到v vi i的所有路中的最短路的所有路中的最短路 设设P P1j1j表表示示从从v v1 1到到v vj j的的最最短短路路长长，，P P1i1i表表示示从从v v1 1到到v vi i的最短路长，则有下列方程：的最短路长，则有下列方程： ( (二二) Ford) Ford法法( (逐次逼近法逐次逼近法) ) （权有负数）（权有负数） 开始时，令开始时，令 即用即用v v1 1到到v vj j的直接距离做初始解的直接距离做初始解从第二步起，使用递推公式：从第二步起，使用递推公式：求求 ，当进行到第，当进行到第t t步，若出现步，若出现即为即为v v1 1到各点的最短路长到各点的最短路长则停止计算，则停止计算，例例: : －－18v1v2v3v4v5－－26－－3－－5－－1－－3－－521－－1211v6v7v837从第二步起，使用递推公式从第二步起，使用递推公式 －－18v1v2v3v4v5－－26－－3－－5－－1－－3－－521－－1211v6v7v837从第二步起，使用递推公式从第二步起，使用递推公式 －－18v1v2v3v4v5－－26－－3－－5－－1－－3－－521－－1211v6v7v837 －－18v1v2v3v4v5－－26－－3－－5－－1－－3－－521－－1211v6v7v837v1v2v3v4v5v6v7v8P(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n 为为了了求求出出从从v1v1到到各各个个点点的的最最短短路路，，一一般般采采用用反反向向追追踪踪的的方方法法：：如如果果已已知知d d( (v vs s ,v,vj j),),那那么么寻寻求求一一个个点点v vk k , ,使使得得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））v1v2v3v4v5v6v7v8P(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v1v2v3v4v5v6v7v8P(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,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) )。

§§4 4 网络最大流问题网络最大流问题引例：下图为引例：下图为V 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} }，其中，其中f fijij 为弧（为弧（v vi i，，v vj j ）上的流量上的流量问题：问题：应如何安排流量应如何安排流量f fijij可使可使D D上通过的总流量上通过的总流量v v最大？最大？v2v1v3v4v5v681041755311635312213362一、一般提法一、一般提法二、最大流问题的数学模型二、最大流问题的数学模型max v=vmax v=v（（f f）） 容量约束容量约束平衡约束平衡约束s.t.v2Vsv3v4v5Vt81041755311635312213362P125P125满足上述所有约束条件的流成为满足上述所有约束条件的流成为可行流可行流。

 （（1 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 的流量的流量( (发点的净输出量或收点的净发点的净输出量或收点的净输入量输入量) )1、称满足下列条件的流称满足下列条件的流f f为可行流：为可行流：三、三、 基本概念和定理基本概念和定理 可行流特征：可行流特征：（（1 1）容量条件：每一个弧上的流量不能超过该弧的容量容量条件：每一个弧上的流量不能超过该弧的容量2 2）每一个中间点的流入量与流出量的代数和为零每一个中间点的流入量与流出量的代数和为零转运的作用）（转运的作用）（（3 3）出发点的总流出量与收点的总流入量必相等。

出发点的总流出量与收点的总流入量必相等 任意一个网络上的可行流总是存在的例如零流任意一个网络上的可行流总是存在的例如零流v(f)=0,v(f)=0,就是满足以上条件的可行流就是满足以上条件的可行流 网络系统中最大流问题网络系统中最大流问题就是在给定的网络上寻求一就是在给定的网络上寻求一个可行流个可行流f,f,其流量其流量v(f)v(f)达到最大值达到最大值可行流中可行流中 f fijij＝＝c cijij 的弧叫做的弧叫做饱和弧饱和弧；； f fijij＜＜c cijij的弧叫做的弧叫做非饱和弧非饱和弧；； f fijij＞＞0 0 的弧叫做的弧叫做非零流弧非零流弧；； f fijij＝＝0 0 的弧叫做的弧叫做零流弧零流弧v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2 2、饱和弧与零流弧、饱和弧与零流弧 f f为一可行流，为一可行流，u u为为v vs s至至v vt t的链，令的链，令u u+ +={={正向弧正向弧} }，， u u- -={={反向弧反向弧} }。

若若u u+ +中弧皆非饱，且中弧皆非饱，且u u- -中弧皆非零，则称中弧皆非零，则称u u为关于为关于f f的一条的一条增广链增广链v2v1v3v4v5v6810417553116353122133623 3、增广链、增广链增广链增广链v2v1v3v4v5v681041755311635312213362显然图中增广链不止一条显然图中增广链不止一条THANK YOUSUCCESS2024/9/1967可编辑增广链增广链v2v1v3v4v5v681041755311635312213362 容容量量网网络络D D = =（（V V，，A A，，C C）），，v vs s为为始始点点，，v vt t为为终终点点如果把如果把V V分成两个非空集合分成两个非空集合 使使 则则所所有有始始点点属属于于V V1 1，，而而终终点点属属于于 的的弧弧的的集集合合 ，称为分离，称为分离v vs s和和v vt t的的截集截集。

4 4、截集和截集的截量、截集和截集的截量截集是连接起点和终点的必经之路截集是连接起点和终点的必经之路 截集截集 中所有弧的容量之和，称为这个截集的中所有弧的容量之和，称为这个截集的截量截量，，记为记为vsv1v2v4v3vt374556378V 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)则截集为则截集为设设容量为容量为2424 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)设设则截集为则截集为容量为容量为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 的最大流的的最大流的流量等于分离流量等于分离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））（（2 2，，2 2））（（1 1）所有的截集：）所有的截集：① ① V V1 1={v={vs s} }，，截集为截集为{({(v vs s,v,v1 1), (), (v vs s,v,v2 2)})}，截量为：，截量为：6 6v v1 1v vs sv v2 2v v3 3v vt t（（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）所有的截集：）所有的截集：① ① V V1 1={v={vs s} }，截集为，截集为{(v{(vs s,v,v1 1), (v), (vs s,v,v2 2)})}，截量为：，截量为：6 6②V1={v②V1={vs s ,v ,v1 1} }，截集为，截集为{(v{(vs s,v,v2 2), (v), (v1 1,v,vt t)})}，截量为：，截量为：7 7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 1 1）所有的截集：）所有的截集：）所有的截集：）所有的截集：① ① V V1 1={v={vs s} }，截集为，截集为{(v{(vs s,v,v1 1), (v), (vs s,v,v2 2)})}，截量为：，截量为：6 6②V②V1 1={v={vs s ,v,v1 1} }，截集为，截集为{(v{(vs s,v,v2 2), (v), (v1 1,v,vt t)})}，截量为：，截量为：7 7③V1={v③V1={vs s , ,v v2 2} }，，截集为截集为截集为截集为{ {…………} }，截量为：，截量为：7 7① ① V V1 1={={vs} }，截集为，截集为{({(vs,v1), (vs,v2)})}，截量为：，截量为：6 6②V②V1 1={={vs ,v1} }，截集为，截集为{({(vs,v2), (v1,vt)}，截量为：，截量为：7 7③V1={③V1={vs ,v2} }，，截集为截集为截集为截集为{ {…………} }，截量为：，截量为：7 7④V1={④V1={vs ,v3} }，，截集为截集为截集为截集为{ {…………} }，截量为：，截量为：1212v1vsv2v3vt（（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 1 1）所有的截集：）所有的截集：）所有的截集：）所有的截集：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 1 1）所有的截集：）所有的截集：）所有的截集：）所有的截集：① ① V V1 1={={vs} }，截集为，截集为{({(vs,v1), (vs,v2)})}，截量为：，截量为：6 6②V②V1 1={={vs ,v1} }，截集为，截集为{({(vs,v2), (v1,vt)}，截量为：，截量为：7 7③V1={③V1={vs ,v2} }，，截集为截集为截集为截集为{ {…………} }，截量为：，截量为：7 7④V1={④V1={vs ,v3} }，，截集为截集为截集为截集为{ {…………} }，截量为：，截量为：1212⑤V1={⑤V1={vs ,v1,v2} }，，截集为截集为截集为截集为{ {…………} }，截量为：，截量为：5 5…………v1vsv2v3vt（（2，，2））（（4，，3））（（3，，1））（（1，，0））（（3，，3））（（5，，2））（（2，，2））（（2 2））最小截量最小截量min C (V1,V2)= 5min C (V1,V2)= 5；；（（3 3））∵∵v(fv(f* *)=5= min C (V1,V2))=5= min C (V1,V2) ∴ f ∴ f* *是最大流。

是最大流最大流判定定理：最大流判定定理： 可行流可行流f* f* 是最大流的充分必要条件是当且仅当不存在从是最大流的充分必要条件是当且仅当不存在从v vs s到到v vt t 的关于的关于f *f *的增广链的增广链 p124寻求网络最大流问题的主要步骤：寻求网络最大流问题的主要步骤：（（1 1）确定初始可行流（观察法和零流法））确定初始可行流（观察法和零流法）（（2 2）检验当前可行流是否是网络中的最大流）检验当前可行流是否是网络中的最大流( (对已知可对已知可行流用标号法寻找可扩充链，若存在，则当前可行流不行流用标号法寻找可扩充链，若存在，则当前可行流不是最大流，转是最大流，转(3)(3)；若不存在，则是最大流）；若不存在，则是最大流）（（3 3）将当前的可行流调整成一个流量更大的新可行流．）将当前的可行流调整成一个流量更大的新可行流．再由再由(2)(2)检验检验四、求最大流方法四、求最大流方法————标号法标号法思路：思路：从始点开始标号，寻找是否存在增广链给从始点开始标号，寻找是否存在增广链给v vj j标号标号为为[θ[θj j,v,vi i] ]，其中，其中θθj j为调整量，为调整量， v vi i为前一节点。

为前一节点标号具体步骤标号具体步骤：检查所有已检查所有已标号点与标号点与没标号点没标号点的关联弧的关联弧流出弧和流流出弧和流入弧入弧（（b b）） 标号终止，说明不存在可扩充链，标号终止，说明不存在可扩充链，当前即为流为最大流，并得最小截集当前即为流为最大流，并得最小截集（（a a）） 说明存在可扩充链说明存在可扩充链, ,反向追踪找出反向追踪找出 , ,转转(4)(4)例例5 5 用标号法求下面网络的最大流用标号法求下面网络的最大流2,2,2 2））（（1,1,1 1））（（3,3,3 3））（（1,1,1 1））（（4,4,3 3））（（5,5,1 1））（（3,3,0 0））（（2,2,1 1））（（5,5,3 3））vsv2v1v3v4v6步骤：步骤：(1)(1)给给v vs s标号为标号为[∞,v[∞,vs s] ]，， 选与选与v vs s关联的流出未饱和弧关联的流出未饱和弧(v(vs s, v, vj j) ,) ,给给v vj j标号标号[θ[θj j,v,vs s],],其中其中θθj j=c=csjsj-f-fsjsj例例5 5 用标号法求下面网络的最大流。

用标号法求下面网络的最大流2,2,2 2））（（1,1,1 1））（（3,3,3 3））（（1,1,1 1））（（4,4,3 3））（（5,5,1 1））（（3,3,0 0））（（2,2,1 1））（（5,5,3 3））vsv2v1v3v4v6(2)把节点集把节点集V分为分为 VA：已标号点集：已标号点集 VB：未标号点集：未标号点集例例5 5 用标号法求下面网络的最大流用标号法求下面网络的最大流2,2,2 2））（（1,1,1 1））（（3,3,3 3））（（1,1,1 1））（（4,4,3 3））（（5,5,1 1））（（3,3,0 0））（（2,2,1 1））（（5,5,3 3））vsv2v1v3v4v6（（3）考虑所有弧）考虑所有弧(vi , vj)或或(vj, vi) ,其中其中vi∈∈VA,vj∈∈VB，若该，若该弧为弧为         流出未饱弧流出未饱弧,则给则给vj标号标号[θj,vi],其中其中θj=min(cij-fij，，θi））         流入非零弧流入非零弧,则给则给vj标号标号[θj,-vi] ,其中其中θj=min( fij ，，θi））（（2,2,2 2））（（1,1,1 1））（（3,3,3 3））（（1,1,1 1））（（4,4,3 3））（（5,5,1 1））（（3,3,0 0））（（2,2,1 1））（（5,5,3 3））vsv2v1v3v4v6例例5 5 用标号法求下面网络的最大流。

用标号法求下面网络的最大流vtvt已标号，得到一条增广链已标号，得到一条增广链u(u(反向追踪反向追踪) )，转（，转（5 5）；）；vtvt未标号，且无法再标号未标号，且无法再标号, ,此时的流为此时的流为最大流最大流, ,此时的截集为此时的截集为最小截最小截4 4）重复（）重复（2 2））, ,（（3 3），依次进行的结局可能为：），依次进行的结局可能为：（（2,2,2 2））（（1,1,1 1））（（3,3,3 3））（（1,1,1 1））（（4,4,3 3））（（5,5,1 1））（（3,3,0 0））（（2,2,1 1））（（5,5,3 3））vsv2v1v3v4v6例例5 5 用标号法求下面网络的最大流用标号法求下面网络的最大流vtvt已标号，得到一条增广链已标号，得到一条增广链u(u(反向追踪反向追踪) )，转（，转（5 5）；）；vtvt未标号，且无法再标号未标号，且无法再标号, ,此时的流为此时的流为最大流最大流, ,此时的截集为此时的截集为最小截最小截4 4）重复（）重复（2 2））, ,（（3 3），依次进行的结局可能为：），依次进行的结局可能为：（（2,2,2 2））（（1,1,1 1））（（3,3,3 3））（（1,1,1 1））（（4,4,3 3））（（5,5,1 1））（（3,3,0 0））（（2,2,1 1））（（5,5,3 3））vsv2v1v3v4v6例例5 5 用标号法求下面网络的最大流。

用标号法求下面网络的最大流vtvt已标号，得到一条增广链已标号，得到一条增广链u(u(反向追踪反向追踪) )，转（，转（5 5）；）；vtvt未标号，且无法再标号未标号，且无法再标号, ,此时的流为此时的流为最大流最大流, ,此时的截集为此时的截集为最小截最小截4 4）重复（）重复（2 2））, ,（（3 3），依次进行的结局可能为：），依次进行的结局可能为：（（2,2））（（1,1））（（3,3））（（1,1））（（4,3））（（5,1））（（3,0））（（2,1））（（5,3））vsv2v1v3v4v6例例5 5 用标号法求下面网络的最大流用标号法求下面网络的最大流5)调整取 =θt，令，令，得新流，得新流 {f{fijij'}'}转转(1)(1)（（2,2））（（1,1））（（3,3））（（1,1））（（4,3））（（5,1））（（3,0））（（2,1））（（5,3））vsv2v1v3v4v6（（2,2））（（1,0））（（3,3））（（1,1））（（4,4））（（5,2））（（3,0））（（2,1））（（5,4））vsv2v1v3v4v6（（2,2,2 2））（（1,1,0 0））（（3,3,3 3））（（1,1,1 1））（（4,4,4 4））（（5,5,2 2））（（3,3,0 0））（（2,2,1 1））（（5,5,4 4））vsv2v1v3v4v6 此时标号无法进行，当前流为最大流，最大流量此时标号无法进行，当前流为最大流，最大流量为为5 5；最小截为；最小截为{(vs,v2), (v1,v3)}{(vs,v2), (v1,v3)}，截量为：，截量为：5 5练习：练习： 有三个发电站有三个发电站v1,v2,v3v1,v2,v3，发电能力分别为，发电能力分别为1515、、1010和和4040兆瓦，经输电网可把电力送到兆瓦，经输电网可把电力送到8 8号地区，电网能号地区，电网能力如图所示。

求三个发电站输到该地区的最大电力力如图所示求三个发电站输到该地区的最大电力v2v1v3v4v5v6v7v8401530154510151020v0101540v2v1v3v4v5v6v7v8401530154510151020（（1）由于网络图中只有一个发点和一个收点，所以）由于网络图中只有一个发点和一个收点，所以有必要添加一个虚设的起点有必要添加一个虚设的起点 和弧和弧 弧弧上各容量为上各容量为 ，分别为三点，分别为三点 的发电能力，如图所示：的发电能力，如图所示：v2v1v3v4v5v6v7v8401530154510151020v0101540101010101515151515150 0101010101010101015152525(2)由观察法得一初始可行流由观察法得一初始可行流 即图上所标即图上所标 为弧为弧 上容量，上容量， 为弧上流量为弧上流量 (2)(2)由观察法得一初始可行流由观察法得一初始可行流 即图上所标即图上所标 。

为弧为弧 上容量，上容量， 为弧上流量为弧上流量 v v3 3(40,10)(15,15)(30,10)(15,15)(45,25)(10,10)(15,15)(10,0)(20,10)v0(10,10)(15,15)(40,10)(3)(3)用标号法寻找可扩充链用标号法寻找可扩充链v v0 0||||||||v v6 6||||v v5 5v v4 4||||v v2 2v v1 1v v7 7v v8 8反向追踪，得一反向追踪，得一v v0 0-v-v8 8的可扩充链的可扩充链: :v0-v3-v6-v5-v2-v7-v8v0-v3-v6-v5-v2-v7-v8v v3 3(40,10)(15,15)(30,10)(15,15)(45,25)(10,10)(15,15)(10,0)(20,10)v0(10,10)(15,15)(40,10)v v0 0||||||||v v6 6||||v v5 5v v4 4||||v v2 2v v1 1v v7 7v v8 8(4)调整流量。

由可扩充链确定一新可行流调整流量由可扩充链确定一新可行流       ，可扩充链，可扩充链上前向弧上流量均增加上前向弧上流量均增加(45,35)(40,20)(10,10)(20,20)(30,20)(40,20)(5)(5)继续用标号法检验当前可行流是否为最大流继续用标号法检验当前可行流是否为最大流 v v3 3(40,20)(15,15)(30,20)(15,15)(45,35)(10,10)(15,15)(10,10)(20,20)v0(10,10)(15,15)(40,20)v v0 0||||||||v v6 6||||v v5 5v v4 4v v2 2v v1 1v v7 7v v8 8|||| 标号完毕，且终点未标号这说明网络中已找不到可扩充标号完毕，且终点未标号这说明网络中已找不到可扩充链，当前即为最大流，最大流流量为：链，当前即为最大流，最大流流量为： 20+15+1020+15+10＝＝4545即三个发电站输送到即三个发电站输送到8 8号地区的最大电力为号地区的最大电力为4545兆瓦  练习：练习：图中图中A A、、B B、、C C、、D D、、E E、、F F分别表示陆地和岛屿，分别表示陆地和岛屿，①②①②…………⒁⒁表示桥梁及其编号。

河两岸分别互为敌对的双方表示桥梁及其编号河两岸分别互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出编号）才能达部队占领，问至少应切断几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的试用图论方法进行分析到阻止对方部队过河的目的试用图论方法进行分析ABDEFC①①②②③③④④⑤⑤⑥⑥⑦⑦⑧⑧⑨⑨⑩⑩⑾⑾⑿⑿⒀⒀⒁⒁分析分析：转化为：转化为一个网络图，一个网络图，弧的容量为两弧的容量为两点间的桥梁数点间的桥梁数则问题为求最则问题为求最小截ABDEFC①①②②③③④④⑤⑤⑥⑥⑦⑦⑧⑧⑨⑨⑩⑩⑾⑾⑿⑿⒀⒀⒁⒁步骤步骤（（1 1）确定初）确定初始可行流始可行流 2112ABCDEF211121222211221(1)1(1)1(0)1(0)分析分析：转化为：转化为一个网络图，一个网络图，弧的容量为两弧的容量为两点间的桥梁数点间的桥梁数则问题为求最则问题为求最小截答案：答案：最小截为最小截为{AE{AE、、CDCD、、CF}CF}A AB BC CD DE EF F2(1)2(1)1(1)1(1)1(1)1(1)1(1)1(1)1(0)1(0)2(2)2(2)2(1)2(1)2(1)2(1)2(1)2(1)2(2)2(2)2(2)2(2)步骤步骤（（1 1）确定初）确定初始可行流始可行流 （（2 2）标号法求最大）标号法求最大流得最小截流得最小截1(0)1(0)1(0)1(0)2(0)2(0)2(0)2(0)2(0)2(0)ABDEFC①①②②③③④④⑤⑤⑥⑥⑦⑦⑧⑧⑨⑨⑩⑩⑾⑾⑿⑿⒀⒀⒁⒁ABDEFC①①②②③③④④⑤⑤⑥⑥⑦⑦⑧⑧⑨⑨⑩⑩⑾⑾⑿⑿⒀⒀⒁⒁F2ABCDE21111122222211221答案：答案：至少应当切至少应当切掉掉3座桥，分别是座桥，分别是AE：（：（12）号桥，）号桥，CD：：(7)号桥，号桥，CF：：(6)号桥号桥案例：案例：有一批人从我国有一批人从我国A A城赴俄罗斯城赴俄罗斯B B城，可能的旅行路线如城，可能的旅行路线如图：图： 边防队拟建立足够数量检查站以便使每辆汽车至少必经过边防队拟建立足够数量检查站以便使每辆汽车至少必经过一个检查站，建立检查站的费用根据各路段条件有所不同（如一个检查站，建立检查站的费用根据各路段条件有所不同（如图数字所示），求最小费用解。

图数字所示），求最小费用解aBAbcdefg468232573843764（分析：最小截问题）（分析：最小截问题） 分析分析：转化为一个网络图，弧的容量为各路段得费用转化为一个网络图，弧的容量为各路段得费用则问题为求最小截则问题为求最小截 步骤步骤a aB BA Ab bc cd de ef fg g4682325738437644(4)6(6)8(3)2(2)3(3)2(2)5(5)7(6)3(0)8(4)4(3)3(3)7(3)6(6)4(4)（（1 1）确定初始可行流）确定初始可行流（（2 2）标号法求最大流得最小截）标号法求最大流得最小截答案：答案：最小截为最小截为{Aa{Aa、、AbAb、、cb}cb}，即在这三个路段修建检查站，最，即在这三个路段修建检查站，最小费用为小费用为1313案例：案例：垃圾处理问题垃圾处理问题 某地区有某地区有3 3个城镇，各城镇每天产生的垃圾要运往该地区个城镇，各城镇每天产生的垃圾要运往该地区的的4 4个垃圾处理场处理，现考虑各城镇到各处理场的道路对各个垃圾处理场处理，现考虑各城镇到各处理场的道路对各城镇垃圾外运的影响。

假设各城镇每日产生的垃圾量、各处理城镇垃圾外运的影响假设各城镇每日产生的垃圾量、各处理场的日处理能力及各条道路（可供运垃圾部分）的容量（其中场的日处理能力及各条道路（可供运垃圾部分）的容量（其中容量为容量为0 0表示无此直接道路）如右表所示，试用网络流方法分表示无此直接道路）如右表所示，试用网络流方法分析目前的道路状况能否使所有垃圾都运到处理场得到处理，如析目前的道路状况能否使所有垃圾都运到处理场得到处理，如果不能，应首先拓宽哪条道路果不能，应首先拓宽哪条道路处理场处理场城镇城镇1234垃圾量垃圾量a302010050b00204070c5040205080处理量处理量60409030分析分析：转化为一个网络图，弧的容量为各路段能处：转化为一个网络图，弧的容量为各路段能处理垃圾的数量理垃圾的数量a ab bc c1 12 23 34 4s st t8080505040402020505060604040909030302020707030305050101020204040则问题为求最小截则问题为求最小截b b8080(80)(80)5050(30)(30)4040(20)(20)2020(0)(0)5050(30)(30)6060(60)(60)4040(40)(40)9090(20)(20)3030(30)(30)2020(20)(20)7070(20)(20)3030(30)(30)5050(50)(50)1010(0)(0)2020(20)(20)4040(0)(0)808050504040202050506060404090902020707030305050101020204040s s（（1 1）确定初始可行流）确定初始可行流3030（（2 2）标号法求最大流得最小截）标号法求最大流得最小截4 4c c3 32 21 1a at tb b8080(80)(80)5050(30)(30)4040(20)(20)2020(0)(0)5050(30)(30)6060(60)(60)4040(40)(40)9090(20)(20)3030(30)(30)2020(20)(20)7070(20)(20)3030(30)(30)5050(50)(50)1010(0)(0)2020(20)(20)4040(0)(0)s s（（3 3）反向追踪，找可扩充链）反向追踪，找可扩充链4 4c c3 32 21 1a at t9090(40)(40)2020(20)(20)5050(10)(10)4040(20)(20)7070(40)(40), ,得一得一s-ts-t的可扩充链的可扩充链: :s-b-4-c-3-ts-b-4-c-3-t，调整量，调整量b b9090(40)(40)5050(10)(10)4040(20)(20)7070(40)(40)8080(80)(80)5050(30)(30)4040(20)(20)2020(20)(20)6060(60)(60)4040(40)(40)3030(30)(30)2020(20)(20)3030(30)(30)5050(50)(50)1010(0)(0)2020(20)(20)（（4 4）重复标号）重复标号3 32 21 1a at ts s4 4c ca a2 21 1a a3 3（（5 5）反向追踪，找可扩充链）反向追踪，找可扩充链（（6 6）找到可扩充流）找到可扩充流S-b-4-c-3-t,S-b-4-c-3-t,调整量为调整量为1010b b8080(80)(80)5050(40)(40)4040(20)(20)2020(20)(20)6060(60)(60)4040(40)(40)3030(30)(30)2020(20)(20)3030(20)(20)5050(50)(50)1010(10)(10)2020(20)(20)3 32 21 1a at ts s4 4c ca a2 21 1a a3 3（（6 6）找到可扩充流）找到可扩充流S-b-4-c-3-t,S-b-4-c-3-t,调整量为调整量为10109090(50)(50)5050(0)(0)4040(30)(30)7070(50)(50)9090(50)(50)2020(20)(20)5050(0)(0)4040(30)(30)7070(50)(50)8080(80)(80)5050(40)(40)4040(20)(20)6060(60)(60)4040(40)(40)3030(30)(30)2020(20)(20)3030(20)(20)5050(50)(50)1010(10)(10)2020(20)(20)（（4 4）重复标号，直至终止）重复标号，直至终止3 32 21 1a at tc c3 32 21 1a at ts sb b4 4答案：答案：最小截为最小截为{sa{sa、、scsc、、b3 b3 、、4t },4t },垃圾最大处理量为垃圾最大处理量为180 180 < 50+70+80< 50+70+80答案答案 综上，目前的道路状况不能使所有垃圾都运到处综上，目前的道路状况不能使所有垃圾都运到处理场得到处理。

理场得到处理 从图上不难发现，理论上应当拓宽割集所在的从图上不难发现，理论上应当拓宽割集所在的道路但由于道路但由于sa,scsa,sc和和4t4t都是添加的虚拟道路，所以只有都是添加的虚拟道路，所以只有拓宽割集中的拓宽割集中的b3b3道路的路宽，或者增大道路的路宽，或者增大4 4号处理场处理垃号处理场处理垃圾的能力，才能解决问题圾的能力，才能解决问题 练习：练习：过纽约过纽约ALBANYALBANY的北的北- -南高速公路，路况通过能力如下南高速公路，路况通过能力如下图所示，图中弧上数字单位：千辆图所示，图中弧上数字单位：千辆/ /小时求（小时求（1 1）该路网能）该路网能承受的北承受的北- -南向最大流量；（南向最大流量；（2 2）若要扩充通过能力，应在那）若要扩充通过能力，应在那一组路段上扩充，说明原因一组路段上扩充，说明原因2143562366241331进入进入Albany（北）（北）离开离开Albany（南）（南）(1)(1)选取一个可行流选取一个可行流123546（进入进入Albany(Albany(北北) )离开离开Albany(Albany(南南) )2(2)4(1)3(0)1(1)6(5)3(3)2(2)3(3)6(2)1(1)V V1 1——V V4 4——V V2 2——V V5 5——V V6 6，可扩充量为，可扩充量为1 1，调整成新流，继续标号，调整成新流，继续标号, ,用标号法得可扩充链用标号法得可扩充链123546（进入进入Albany(Albany(北北) )离开离开Albany(Albany(南南) )2(2)4(2)3(1)1(1)6(5)3(3)2(2)3(3)6(3)1(0)标号终止，当前流为最大流，最大流量为标号终止，当前流为最大流，最大流量为8 8割集为：割集为：12, 4512, 45，， 4646，，3636应该在割集弧上扩大流量应该在割集弧上扩大流量[ [练习练习1]1][0, v[0, v1 1] ][4, v[4, v1 1] ][3, v[3, v1 1] ][5, v[5, v2 2] ][6, v[6, v2 2] ][9, v[9, v7 7] ][7, v[7, v4 4/ / v v6 6] ][8.5, v[8.5, v6 6] ][6, v[6, v2 2] ]v2v1v5v4v3v6v8v7v943232.533523421有有9 9个城市个城市v v1 1、、 v v2 2、、……v v9 9，其公路网如图所示。

其公路网如图所示弧旁数字是该段公路的长度，有一批物资要从弧旁数字是该段公路的长度，有一批物资要从v v1 1 运到运到v v9 9 ，问走哪条路最近？，问走哪条路最近？习题课练习（最小支撑树） 已知有已知有A A、、B B、、C C、、D D、、E E、、F F六个城六个城镇间的道路网络镇间的道路网络 如图，现要在六个城镇间架设通讯网如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图求络（均沿道路架设），每段道路上的架设费用如图求能保证各城镇均能通话且总架设费用最少的架设方案能保证各城镇均能通话且总架设费用最少的架设方案EACBFD51069353978284[ [练习练习2]2]第四节第四节 最小费用最大流问题最小费用最大流问题 在在实实际际的的网网络络系系统统中中，，当当涉涉及及到到有有关关流流的的问问题题的的时时候候，，我我们们往往往往不不仅仅仅仅考考虑虑的的是是流流量量，，还还经经常常要要考考虑虑费费用用的的问问题题比比如如一一个个铁铁路路系系统统的的运运输输网网络络流流，，即即要要考考虑虑网网络络流流的的货货运运量量最最大大，，又又要要考考虑虑总总费费用用最最小小。

最最小小费费用用最最大大流流问问题题就就是是要解决这一类问题要解决这一类问题 设设一一个个网网络络D=（（V，，A，，C）），，对对于于每每一一个个弧弧( (vi ,vj )∈∈A A , ,给给定定一一个个单单位位流流量量的的费费用用b bijij  0 0 ，，网网络络系系统统的的最最小小费费用用最最大大流流问问题题，，是是指指要要寻寻求求一一个个最最大大流流 f ，，并并且且流流的的总总费用费用 达到最小达到最小 而此时总费用而此时总费用b(f ' )比比b(f)增加了增加了我们将我们将 叫做这条叫做这条增广链的费用增广链的费用 我我们们首首先先考考察察，，在在一一个个网网络络D D中中，，当当沿沿可可行行流流 f f 的的一一条条增增广广链链μμ，，以以调调整整量量θθ=1=1改改进进f f ，，得得到到的的新新可可行行流流f f ' '的的流量，有流量，有 v v( (f ' f ' )= )= v v( (f f )+1)+1 显然，零流显然，零流f f ={0}={0}是流量为是流量为0 0的最小费用流。

一般地，的最小费用流一般地，寻求最小费用流，总可以从零流寻求最小费用流，总可以从零流f f ={0}={0}开始 问题是：如果已知问题是：如果已知f f 是流量为是流量为v v( (f f) )的最小费用流，如的最小费用流，如何寻找关于何寻找关于f f 的最小费用增广链？的最小费用增广链？结论：结论：若若f f 是流量为是流量为v v( (f f ) )的所有可行流中的费用最小，而的所有可行流中的费用最小，而   是关于是关于f f 的所有增广链中的费用最小的增广链，则的所有增广链中的费用最小的增广链，则 f f 沿沿增广链增广链μμ调整量为调整量为1 1得到的新可行流得到的新可行流f 'f ' ，一定是流量为，一定是流量为v v( (f f ' ' )+1)+1的所有可行流中的最小费用流的所有可行流中的最小费用流 依次类推，当依次类推，当 f 'f ' 是最大流时，就是所要求的最是最大流时，就是所要求的最小费用最大流小费用最大流若若u u是从是从v vs s到到v vt t关于关于f f的增广链，它的费用的增广链，它的费用 若果把若果把u u- - 中的边中的边( (v v i i , ,v vj j) )反向，并且令它的权反向，并且令它的权是是- -b bijij，而，而u u+ +中的方向不变，并且的它的权是中的方向不变，并且的它的权是b bijij，这样，这样就把求从就把求从v vs s到到v vt t关于关于f f 的最小费用增广链就转换成寻求的最小费用增广链就转换成寻求从从v vs s 到到v vt t 的最短路。

的最短路 构造一个赋权有向图构造一个赋权有向图 M M( ( f f ) )，其顶点是原网络，其顶点是原网络D D的顶的顶点，他的边根据点，他的边根据f f 的情况确定：的情况确定：若原图中（若原图中（v vi i ，，v vj j）边中）边中f fijij=0=0，则，则M M( ( f f ) )中连接（中连接（v vi i，，v vj j））, ,并令其权并令其权L(L(v vi i ,v,vj j)=)=b bijij；；若原图中（若原图中（v vi i，，v vj j）边中）边中f fij ij = =c cijij，则，则M M( ( f f ) )中连接（中连接（v vi i，，v vj j））, ,并令其权并令其权L(L(v vi i , ,v vj j)=-)=-b bijij；；若原图中（若原图中（v vi i，，v vj j）边中）边中f fijij=0=0，则，则M M( ( f f ) )中连接（中连接（v vi i，，v vj j）和）和( (v vj j , ,v vi i),),并令其权并令其权L(L(v vi i , ,v vj j )=)=b bij ij , L(, L(v vi i , ,v vj j )=-)=-b bijij ；； 步骤：步骤： （（1 1）取零流为初始可行流）取零流为初始可行流 ，，f f (0) ={0}(0) ={0}。

2 2））一一般般地地，，如如果果在在第第k-1k-1步步得得到到最最小小费费用用流流 f f ( (k k-1)-1)，，则则构构造图造图 L( L( f f ( (k k-1)-1) ) )3 3））在在L( L( f f ( (k k-1)-1) ) )中中，，寻寻求求从从v vs s到到v vt t的的最最短短路路若若不不存存在在最最短路，则短路，则f f ( (k k-1)-1)就是最小费用最大流；否则转就是最小费用最大流；否则转(4)(4)4 4））如如果果存存在在最最短短路路，，则则在在可可行行流流f f ( (k k－－1)1)的的图图中中得得到到与与此此最最短短路路相相对对应应的的增增广广链链，，在在增增广广链链上上，，对对f f ( (k k－－1)1)进进行行调调整整，，调调整整量为：量为：得到新可行流得到新可行流f f ( (k k) ) 对f f ( (k k) )重复上面步骤，返回（重复上面步骤，返回（2 2） 例例 求求图图8-24 8-24 所所示示网网络络中中的的最最小小费费用用最最大大流流，，弧弧旁旁的权是（的权是（b bij ij , c, cijij））. .(bij ,cij)(1, 8)(3,10)(2, 4)(6, 2)(1,7)(4, 10)(2, 5)v1v2vsv3vt图图 8-248-244 4(1, 8)(3,10)(2, 4)(6, 2)(1,7)(4, 10)(2, 5)v1v2vsv3vt(1)(3)(2)(6)(1)(4)(2)M(f(0))v1vsv2v3vt(1)(3)(2)(6)(1)(4)(2)M(f(0))v1vsv2v3vt(8,5)(10,0)(4,0)(2,0)(7,5)(10,0)(5,5)f(1),v( f (1))=5v1vsv2v2vtM(f (1))v1(2)v3(1)(3)(6)(1)(4)(2)(-1)vsv2vt( -1)(2,0)(5,5)(8,5)(4,0)(7,7)(10,2)(10,0)f (2),v( f (2))=7v1vsv2v3vtM( f (2) )(1)(3)(2)(6)(-1)(4)(-2)(-1)(-4)v1vsv3vtv2(8,8)(10,3)(4,3)(2,0)(7,7)(10,2)(5,5)f (3),v( f (3))=10v1vsv2v3vt (-1)(3)(2) (6)(-1)(4)  (-2) (-4)M( f (3) )(-2)  (-3)v1vsv2v3vt(8,8)(10,4)(4,4)(2,0)(7,7)(10,3)(5,4)f (4),v ( f(4)) =11v1vsv2v3vt(-1)(3)(-2)(6)(-1)(4) (2) (-4)M( f (4) )(-2)(-3)v1vsv2v3vt(8,8)(10,4)(4,4)(2,0)(7,7)(10,3)(5,4)f (4),v ( f(4)) =11v1vsv2v3vt由于在由于在M M( ( f f (4)(4)) )中已经不存在从中已经不存在从v vs s到到v vt t的最短路，因此，可行流的最短路，因此，可行流f f (4)(4)，，v(fv(f(4)(4)) )=11=11是最小费用最大流。

是最小费用最大流例例8.11 8.11 求网络的最小费用最大流，弧旁权是（求网络的最小费用最大流，弧旁权是（b bijij , c , cijij）） (3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)3 vsv2v1vtv31 64 12 2 (1)    L(f (0))(3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)0vsv2v1vtv3300333(2)  f ( 1) 1=3W(f(1))=3－－1(3)    L(f (1))－－2 3vsv2v1vtv31 64 12 －－1－－21vsv2v1vtv3400343 (4 )  f ( 2) 2=1W(f(2))=4(3 ,2)vsv2v1vtv3(1 ,4)(6 ,7)(4 ,8)(1 ,6)(2 ,5)(2 ,3)(5) L(f (2))－－3 vsv2v1vtv3－－1 4 12 －－2 －－23－－161vsv2v1vtv3401453 (6 )  f ( 3) 3=1W(f(3))=5THANK YOUSUCCESS2024/9/19132可编辑。