1、6.7 习习 题题本章内容重点本章内容重点 6.1 图与网络图与网络6.2 树树6.3 最短路问题最短路问题6.4 网络最大流问题网络最大流问题6.5 最小费用最大流最小费用最大流6.6 案例：网络的中心与选址问题案例：网络的中心与选址问题第六章第六章 网络规划与网络分析网络规划与网络分析概概 述述概概 述述6.1 6.1 图与网络图与网络哥尔斯保七桥问题：哥尔斯保七桥问题：哥尔斯保城有哥尔斯保城有一条普雷尔河，该河上有两个小岛，一条普雷尔河，该河上有两个小岛，河上有七座桥将这两个小岛及岛与河上有七座桥将这两个小岛及岛与河岸之间连接起来。河岸之间连接起来。问题问题是要从是要从A,B,C,DA,
2、B,C,D这四块陆这四块陆地中的任何一块开地中的任何一块开始，通过所有的桥始，通过所有的桥一次且仅一次，最一次且仅一次，最后回到开始出发的后回到开始出发的这块陆地。这块陆地。从图中可反映出从图中可反映出a球队球队分别与分别与b，c，d 球队有球队有赛事；球队还与赛事；球队还与c球队，球队，d球队还与球队还与e球队有赛球队有赛事事。图图a 这这5个球队之间的关系也可用图个球队之间的关系也可用图b)来反映。来反映。图图a)与与b)没有本质的差异没有本质的差异 可见表示球队间有无赛事关系是两点间可见表示球队间有无赛事关系是两点间的连线，而图中点的相对位置如何、点与的连线，而图中点的相对位置如何、点与
3、点之间联线的长短曲直，对反映对象之间点之间联线的长短曲直，对反映对象之间的关系并不重要。的关系并不重要。图图b例例 6-2 图图 6-2 是一张管道运输网示意图，是一张管道运输网示意图，代 表代 表 7 个 城 市 间 物 资 运 输 关 系，个 城 市 间 物 资 运 输 关 系，v1,v2,v3,v4,v5,v6,v7表示表示7个城市，箭线旁个城市，箭线旁数字表示物流的最大容量。现在要求出数字表示物流的最大容量。现在要求出从从v1地到地到v7地的运送的最大流方案。地的运送的最大流方案。图图 6-2 是由点及带箭头的连线所组成的图形。是由点及带箭头的连线所组成的图形。为区别起见，为区别起见，
4、把两点间不带把两点间不带箭头的连线称箭头的连线称为为，带箭头，带箭头的连线称为的连线称为。n这里所讲的图是反映对象之间关系的一这里所讲的图是反映对象之间关系的一种工具。电路网络、城市规划、信息传种工具。电路网络、城市规划、信息传递、物质结构、物资调配等也都可以用递、物质结构、物资调配等也都可以用点和线连接起来的图进行模拟。点和线连接起来的图进行模拟。（1）无向图）无向图,iijjiijevvvvvvV由点和边由点和边组成的图称为组成的图称为无向图无向图，如图，如图 6-1。图图 6-3即为无向图，图中：即为无向图，图中：12345(,)Vvvvvv128(,.,)Eeee顶点数：顶点数：点集点
5、集V中中元素的个数称为图元素的个数称为图G的顶点数，的顶点数，记为记为 。()|p GV如图如图 6-3，()5p G()|q GE如图如图 6-3，()8q G端点端点：对于边：对于边,iijevvE，e为为vi,vj的关联边。的关联边。图图 6-3 中，中，12,vv 为为2e 的端点，的端点，2e 为为12,vv 的关联边。的关联边。称称vi，vj为为e的端点。的端点。若点若点 vi,vj有边相连，即有边相连，即,ijevvE则称则称vi,vj 相邻，相邻，vi,vj 与与e关联关联。如图如图6.3 中，中，v3,v5相邻，相邻，v3,v5与与e7关联关联。图图6.3不含环和多重边的图称
6、不含环和多重边的图称为为简单图简单图，含有多重边的图称为多含有多重边的图称为多重图重图。(3)点的次（度）点的次（度）以点以点v为为端点的边数叫做点端点的边数叫做点v的次，记作的次，记作d(v)。如图如图6-3中，中，d(v1)=4，d(v2)=4。若若12(,.,)pVvvv，则称，则称12(),(),.,()pd vd vd v称为图称为图G的次序列。的次序列。()1()2()pGiidvqG定理定理 6-2 任何图任何图G=（V,E）中，奇点的个中，奇点的个数必为偶数。数必为偶数。n证：设图证：设图G中奇点与偶点的集合分别为中奇点与偶点的集合分别为V1和和V2，由定理由定理 6-1 知知
7、12()()()2()iViViVdvdvdvqG12VVV由于由于2q(G)为偶数，而为偶数，而 是若干个偶数是若干个偶数之和，也为偶数。所以之和，也为偶数。所以 必为偶数，必为偶数，即奇点的个数即奇点的个数 必为偶数。必为偶数。2()iVd v1()iVd v1|V（4）链）链链链：对于无向图：对于无向图G=（V,E）,称顶点和边交替的序列称顶点和边交替的序列 为连接为连接 的一条链，的一条链，简记为简记为 其中其中 ,称称 为链的为链的两个端点。图两个端点。图6-3 中的中的都是链。都是链。两个端点重合的链，称为两个端点重合的链，称为圈圈。在一个图中，如果。在一个图中，如果任何两个顶点之
8、间都有一条链，该图称为连通图。任何两个顶点之间都有一条链，该图称为连通图。1iitvv和1122,(1)(1),iiiiitititvevevev12,iiitvvv(1)(,),1,2,1ikikikveekt 1232451245,vvvvvvvvvv1iitvv和有向图是一个有序二元组（有向图是一个有序二元组（V,A），记为），记为D（V,A），），其中其中 是是p个顶点的集合，个顶点的集合，是是q条弧的集合，并且条弧的集合，并且 是一个有序二元组，记为是一个有序二元组，记为 并称并称 是以是以vi为始点，为始点，vj为终点为终点的弧，的弧，i，j的顺序不能颠倒，图中弧的方向用箭头标的顺
9、序不能颠倒，图中弧的方向用箭头标识。由点和弧组成的图称为有向图，如图识。由点和弧组成的图称为有向图，如图6-4。图中：。图中：12(,.,)pVvvv12(,.,)qAaaaia(,)(,),ijijjiijav vvvv vV12345,Vvvvvv129(,.,)Aaaaija两个端点重合的弧称环。如图两个端点重合的弧称环。如图 6-4 中的中的a1.图图6-4n两个端点之间的同向弧数大于等于两个端点之间的同向弧数大于等于2，称，称为为多重弧多重弧。n无环也无多重弧的有向图称为无环也无多重弧的有向图称为简单有向简单有向图。图。以点以点v为起点的弧数叫做点为起点的弧数叫做点v的出次，记作的出
10、次，记作以点以点v为终点的弧数叫做点为终点的弧数叫做点v的入次，记作的入次，记作称称 为点为点v的次。的次。()dv()dv()()()dvdvd v在有向图在有向图D=(V,A)中，点和弧交替的序列中，点和弧交替的序列1122,(1)(1),iiiii ti titPvavavav，若有，若有(1),ititi tavv或或(1),iti titavv，则称，则称P是一条链接是一条链接的有向路的有向路1iitvv和 三、网络三、网络 10ijijvea当点 与边 关联否则()ijp qAa构造一个矩阵构造一个矩阵 其中其中图图6.5则称则称A A为为G G的关联矩阵的关联矩阵。关联指顶点与边
11、的关系。关联指顶点与边的关系。12345612345110000101100010110001001000011eeeeeevvvvv图图6.5的关联矩阵的关联矩阵()ij p qAa10ijijva当点 与边v 相邻否则构造一个构造一个矩阵矩阵 其中其中图图6.66.6则称则称A A为为G G的邻接矩阵的邻接矩阵。邻接指顶点与顶点的关系。邻接指顶点与顶点的关系。12345123450110010110110010100100110vvvvvvvvvv图图6.66.6的邻接矩阵的邻接矩阵()ijpqAa0ijijijwvEa,v否则构造一个构造一个矩阵矩阵 其中其中图图6.76.7n则称则称A
12、 A为为G G的的权矩阵。权矩阵。12345123450740070260420030600500350vvvvvvvvvv图图6.76.7的权矩阵的权矩阵6.2 6.2 树树a）b）已知已知12345,vvvvv图图6.76.7（a a）12345,v v v v v图图 6.7（b）6.6.2.2.1 1 树树的的基基本本概概念念与与性性质质树的性质可用下面定理给出树的性质可用下面定理给出：设有图设有图G=(V,E)G=(V,E)，n n和和m m分别为图分别为图G G的顶点数和的顶点数和边数，则下列命题是等价的：边数，则下列命题是等价的：n（1 1）G G是一个树。是一个树。n（2 2）
13、G G无圈，且无圈，且m=n-1 m=n-1。n（3 3）G G连通，且连通，且m=n-1 m=n-1。n（4 4）G G无圈，但每加一条新边即存在唯一一个无圈，但每加一条新边即存在唯一一个圈。圈。n（5 5）G G 连通，但每舍去一条边就变成不连通。连通，但每舍去一条边就变成不连通。n（6 6）G G中任意两点，有唯一路相连。中任意两点，有唯一路相连。定义定义6-7 图图G=(V,E)G=(V,E)，若若EE是是E E的子集，的子集，VV是是V V的子集，且的子集，且EE中的边仅与中的边仅与VV中的顶点中的顶点相关联，则称相关联，则称G=(V,E)G=(V,E)是是G G的一个子的一个子图。
14、特别的，若图。特别的，若V=VV=V，则则GG称为称为G G的生成的生成子图子图（或支撑子图）（或支撑子图）定义定义6-8 若图若图G G的生成子图是一棵树，则称的生成子图是一棵树，则称该树为该树为G G的生成树，或简称为的生成树，或简称为图图G G的树的树。G G中中属于生成树的边称为属于生成树的边称为树枝树枝，不在生成树中，不在生成树中的边称为的边称为弦。弦。证明：必要性由定义直接可得。证明：必要性由定义直接可得。充分性的证明过程如下：充分性的证明过程如下：设图设图G G是连通的。若是连通的。若G G不含圈，则不含圈，则 G G就是其自就是其自身的一棵生成树；身的一棵生成树；若若G G含有
15、圈，任取一个圈，从圈中任意去掉含有圈，任取一个圈，从圈中任意去掉一条边，得到图一条边，得到图G G的一个生成子图的一个生成子图G G1 1。如果如果G G1 1不含圈，那么不含圈，那么G G1 1是是G G的一棵生成的一棵生成树；树；如果如果G G1 1仍含有圈，那么从仍含有圈，那么从G G1 1中任取一个中任取一个圈，从圈中再任意去掉一条边，得到图圈，从圈中再任意去掉一条边，得到图 G G的一个生成子图的一个生成子图G G2 2。重复使用此法使每个圈都受到破坏，重复使用此法使每个圈都受到破坏，最后可以得到最后可以得到G G的一个生成子图的一个生成子图G Gk k，它是不，它是不含圈的生成子图
16、。含圈的生成子图。这就是这就是G G一棵生成树。一棵生成树。6.2.2 6.2.2 最小支撑树及其算法最小支撑树及其算法l破圈法步骤：破圈法步骤：G=(V,E)为连通图，为连通图，Gk=(V,Ek)是是G的支的支 撑子图。撑子图。步骤步骤1 开始取开始取G0=(V,E)=G，k=0 步骤步骤2 若若Gk不含圈，则不含圈，则Gk为支撑树；若为支撑树；若Gk含圈，取含圈，取Gk中的任一圈，去掉圈上任一条边，中的任一圈，去掉圈上任一条边，得得Gk+1=(V，Ek+1)，Ek+1=Ekek;步骤步骤3 若若kq(G)-p(G)+1,则重复步骤则重复步骤 2；否；否则，则，Gk+1一定是支撑树。一定是支
17、撑树。避圈法步骤：避圈法步骤：为连通图。为连通图。步骤步骤1 1 始取始取 ；步骤步骤 2 2 若若G Gk k 连通，则连通，则G Gk k为支撑树；若为支撑树；若G Gk k不不连通，任选图连通，任选图G G边集边集E E中的一边中的一边e e，使，使e e的的两个端点分属两个不同的连通分图，两个端点分属两个不同的连通分图，得，得，；步骤步骤 3 3 若若 ，则重复步骤，则重复步骤 2 2；否则，否则，G Gk k一定是支撑树。一定是支撑树。(,)GVE0(,),0GVk111(,),1kkkkkGV EEEekk()1kp Gn（2 2）最小支撑树定义）最小支撑树定义设有一个连通图设有一
18、个连通图G G=(=(V V,E E),),每一边每一边e e=v vi i,v vj j 有一个权有一个权w w(e e)=)=w wijij，如果是的，如果是的一个支撑树，称中所有边的权之和为一个支撑树，称中所有边的权之和为支支撑树的权撑树的权，记为：，记为：如果支撑树如果支撑树T T*的权的权W W(T T*)是是G G的所有支的所有支撑树中权数最小的，则称撑树中权数最小的，则称T T*是是G G的最小支的最小支撑树（也称最小树），撑树（也称最小树），即即,()iijvvTw Tw*()m in():w Tw TTG是的 支 撑 树1）破圈法）破圈法 步骤：步骤：从图从图G中任取一圈，去
19、掉这个圈中任取一圈，去掉这个圈中权数最大的一条边，得一支撑子图中权数最大的一条边，得一支撑子图G1。在在G1中再任取一圈，再去掉圈中权数最中再任取一圈，再去掉圈中权数最大的一条边，得大的一条边，得G2。如此继续下去，一。如此继续下去，一直到剩下的子图中不再含圈为止。该子直到剩下的子图中不再含圈为止。该子图图G1就是的最小支撑树就是的最小支撑树T*。步骤步骤0 按照权的大小对边由小到大排序，按照权的大小对边由小到大排序，即即 令令 步骤步骤1 判断判断 是否含圈。如含圈，转步是否含圈。如含圈，转步骤骤2；否则，转步骤；否则，转步骤3.步骤步骤2 令令i=i+1。若。若im，转步骤，转步骤1；否；
20、否则，结束，没有支撑树，则，结束，没有支撑树，G 不联通。不联通。步骤步骤3 令令 。若。若j=n-1，结束，结束，T是最小树；否则，转步骤是最小树；否则，转步骤1。12()()()mwewewe1,0,ijT,1iTTejj图图6.86.8（a)a)图图6.86.8（b b）SS和S步骤步骤3 3 令令 步骤步骤4 4 重复步骤重复步骤2 2、步骤、步骤3 3，一直到图中，一直到图中所有点均包含在所有点均包含在S S中为止。中为止。jjSvSSvS，图图6.96.9（a a）图图6.9（b）问如何构建这个连问如何构建这个连接网络并分配建设接网络并分配建设费用？费用？图图6.106.10n设分
21、别承担的建设费用为设分别承担的建设费用为x1,x2,x3，则建，则建设费用的分配应该满足：设费用的分配应该满足：n有无限个向量有无限个向量满足上式，每个满足上式，每个向量都可以作为一个建设费用的分配方向量都可以作为一个建设费用的分配方案。案。12312132312309,010,011;17,18,11;18xxxxxxxxxxxx6.3 6.3 最短路问题最短路问题 在上一章中我们曾介绍了最短路问题在上一章中我们曾介绍了最短路问题的动态规划解法，但某些最短路问题（的动态规划解法，但某些最短路问题（如如道路不能整齐分段者道路不能整齐分段者）构造动态规划方程）构造动态规划方程比较困难，而图论方法
22、则比较有效。另外，比较困难，而图论方法则比较有效。另外，这个问题相对比较简单，其算法经常做为这个问题相对比较简单，其算法经常做为其他问题的子算法而调用。其他问题的子算法而调用。最短路问题是求一条最短路问题是求一条v v1 1v vj j的路的路 ，使它是从使它是从v v1 1到到v vj j的所有路中总权最小的路。的所有路中总权最小的路。即：优化问题即：优化问题6.3.1 基本概念与基本概念与Bellman方程方程 1,1,1,1m in():jjjjPw PPvv是的 路1,jP10 (6.1)m in,2,3,.,jkkjkjuB ellm anuuwjn方 程n定理定理 6-5 6-5
23、设有向网络设有向网络G G中只含正圈，并中只含正圈，并且从点且从点v v1 1到其余点到其余点 v vj j都有有限长度的有都有有限长度的有向路，那么向路，那么(6.1)(6.1)有唯一有限解。有唯一有限解。,ijijvvA(,)NVABellmanBellman算法的基本思想是：算法的基本思想是：基于这样的事实：从基于这样的事实：从v v1 1到到v vj j的最短路总的最短路总是沿着该路先到是沿着该路先到v vj j前面的某一点前面的某一点v vi i ，然后，然后再沿着再沿着(v(vi i ,v vj j)到到v vj j 。于是，若。于是，若v v1 1到到v vj j为最为最短路，则
24、短路，则v v1 1到到v vj j亦为最短路。亦为最短路。图图6.116.1112223334445550,m inm in011,m inm in011,m inm in05,1(2),131,m inm in11,140iiiiiiiiiiiiuuuwuuwuuwuuw n按照按照u ui i，求出最短路网络，图，求出最短路网络，图6-11(c)6-11(c)。nBellmanBellman方程的计算：方程的计算：6.3.2 Dijkstra算法算法 Dijkstra 算法也称为双标号法。算法也称为双标号法。也就是对图中的每个点也就是对图中的每个点vj 赋予两个参数（通赋予两个参数（通常
25、称为标号）常称为标号）：第一个标号第一个标号uj表示从起点表示从起点v1到到vj的最短路的最短路的长度，是距离标号；的长度，是距离标号；第二个标号第二个标号 称作前趋标号，是称作前趋标号，是记录在记录在v1到到vj的最短路上，的最短路上，vj 前面一个邻点前面一个邻点的下标，用来标识最短路路径，从而可对终的下标，用来标识最短路路径，从而可对终点到始点进行反向追踪，找到点到始点进行反向追踪，找到v1到到vj的最短的最短路。通过不断修改这些标号，进行迭代计算。路。通过不断修改这些标号，进行迭代计算。(,()jupredj()predjDijkstraDijkstra 算法：算法：步骤步骤0 0 给
26、起点给起点v v1 1标号标号(0,s)(0,s)，表示从，表示从v v1 1到到v v1 1的距离为的距离为0 0，v vs s为起为起 点。点。S 步骤步骤1 1 如果如果S S=V V，则，则u uj j即为即为v v1 1到到v vj j的最短的最短路的长度，最短路可路的长度，最短路可以按照以按照 predpred(j j)记记录的信息，反向追踪即可获得，结束。录的信息，反向追踪即可获得，结束。否则，转步骤否则，转步骤2。步骤步骤2 求出弧集求出弧集 。若若 ，表明从所有已经赋予标号的顶，表明从所有已经赋予标号的顶点出发，不再有这样的弧，它的另一顶点出发，不再有这样的弧，它的另一顶点尚
27、未标号，则计算结束。对于已有标点尚未标号，则计算结束。对于已有标号的顶点，可求得从到达这个顶点的最号的顶点，可求得从到达这个顶点的最短路，对于没有标号的顶点，则不存在短路，对于没有标号的顶点，则不存在从到达这个顶点的路。从到达这个顶点的路。若弧集，转步骤若弧集，转步骤3。A (,)|,ijijAv vvS vS步骤步骤3 3 对弧集对弧集A A中的每一条弧中的每一条弧(v vi,i,v vj j)，计算计算 则则v vi i 赋予双标号赋予双标号 其中其中 。转步骤转步骤 2 2min:,iijijiijuwvvAuw(,)juijii juuw jSSv 经上述一个循环的计算，将求出经上述一
28、个循环的计算，将求出v v1 1到一到一个顶点个顶点v vj j的最短路及其长度，从而使一个顶的最短路及其长度，从而使一个顶点点v vj j得到双标号。得到双标号。若图中总共有若图中总共有n n个顶点，则最多计算个个顶点，则最多计算个(n n-1)-1)循环，即可得到最后结果。循环，即可得到最后结果。图图6.121 Sv234567,Sv v v v v v234567,Svvvvvv:,iijijuwv vA14,Sv v23567,Svvvvv:,iijijuwv vA1213(,)|,(,),(,)ijijAv vvS vSv vv v124,Sv vv132325(,),(,),(,)
29、,(,)ijijAv vvS vSv vvvvv3567,Svvvv567,Svvv1234,Sv vvv25(,),(,)ijijAv vvS vSvv57(,),(,)ijijAv vvS vSvv12345,Sv vvvv67,Svv6Sv123457,Svvvvvv(,),ijijAv vvS vS 6Sv图图 6.13至此，自顶点至此，自顶点 V1至其余顶点的最短至其余顶点的最短路都已求得。如图路都已求得。如图 6.13粗线所示。粗线所示。6.3.3 Floyd-Warshall算法算法 Floyd-Warshall算法是求网络中任意算法是求网络中任意两点间的最短路的算法，这个算法的
30、基本两点间的最短路的算法，这个算法的基本思想就是思想就是标号修正标号修正。为 计 算 方 便，令 网 络 的 权 矩 阵为 计 算 方 便，令 网 络 的 权 矩 阵为为 ，为为 到到 的距离。的距离。()ijnnwwivjvijw111,0,m i n,i ii ji jkkki ji ji ll jliljuuwijuuuwkijuniju1niju21nnijijuu图图6.14解：解：用用 表示表示各顶点对之间通过不超过各顶点对之间通过不超过k k条弧所能够到达的最短路的长度矩阵，则条弧所能够到达的最短路的长度矩阵，则计算结果如下：计算结果如下：首先给出通过不超过首先给出通过不超过1
31、1条弧即可到达的条弧即可到达的长度长度矩阵矩阵()kD(1)0430756060D40min643 n到不超过到不超过2 2条弧即可到达的长度条弧即可到达的长度 就是就是D(1)第一行与第一行与它第二列对应元素它第二列对应元素之和的最小值之和的最小值n到不超过到不超过2条弧即可到达的长度条弧即可到达的长度 04m in3036(3)就是就是D(1)第一行与第一行与它第三列对应元素它第三列对应元素之和的最小值之和的最小值到不超过到不超过2 2条弧即可到达的长度条弧即可到达的长度 ；3 0min374 其他同样计算。其他同样计算。就是就是D(1)第一行与第一行与它第四列对应元素它第四列对应元素之和
32、的最小值之和的最小值(2)04330175601111260Dn各顶点对之间通过不超过各顶点对之间通过不超过k k(3,4)(3,4)条弧所能条弧所能够到达的最短路的长度矩阵如下：够到达的最短路的长度矩阵如下：(3)043340175601111260D(4)043340175601111260Dn我们看到我们看到 则则 中的长度就是中的长度就是最短路长度。最短路长度。(3)(4)DD(3)D6.4 网络最大流问题网络最大流问题6.4.1 基本概念与模型基本概念与模型考虑：考虑：如何安排运输方案，使得从起如何安排运输方案，使得从起点点v1运到终点运到终点v6的总运量达到最大？的总运量达到最大？
33、(,).0ijDV A CcijfijFf 弧旁括号中的两个数字弧旁括号中的两个数字 ，第一，第一个数字表示弧容量，第二个数字表示通过个数字表示弧容量，第二个数字表示通过该弧的流量，如弧（该弧的流量，如弧（vs,v2 2）上的）上的(5(5，1)1)，(,)ijijcf，图图6160ijijfc（2 2）可行流与最大流）可行流与最大流 2 2）节点流量平衡条件）节点流量平衡条件：网络中的流量：网络中的流量必须满足守恒条件，对收发点来说，发点必须满足守恒条件，对收发点来说，发点的总流出量的总流出量=收点的总流入量；收点的总流入量；对中间点对中间点v v1 1,v v2,2,v v3 3,v v4
34、 4 来说，中间点的来说，中间点的总流入量总流入量=总流出量。前者是可通过该弧的总流出量。前者是可通过该弧的最大流量为最大流量为 5 5，后者是目前通过该弧的流，后者是目前通过该弧的流量量 1 1。(,)(,)m ax().0(,)()0,()ijijijijijijjivvAvvAvfs tfcvvAvfisffis tvfitijffijijfcijijfc0ijf0ijf增广链：增广链：对于可行流对于可行流 f f，是一条从是一条从 v vs s 到到v vt t的链，如果的链，如果 中的每条弧均为非饱和弧，中的每条弧均为非饱和弧，且且 中的每条弧均为非零流弧，则称中的每条弧均为非零流弧
35、，则称链链是关于是关于f f 的增广链。的增广链。sV,sstsssssvV vVVVVVV且(,)(,)|,ssijijsVVvvAvVvV(,)ssVV（4）截集和截量）截集和截量ssVV和sVssVV和 截集截集 中所有弧的容量之和称为中所有弧的容量之和称为该该截集的截量截集的截量，记为，记为 ，有，有 在在 D的所有截集中，称截量最小的截集的所有截集中，称截量最小的截集为为最小截集。最小截集。,(,)(,)(,)ijssssijvvVVC VVc(,)ssC VV(,)ssVV1234,ssstVvvvVvvv1324(,)(,),(,)ssVVvvvv1324(,)426ssC VV
36、cc1234,ssstVvvVvvvv13122(,)(,),(,),(,)sssVVvvvvvv13122(,)41510sssC VVccc()(,)ssvfC VV,(,)(,)(,)(,)(,)(,)(,)(,)()(,)ijs sijs sijs sijs si jj ii ji jssv vV Vv vV Vv vV Vv vV Vv ffffcCV V 证明如下：证明如下：由该结论可知：由该结论可知：在一个容量网络中，最大流的流量小在一个容量网络中，最大流的流量小于等于最小截集的截量。于等于最小截集的截量。如果存在一可行流如果存在一可行流 f f*和一个截量和一个截量 使得使得
37、则则 f f*就是最大流，且就是最大流，且 是最小是最小截集。截集。*,)ssVV（*()(,)ssvfC VV*,)ssVV（n判断一个可行流是否为最大流，有两种途判断一个可行流是否为最大流，有两种途径：径：一是能否找出一是能否找出v vs s到到v vt t的增广链，若能，的增广链，若能，则说明则说明f f不是最大流；否则不是最大流；否则f f就是最大流。就是最大流。二是看二是看V V(f f)是否等于最小截量。若是否等于最小截量。若等，则等，则f f就是最大流，否则就不是最大流。就是最大流，否则就不是最大流。6.4.2 Ford-Fulkerson6.4.2 Ford-Fulkerson
38、标号算法标号算法 若无，则若无，则 f f 为所求的最大流；为所求的最大流；若有，则在增广链上进行调整，改变若有，则在增广链上进行调整，改变流量，得一新的可行流流量，得一新的可行流 ，继续寻找相，继续寻找相应于该可行流的增广链。应于该可行流的增广链。f 在标号过程中，每个点属于且仅属在标号过程中，每个点属于且仅属于下列集合之一：已标号，但未检查的于下列集合之一：已标号，但未检查的点集点集V V0 0；已标号，已检查的点集；已标号，已检查的点集V Vs s ；未标号的点集未标号的点集 sV 首先给首先给V Vs s 标号标号(0(0，+)+)，因，因V Vs s是发点，是发点，故括弧中第一个数字
39、记为故括弧中第一个数字记为 0 0。括弧中第二。括弧中第二个数字表示从上一标号点到这个标号点的个数字表示从上一标号点到这个标号点的流量的最大允许调整值。流量的最大允许调整值。V Vs s为发点，不限为发点，不限允许调整量，故为允许调整量，故为+。此时此时 012,.,ssstVvVVvvv sV（a a）对于前向弧对于前向弧(v vi,i,v vj j)，若非饱和，若非饱和，则给点则给点 v vj j 标以标以(v vi i,l l(v vj j)），其中），其中 同时把同时把 v vj j 从从 中除去，归入中除去，归入V V0 0 。()m in(),jiijijl vl vcfsV（b）
40、对于后向弧对于后向弧(vj,vi)，若非零流，则给，若非零流，则给点点vj 标以标以(-(-v vi i,l l(v vj j)），其中，其中，同时把同时把 vj 从从 中除去，归入中除去，归入V0。()m in(),jjjil vl vfsV(,)(,)(,)ijijijijijijijfvvffvvfvv作 调 整：(,)(,)0m inm in(),m inijijijijjiijijjivvfcvvfcff当时，；当时，此 时，取 调 整 量 则调整之后仍为可行流，流值比原则调整之后仍为可行流，流值比原来的可行流流量增大了来的可行流流量增大了(0)0)。*(,)ssVV*ijff*()
41、(,)ssVfC VV例例6-10 6-10 试用试用 FordFordFulkerson Fulkerson 标号法标号法求图求图 6 61818所示的网络最大流，括号中，所示的网络最大流，括号中，第一个数字是容量，第二个数字是流量。第一个数字是容量，第二个数字是流量。01234,ssstVvVVvvvvv 22(,()svvL v222(,),sssvvfc111(,),3sssvvfc02134,ssstVvVvVvvvv222()min,()min,(51)4ssL vcfl第一步，第一步，图中已给出可行流图中已给出可行流f f；01234,ssstVvVvvVvvv1212()min
42、(),min4,11L vL vf121(,()vvL v1210f24242fcn检查点检查点V V1 1：弧弧(V(V1 1，V V3 3)，为非饱和弧，所以对，为非饱和弧，所以对V V3 3 标号。标号。，其中，其中弧弧(V(V4 4，V V1 1)，为非零流弧，所以给，为非零流弧，所以给V V4 4 标号，标号，其中，其中此时此时03421,ssstVvvVvvvVv4141()min(),min1,11L vL vf4110f313(,()vvL v1313fc311313()min(),()min1,(43)1L vL vcf414(,()vvL vn检查点检查点V V3 3 ：弧
43、弧(V(V3 3，V Vt t)，为非饱和弧，所以对，为非饱和弧，所以对V Vt t 标号。标号。，其中，其中由于由于Vt已已标号，不需再检查标号，不需再检查 V V4 4。3(,()ttvvL v33ttfc333()min(),()min1,(53)1tttL vL vcf213,stvvvvv1213312(,),(,),(,),(,)stvvvvvvvv2221313133312123112(,)314(,)314(,)110(,)(,)ssststtijtijijffvvffvvffvvfffvvfvv 调整后的可行流如图调整后的可行流如图 6.216.21所示。对所示。对这个新的可
44、行流重新在图中进行标号，这个新的可行流重新在图中进行标号，寻找新的增广链。寻找新的增广链。图图 6.216.21(,3)sv02134,ssstVVvvVvvvv*124(,)(,),(,)sssVVvvvv*124()(,)325sssVfC VVcc,()()ijijijijijijvvvvijijvvvvbfbfbbbb 6.5 最小费用最大流最小费用最大流 1 1时，费用的增加量是时，费用的增加量是,ijijijijvvvvbb 这个数值反映了增广链的好坏，这个这个数值反映了增广链的好坏，这个数值越小，这条增广链就越好。数值越小，这条增广链就越好。,ijijijijvvvvbb 确定一
45、个最小费用可行流确定一个最小费用可行流,然后找出然后找出最小费用增广链，按照最小费用增广链最小费用增广链，按照最小费用增广链对可行流进行调整，一直调整下去，直对可行流进行调整，一直调整下去，直到找不出增广链为止，这样得到的可行到找不出增广链为止，这样得到的可行流即为流即为最小费用最大流最小费用最大流。,ijijijijijijbfcwfc,0,0ijijjiijbfwf弧的赋权原则如下：弧的赋权原则如下：对于弧对于弧 ，有，有对于弧对于弧 ,有有当然，长度为当然，长度为+的弧可以略去。的弧可以略去。若不存在最短路，则目前的可行流若不存在最短路，则目前的可行流F(k)即为网络即为网络D的最小费用
46、最大流；若存在最短的最小费用最大流；若存在最短路，则在原网络路，则在原网络D中得到了相应的最小费用中得到了相应的最小费用增广链增广链，对，对F(k)进行调整，调整量为进行调整，调整量为()()m inm in(),m in()kkijijijuucff(),(1)(),ijijijijijbkvvfkbkvv例例6.11 6.11 求网络（图求网络（图6.206.20）的最小费用）的最小费用最大流，弧旁的数字为最大流，弧旁的数字为(,)ijijbc图图6.206.20(,)ijijijbcf图图6.216.21图图6.226.22(Df（0)）中最短路见图中最短路见图6-226-22中的粗线所
47、中的粗线所示，由此找到最小费用增广链，见图示，由此找到最小费用增广链，见图6-216-21中粗线所示。中粗线所示。(Df（0)）图图6.236.23（2 2）继续进行可行流的调整：）继续进行可行流的调整：在图在图6-236-23中中 是饱和弧，是饱和弧，它们只能作后向弧；它们只能作后向弧；既是非既是非0 0流弧，流弧，又非饱和弧，因此它既作前向弧，也作后又非饱和弧，因此它既作前向弧，也作后向弧，其他弧只是向弧，其他弧只是0 0流弧，只能做前向弧。流弧，只能做前向弧。新赋权网络如图新赋权网络如图6.246.24所示：所示：113,svvvv3tvv图图6.246.24 图图6-246-24中的最
48、短路见粗线所示，因此中的最短路见粗线所示，因此找到最小费用增广链，见图找到最小费用增广链，见图6-236-23中粗线所中粗线所示。利用最小费用增广链对可行流进行调示。利用最小费用增广链对可行流进行调整，调整后的新流见图整，调整后的新流见图6-256-25。图图6.256.25图图6.266.26stvv6.6 网络计划技术网络计划技术l 网络图的绘制网络图的绘制l 网络图的时间参数计算网络图的时间参数计算l 网络优化网络优化为了编制网络计划，首先需绘制网为了编制网络计划，首先需绘制网络图。网络图是由络图。网络图是由节点节点(点点)、弧及权、弧及权所所构成的有向图。即构成的有向图。即有向的赋权图
49、有向的赋权图。一、网络图的绘制一、网络图的绘制节点节点表示一个事项（或事件），它表示一个事项（或事件），它是一个或若干个工序的开始或结束，是是一个或若干个工序的开始或结束，是相邻工序在时间上的分界点。节点用圆相邻工序在时间上的分界点。节点用圆圈和里面的数字表示，数字表示节点的圈和里面的数字表示，数字表示节点的编号，如，编号，如，等。等。弧弧表示一个工序，工序是指为了完表示一个工序，工序是指为了完成工程项目成工程项目,在工艺技术和组织管理上相在工艺技术和组织管理上相对独立的工作或活动。一项工程由若干对独立的工作或活动。一项工程由若干个工序组成。工序需要一定的人力、物个工序组成。工序需要一定的人力
50、、物力等资源和时间。弧用箭线力等资源和时间。弧用箭线“”“”表示。表示。权权表示为完成某个工序所需要的时表示为完成某个工序所需要的时间或资源等数据。通常标注在箭线下面间或资源等数据。通常标注在箭线下面或其它合适的位置上。或其它合适的位置上。例例1 1 某项研制新产品工程的各个工序与所某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如下表所需时间以及它们之间的相互关系如下表所示。示。要求编制该项工程的网络计划。要求编制该项工程的网络计划。根据上表绘制的网络根据上表绘制的网络,如图如图6.286.28所示。所示。b12467835a6045 c10d20e40f18g30h15k25l
