《运筹学第06章图论概述ppt课件》由会员分享，可在线阅读，更多相关《运筹学第06章图论概述ppt课件（76页珍藏版）》请在金锄头文库上搜索。
1、运筹学运筹学 第六章第六章 图论概述图论概述本章重点本章重点n图的根本概念n常见的四个问题的求解方法图的含义图的含义n图是一种模型n如公路、铁路交通图，通讯网络图等n图是对现实的笼统n很多问题都可以用顶点和边来表示，普通顶点表示实体，边(顶点与顶点之间的连线)表示实体之间的关系，顶点和边的集合定义为图图论的提出图论的提出(1)n用图来描画事物及其联络，最早是由瑞士数学家欧拉(Euler)于1736年处理哥尼斯堡七桥问题时提出的n如右图所示，哥尼斯堡地域被河流分为了四个区域，四个区域之间有七座桥相连，问能否有一条道路，可以经过一切的桥并且每座桥只经过一次？BACD图论的提出图论的提出(2)n用图
2、来表示这个问题n用四个顶点表示四个地域n用七条边表示七座桥n要寻觅这样的一条道路：经过一切的边并且每条边只经过一次n该问题曾经证明无解图的根本概念图的根本概念(1)n图：顶点和点和边的集合的集合n点的集合用点的集合用V表示，表示，边的集合用的集合用E表示，那表示，那么么图可以表示可以表示为G=(V, E)n如以下如以下图G=(V, E)其中，V=A, B, C, D E=e1, e2, e3, e4, e5, e6, e7 E中，e1=(A, D), e2=(B, D), e3=(C, D) e4=(B, C), e5=(A, C), e6=(A, C), e7=(B, C)e2e1e3e4e
3、5e6e7图的根本概念图的根本概念(2)n边都没有方向的图称为无向图，前面所讲的图就是无向图。无向图的边eij=(vi, vj)=(vj, vi)= ejin当图中的边都有方向时，称为有向图。为了区别于无向图，有向图用G(V,A)表示n在有向图中，有向边又称为弧，用 aij=(vi, vj)表示， (vi, vj)(vj, vi)，弧的方向用箭头标识n既有边又有弧的图称为混合图n以下图中从左向右依次为：无向图，有向图，混合图图的根本概念图的根本概念(3)n集合V中元素的个数称为图G的顶点数，记作p(G)。前例中，p(G)=4n集合E(或A)中元素的个数称为图G的边数，记作q(G)。前例中，q(
4、G)=7n假设e=(u, v)E(或a=(u, v)A)，那么称u和v为e (或a )的端点，e (或a )称为顶点u和v的关联边，也称u, v与边e (或a )相关联。前例中，A, B是边e1 的端点，e1 是A, B的关联边n假设顶点u和v与同一条边相关联，那么称u和v为相邻点n假设两条边ei 和ej 有同一个端点，那么称ei 和ej 为相邻边图的根本概念图的根本概念(4)n假设一条边的两个端点是同一个顶点，那么称该边为环n假设两个端点之间有多于一条边，那么称为重边(书上称为多重边)，前例中，A, C之间和B, C之间都有两条边n无环也无重边的图称为简单图n与顶点v相关联的边的数目，称为该
5、顶点的“度(书上称为次)，记为d(v)n度数为奇数的顶点称为奇点，度数为偶数的顶点称为偶点n在有向图中，由顶点指向外的弧的数目称为正度，记为d+，指向该顶点的弧的数目称为负度，记为 dn度数为0的点称为孤立点，度数为1的点称为悬挂点图的根本概念图的根本概念(5)n与悬挂点衔接的边称为悬挂边n假设图中一切的点都是孤立点，那么称为空图n定理6.1n一切顶点的度数之和，等于一切边数的两倍n缘由：每条边关联两个顶点，计算顶点的度数时，每条边计算了2次n定理6.2n图中奇点的个数总是偶数个n缘由：一切顶点的度数之和是偶数，偶点的度数之和也是偶数，因此，奇点的度数之和必为偶数，因此，奇点的个数必是偶数个图
6、的根本概念图的根本概念(6)n点边交错序列v0, e1, v1, e2, v2, , vn-1, en, vn 称为链。其中v0称为路的起点， vn称为路的终点n假设v0vn，称为开链；反之，称为闭链(对于无向图而言，也称为回路)n假设链中所含的边均不一样，称为简单链n假设链中所含的顶点均不一样，称为初等链(对于无向图而言，也称为通路)n除起点和终点外均不一样的闭链，称为圈(对于无向图而言，也称为初等回路)以上概念(除特别标注的外)对无向图和有向图均适用图的根本概念图的根本概念(7)n在有向图中，点边交错序列v0, e1, v1, e2, v2, , vn-1, en, vn (其中ek=(v
7、k-1, vk) )称为路n假设v0vn，称为开路；反之，称为回路(留意和无向图的回路区分开来)n假设路中所含的边均不一样，称为简单路n假设路中所含的顶点均不一样，称为初等路n除起点和终点外均不一样的回路，称为初等回路(留意和无向图的初等回路区分开来)本页概念都是针对有向图图的根本概念图的根本概念(8)n假设一个图(无向图或有向图)中恣意两点之间至少有一条初等链衔接，那么称该图为连通图，否那么称为不连通图n在一个有向图中，假设恣意两点u和v， u到v和v到u之间都至少有一条初等路衔接，那么称该图为强连通图，否那么称为非强连通图图的根本概念图的根本概念(9)n子图：设子图：设G1=(V1, E1
8、 )，G2=(V2, E2 )，假设，假设V1 V2， E1 E2，那么称，那么称G1是是G2的子图的子图n注：生成子注：生成子图时，可以只，可以只选顶点不点不选与与该顶点相关点相关联的的边，但不能只，但不能只选边不不选与与该边相关相关联的的顶点点n如以下图，右图是左图的子图图的根本概念图的根本概念(10)n如以下图，右图是左图的真子图n真子图：假设真子图：假设V1 V2， E1 E2，称，称G1是是G2的真的真子图子图n部分图：假设部分图：假设V1=V2， E1 E2，称，称G1是是G2的部的部分图分图图的根本概念图的根本概念(11)n导出子图：假设导出子图：假设V1 V2，E1=(ui,
9、vj) E2 | ui V1, vj V1，称，称G1是是G2中由中由V1导出的导出子图，记作导出的导出子图，记作G(V1)n如以下图，右图是左图的导出子图图的根本概念图的根本概念(12)n一个没有圈的图称为无圈图或称为林n一个连通的无圈图称为树n一个林的每个连通子图都是一个树n定理6.3：关于树的以下描画是等价的n无圈连通图(定义)n无圈图G，q(G)=p(G)-1(定义+对顶点个数用归纳法)n连通图G，q(G)=p(G)-1(定义+对顶点个数用归纳法)n无圈，但添加一条边可以得到独一的圈(定义+对顶点个数用归纳法)n连通，但去掉一条边就不连通(反证法)n每一对顶点之间有且仅有一条初等链(反
10、证法)图的根本概念图的根本概念(13)n假设T是图G的部分图，且T是树，那么称T为G的生成树(书上称为部分树)图的存储方式图的存储方式(1)n计算机中存储图普通采用矩阵存储n常用的存储方法有两种n邻接矩阵n关联矩阵图的存储方式图的存储方式(2)n对于无向图，邻接矩阵存储方式如下n假设顶点vi 和vj 之间没有边，那么aij =aji=0n假设顶点vi 和vj 之间存在n条边，那么aij =aji=nn注：普通 i jv1v2v3v4v5图的存储方式图的存储方式(3)v1v2v3v4v5n对于有向图，邻接矩阵存储方式如下n假设顶点vi 和vj 之间没有弧，那么aij =0n假设顶点vi 和vj
11、之间存在n条弧(vi , vj )，那么aij =nn注：允许 i = j图的存储方式图的存储方式(4)n对于无向图，关联矩阵存储方式如下n假设顶点vi 不和边ej 相关联，那么bij =0n假设顶点vi 和边ej 相关联，那么bij =1v1v2v3v4v5e1e2e3e4e5e6e7e8e9e9 关联的顶点个数为1，是自环图的存储方式图的存储方式(5)n对于有向图，关联矩阵存储方式如下n假设顶点vi 不和弧ej 相关联，那么bij =0n假设顶点vi 是弧ej 的起点，那么bij =1n假设顶点vi 是弧ej 的终点，那么bij =-1n假设顶点vi 既是弧ej 的起点又是弧ej 的终点，
12、那么bij =2v1v2v3v4v5e1e2e3e4e5e6e7e8e9简单图的权值矩阵简单图的权值矩阵(1)n对于赋权简单图，权值矩阵存储方式如下n假设顶点vi 和vj 之间没有边，那么wij =0n假设顶点vi 和vj 之间有边(vi , vj ) ，那么wij =相应边的权值n注：无向图和有向图均适用，有向图要留意边的方向简单图的权值矩阵简单图的权值矩阵(2)v1v2v3v4v5376245v1v2v3v4v5376245最短道路问题最短道路问题n普通针对赋权连通图(有向图或无向图皆可) ，求两点之间所经道路权值之和为最小的道路n求解该问题可以采用上一章引见的动态规划的方法n该方法适用于
13、无负初等回路(指一切边的权值之和为负值的初等回路)的赋权连通图(有向图或无向图皆可)；假设有负初等回路，那么不存在最短道路n该方法需求人工划分阶段，适宜人工计算n书上引见的三种算法，不需求明确的划分阶段，较为适宜计算机运算狄克斯拉狄克斯拉(Dijkstra)(Dijkstra)算法算法(1)(1)n该算法有两个根据n从v1 到vn 的最短道路也是从vn 到v1 的最短道路n对于无向图必定成立n对于有向图而言，vn 到v1 的最短道路是指将图中弧的方向反过来，但权值不变时的最短道路n以vn 为起点，v1 为终点运用动态规划的最优性原理n第一条根据保证了按这种方法求得的结果是从v1 到vn 的最短
14、道路狄克斯拉狄克斯拉(Dijkstra)(Dijkstra)算法算法(2)(2)n算法步骤n知网络的间隔矩阵L=(lij)，lij表示vi到vj的弧上的间隔权值n令i=1，S1=v1，S2=v2, v3, , vn，令P(v1)=0，T(vj)=vjS2n令T(vj)=minT(vj)，P(vi)+lij | vjS2n令vk=minT(vj)| vjS2，P(vk)=T(vk)n假设vk=vn，那么曾经找到v1到vn的最短间隔P(vk)n否那么，令i=k，从S2中删去vi，转上一步狄克斯拉狄克斯拉(Dijkstra)(Dijkstra)算法算法(3)(3)n该算法适用于无负初等回路的赋权连通
15、图(有向图或无向图皆可)，但算法本身不能断定图中能否存在负初等回路n因此，该算法普通运用于无负权值的赋权连通有向图或无向图例如例如(6.1-1)sabcdt5839149543n道路图如下所示，箭头表示通行方向，线上数字表示道路长度，试用Dijkstra 算法求s到t的最短道路例如例如(6.1-2)sabcdt初始值T( )第1次P( )+ lijT( )第2次P( )+ lijT( )第3次P( )+ lijT( )第4次P( )+ lijT( )第5次P( )+ lijT( )00+50+80+0+0+585+5+35+95+88148+8+48+8128+38+9111711+51612
16、345例如例如(6.1-3)sabcdt5839149543海斯算法海斯算法(1)(1)n该算法有两个根据n从v1 到vn 的最短道路也是从vn 到v1 的最短道路n对于无向图必定成立n对于有向图而言，vn 到v1 的最短道路是指将图中弧的方向反过来，但权值不变时的最短道路n假设从vi 到vj 的最短道路经过vk ，那么vi 到vk 、vk 到vj 的都是相应的最优道路n第一条根据保证了从vi 到vj 的最短道路也是从vj 到vi 的最短道路n那么根据动态规划最优性原理，vk 到vj 和vk 到vi都是相应的最优道路，由此得到上面的结论海斯算法海斯算法(2)(2)n算法步骤n知网络的间隔矩阵L
17、=(lij)，lij表示vi到vj的弧上的间隔权值n令dij(0)= lij，i=1n，j=1nndij(t)表示从vi到vj的2t步间隔n当dij(m-1)知时，令n dij(m)=mindik(m-1)+dkj(m-1)| k=1nn当对一切的i, j有dij(m)=dij(m-1)时，dij(m)是vi到vj的最短间隔。否那么，假设2m-1n-1，m=m+1，转上一步；假设2m-1n-1，阐明存在负初等回路，最短道路不存在，算法停顿海斯算法海斯算法(3)(3)n该算法可以判别能否存在负初等回路，适用于恣意权值的赋权连通有向图或无向图n所得的结果矩阵中包含了图中恣意两点之间的最短间隔例如例
18、如(6.2-1)sabcdt5839149543n道路图如下所示，箭头表示通行方向，线上数字表示道路长度，试用海斯算法求s到t的最短道路例如例如(6.2-2)例如例如(6.2-3)例如例如(6.2-4)n由于D(3)=D(2)，停顿计算ns到t 的最短道路长度为16n由D(2)知s到t 经过cn由D(1)知s到c经过a，c到t经过dn那么最短道路为s a c d tsabcdt5839149543福德福德(Ford)(Ford)算法算法(1)(1)n该算法和Dijkstra算法一样有两个根据n从v1 到vn 的最短道路也是从vn 到v1 的最短道路n对于无向图必定成立n对于有向图而言，vn 到
19、v1 的最短道路是指将图中弧的方向反过来，但权值不变时的最短道路n以vn 为起点，v1 为终点运用动态规划的最优性原理n第一条根据保证了按这种方法求得的结果是从v1 到vn 的最短道路福德福德(Ford)(Ford)算法算法(2)(2)n算法步骤n知网络的间隔矩阵L=(lij)，lij表示vi到vj的弧上的间隔权值n令dj(1)= l1j，j=1nndj(t)表示从v1到vj的步数不超越t的最短间隔n当dj(k)知时，令dj(k+1)=mindi(k)+lij| i=1nn当对一切的j有dj(k+1)=dj(k)时，dj(k)是v1到vj的最短间隔。否那么，假设kn-1，k=k+1，转上一步；
20、假设kn-1，阐明存在负初等回路，最短道路不存在，算法停顿福德福德(Ford)(Ford)算法算法(3)(3)n该算法可以判别能否存在负初等回路，适用于恣意权值的赋权连通有向图或无向图n所得的结果中包含了从v1到其他恣意点的最短间隔例如例如(6.3-1)sabcdt5839149543n道路图如下所示，箭头表示通行方向，线上数字表示道路长度，试用Ford 算法求s 到t的最短道路例如例如(6.3-2)abcdd例如例如(6.3-3)n由于dj(4)=dj(3) (j=s,a,b,c,d,t)，停顿计算ns到t 的最短道路长度为16n最短道路为s a c d tsabcdt5839149543最
21、小生成树问题最小生成树问题n普通针对赋权连通图，求该图权值之和为最小的生成树n求解该问题普通有两种方法n破圈法n生长法破圈法求最小生成树破圈法求最小生成树n假设原图为赋权连通图n破圈法根据树的定义给出求最小生成树算法n破圈法步骤如下n在图中找到一个圈，进入下一步；假设无圈那么停顿，此时的图就是原图的最小生成树n查看该圈与其它圈能否有公共边n假设没有公共边，在该圈中选权值最大的边，去掉该边；对新的图前往上一步n假设有公共边，将这些有公共边的假设干个圈合在一同看作一个回路，在该回路中选权值最大的边，去掉该边；对新的图前往上一步例如例如(6.4-1)3354726432n用破圈法求以下图的最小生成树
22、生长法求最小生成树生长法求最小生成树(1)n生长法根据n根据动态规划最优性原理，划分n-1个阶段nx1=S1n从图中任选一点vi，令S1=vi，S2=V-S1，k=1nuk 为k 阶段选中的权值最小的边(vi, vj)，viS1，vjS2nxk+1=xk+uk+vjnS1=S1 +(vi, vj)+vj，S2=S2-vjnxn 形状终了n此时，S1 就是要求的最小生成树的点边集合，S2 是空集生长法求最小生成树生长法求最小生成树(2)n假设原图为赋权连通图n生长法步骤如下n从图中任选一点vi，令S1=vi，S2=V-S1n从S1中的各点到S2中各点的边中选择权值最小的边(vi, vj)，viS
23、1，vjS2n令S1=S1+(vi, vj)+vj，S2=S2-vjn假设S2 是空集，那么停顿，S1 就是要求的最小生成树的点边集合；否那么转第二步例如例如(6.5-1)3354726432n用生长法求以下图的最小生成树作业作业(17)n书上218页5-1的(b)n补充：3和8之间权值为13n破圈法或生长法皆可最大流问题最大流问题(1)n普通针对赋权连通有向图，每条弧的权值表示该弧允许流过的最大流量，每个顶点的流入量之和等于流出量之和，求图上两定点之间允许流过的最大流量n最大流-最小割定理n最大流量等于最小割集(容量最小的割集)的容量n注：将图G中顶点集合V分为两个集合S1和S2，其中起点v
24、sS1、终点vtS2，且S1S2 =V、 S1S2 = ，那么把集合C =(vi, vj) | viS1, vjS2 称为图G的一个割集割集中弧的权值之和称为该割集的容量最大流问题最大流问题(2)n利用最大流-最小割定理，福德和富克逊提出了求解最大流问题的标号法可行流可行流最大流最大流终了终了改动流量改动流量是否最大流问题最大流问题(3)n标号法相关概念n假设弧(vi , vj )上的流量xij=bij，那么称该弧为饱和弧，否那么称为非饱和弧n假设弧(vi , vj )上的流量xij=0，那么称该弧为零流弧，否那么称为非零流弧n在一条从vs 到vt 的点边交错序列中，与vs 到vt 方向一致的
25、弧称为正向弧，与vs 到vt方向相反的弧称为逆向弧n假设从vs 到vt 的某个点边交错序列中，正向弧均为非饱和弧，逆向弧均为非零流弧，那么称该点边交错序列为一条流量增广链最大流问题最大流问题(4)n流量增广链的作用n它是用来添加正向总流量的n使增广链上正向弧的流量增大n使增广链上逆向弧的流量减小n假设找不到，表示不能再增大正向总流量，即当前的正向总流量就是最大流量最大流问题最大流问题(5)n标号法步骤如下n分配vi 到vj 的初始流xijn寻觅增广链，假设不存在，那么曾经最优；否那么进入下一步伐整。寻觅增广链方法如下n将vs 标志上(-, )，S1=vs，S2=V-S1n假设存在以S1中点为起
26、点、以S2中点为终点的非饱和弧(vi , vj )，那么为vj 标志上(vi+, zj )，zj=minzi , bij-xij，S1=S1+vj，S2=S2-vjn假设存在以S2中点为起点、以S1中点为终点的非零流弧(vj , vi )，那么为vj 标志上(vi-, zj )，zj=minzi , xji，S1=S1+vj，S2=S2-vjn假设S1中已包含vt ，那么已找到一条增广链，否那么转向第二步最大流问题最大流问题(6)u调整流量，方法如下u设vt 上的标志为(vk+, zt )，那么整个增广链上最大的调整量为z=ztu由vt 上的标志可以得到增广链上的前一个顶点vk ，依次向前可以
27、找到整个增广链u在增广链上，正向弧流量添加z，逆向弧流量减少zu前往第二步继续寻觅下一个增广链例如例如(6.6-1)(9)(8)(3)(7)(4)(4)(2)(6)(11)711106915543vsvtv2v3v4v5(-, )(vs+, 7)(v2-, 3)(v3+, 1)(v3+, 3)(v5+, 3)n用标号法求出从vs 到vt 的最大流例如例如(6.6-2)n调整流量，得711106915543vsvtv2v3v4v5(11)(0)(9)(7)(4)(4)(5)(9)(11)(-, )(vs+, 4)n找不到增广链，那么当前流量20为最优最小费用最小费用-最大流问题最大流问题(1)n
28、普通情况下，最大流量是独一的，而相应的每条弧上的流量分布却是不独一的n假设知流过弧(vi , vj )的单位流量要发生cij 的费用，要求使得总费用为最小的最大流流量分配方案，这种问题称为最小费用-最大流问题n可以运用对偶法处理这个问题最小费用最小费用-最大流问题最大流问题(2)n对偶法原理n对原图求出从vs 到vt 的一切初等路n将这些初等路按照单位流量费用之和从小到大排序，编号1, 2, 3, , mn使第1号初等路上的流量为最大n在余下的允许流量中，使第2号初等路上的流量为最大n在余下的允许流量中，使第3号初等路上的流量为最大nn在余下的允许流量中，使第m号初等路上的流量为最大n此时，图
29、中的流量分布即为最小费用-最大流n在实践运用时，要对原图求出从vs 到vt 的一切初等路有一定的难度，容易脱漏最小费用最小费用-最大流问题最大流问题(3)n因此，对偶法在实践操作时n求出最大流量，以0流为初始可行流n对原图求出从vs 到vt 的单位流量费用之和为最小的初等路n调整使得该初等路上的流量为最大，假设当前可行流的流量等于最大流量，那么当前可行流就是最小费用-最大流，否那么进入下一步n对当前可行流生成扩展费用图。在扩展费用图中，从原图的允许流量中去掉当前可行流的流量，将图中某些弧的单位流量费用调整为 (这些弧的允许流量曾经减小为0，使得此弧不通)n在该扩展费用图中，求出新的从vs 到v
30、t 的单位流量费用之和为最小的初等路，转向第三步最小费用最小费用-最大流问题最大流问题(4)n对偶法步骤n用标号法求出最大流量n将原图作为初始扩展费用图，以0流作为初始可行流n在扩展费用图上，用Ford 算法求出从vs 到vt 的单位流量费用之和为最小的初等路作为增广链n按前面标号法中调整流量的方法调整流量，得到一个新的可行流n假设当前可行流的流量等于最大流量，那么当前可行流就是最小费用-最大流，否那么进入下一步n对当前可行流生成新的扩展费用图，转向第三步最小费用最小费用-最大流问题最大流问题(5)n扩展费用图的生成n在弧(vi , vj )上n假设xij =0，那么原弧不变n假设0xij b
31、ij ，那么把弧(vi , vj )改呵斥如下的两条弧假设xij =bij ，那么把弧(vi , vj )改呵斥方向相反的另一条弧vivj(bij-xij , cij )(xij , -cij )vivj(bij , cij )在生成增广链时用不到反向弧(vj , vi ) ，这样就去掉了当前可行流的流量同理，使得弧(vi , vj )不通，将其单位流量费用调整为例如例如(6.7-1)n求出从vs 到vt 的最小费用-最大流，图中弧上数字含义为(bij , cij )vsvtv2v4v3v5(15, 2)(9, 6)(3, 3)(5, 5)(4, 9)(7, 8)(6, 3)(10, 1)(1
32、1, 3)例如例如(6.7-2)n由例如(6.6)，如以下图，知从vs 到vt 的最大流量为20vsvtv2v4v3v5(15, 2)(9, 6)(3,3)(5, 5)(4, 9)(7, 8)(6, 3)(10, 1)(11, 3)例如例如(6.7-3)n初始扩展费用图如下所示vsvtv2v4v3v5(15, 2)(9, 6)(3, 3)(5, 5)(4, 9)(7, 8)(6, 3)(10, 1)(11, 3)n求出了增广链例如例如(6.7-4)n初始流量为0，在增广链上调整流量，得vsvtv2v4v3v5(15,2,0)(9,6,6)(3,3,0)(5,5,0)(4,9,0)(7,8,0)
33、(6,3,6)(10,1,6)(11,3,0)n当前可行流流量为620，需求继续调整例如例如(6.7-5)n对当前可行流生成新的扩展费用图为vsvtv2v4v3v5(15, 2)(3, 6)(3, 3)(5, 5)(4, 9)(7, 8)(6,3)(4, 1)(11, 3)(6, -6)(6, -1)n求出了增广链例如例如(6.7-6)n当前流量为6，在增广链上调整流量，得n当前可行流流量为1020，需求继续调整vsvtv2v4v3v5(15,2,4)(9,6,6)(3,3,0)(5,5,0)(4,9,4)(7,8,0)(6,3,6)(10,1,10)(11,3,0)例如例如(6.7-7)n对
34、当前可行流生成新的扩展费用图为n求出了增广链vsvtv2v4v3v5(11, 2)(3, 6)(3, 3)(5, 5)(4, 9)(7, 8)(6,3)(10, 1)(11, 3)(6, -6)(4, -2)例如例如(6.7-8)n当前流量为10，在增广链上调整流量，得n当前可行流流量为1720，需求继续调整vsvtv2v4v3v5(15,2,11)(9,6,6)(3,3,0)(5,5,0)(4,9,4)(7,8,7)(6,3,6)(10,1,10)(11,3,7)例如例如(6.7-9)n对当前可行流生成新的扩展费用图为n求出了增广链vsvtv2v4v3v5(4, 2)(3, 6)(3, 3)(5, 5)(4, 9)(7, 8)(6,3)(10, 1)(4, 3)(6, -6)(11, -2)(7, -3)例如例如(6.7-10)n当前流量为17，在增广链上调整流量，得n当前可行流流量为20，等于最大流量，不需求调整，当前可行流就是最小费用-最大流vsvtv2v4v3v5(15,2,11)(9,6,9)(3,3,0)(5,5,3)(4,9,4)(7,8,7)(6,3,6)(10,1,10)(11,3,10)作业作业(18)n书上220页的5-5n是一个最小费用-最大流问题
