1、第8章 分枝一限界法 本章的内容是回溯法讨论的问题的继续和扩展。使用限界函数的深度优先生成结点方法是回溯法，E结点一直保持到死为止的状态生成方法叫分枝限界法。在这一章里，首先介绍状态空间树上的三种检索方式：FIFO，LIFO，LC检索，再重点介绍用LC-分枝限界法解最优化问题的一般实现，最后得出一个实例0/1背包的解法以及用C语言实现的程序。8.1 状态空间树上的检索FIFO，LIFO，LC检索 8.1.1 FIFO(first in first out)，LIFO(last in first out)检索图8.1 由FIFO分枝限界法生成的一部分4-后状态空间树 8.1.2 LC-检索 在生
2、成一个答案结点之前，子树X需要生成的结点数。在子树X中，X到最近一个答案结点的路径长。例8.1 15谜问题(15-puzzle)。在44的方格棋盘上,将数字1,2,3,15以任意顺序放置在棋盘的各个方格中，空出一格,如图8.2(a)为15谜问题的一种初始棋盘格局。定理8.1 对于一个给定的状态图8.2 15谜问题的一个实例 如果这个和数是偶数,则这个状态可达目标状态,否则,其他任何初态都不可达目标状态。图8.3 15-谜问题的一部分状态空间树 设想1：g(X)是结点X表示的状态中没有到达目标位置的非空白牌的数目。显然，状态X到达目标状态所需要的移动空白牌的次数大于g(X)。比如状态X 设想2：
3、f(x)同设想1，这里j表示空格的位置。它也是一个可行的方法,似乎不及设想1中的g(X)好，因为对图 8.3给定的初态，它需要产生更多的结点，但是如果检索如 8.1.3 LC-检索的抽象化描述 算法8.1 的状态空间树，按设想1,g(1)=1,按设想2,g(1)=14。这里f(X)+14=14显然更接近C(X),C(X)是初态到目标状态的路径长度,即需要移动空白牌的次数。procedure LC(T，C)；begin ET；置活结点表为空；loop if E是答案结点 then begin 输出从E到T的路径；return；end；for E的每个儿子结点X do begin call add
4、(x)；parent(x)E；end；if 不再有活结点 then begin print(No answer node)；stop；end；call least(E)；repeat；endp；8.2 分枝限界法解最优化问题 例8.2 带限期的作业排序问题。假定有n个作业Wi，i=1，n和一台处理机，每个作业Wi与一个三元组(pi，di，ti)对应，其中ti是完成作业Wi需要的时间，di是完成作业Wi需要的期限，如果不在这个期限di之内完成Wi则将受到pi的罚款。问题的目标是从n个作业中选取一个子集J，要求J中的作业都能在相应的限期内完成，且使不在J中的作业受到的罚款总额最小,这样的J就是最优
5、解。图8.4 大小可变的元组表示对应的状态空间树 X中最小成本答案结点的上界函数u(X)定义为：图8.5 大小固定的元组表示对应的状态空间树 以图8.4元组大小不固定的状态空间树为例说明作业排序的LC-分枝限界算法。开始时置最小成本答案结点的成本上界U=,或 由于图8.4中每个圆形结点都是答案结点，按U的定义：算法8.2 procedure LCBB(T，c，u，cost)/为了找出最小成本结点,检索状态空间树T,假定T至少包含一个解结点,且C(X)C(X)u(X)/begin ET；parent(E)0；if T是解结点 then begin Umin(cost(T)，u(T)+)；ansT
6、；end else begin Uu(T)+；ans0；end；将活结点表初始化为空；loop for E的每个儿子 do if C(X)U then begin call ADD(X)；parent(X)E；case X是解结点and cost(X)U：begin Umin(cost(X)，u(X)+)；ansX；end；u(X)+U Uu(X)+：endcase；end；if 不再有活结点 or 下一个E-结点有CU then begin print(least cost=，U)；while ans0 do begin print(ans)；ansparent(ans)；end；retur
7、n；end；call least(E)；repeat；endp；对算法LCBB还需强调以下几点：当下一个E-结点使CU时，算法终止；子算法ADD是加入一个结点到活结点表中，LEAST是从一个活结点表中删去一个结点，活结点表作成一个min堆；如果U是已找到的一个解X的成本值，U=c(X)u(X)，对于X的儿子Y，不仅c(Y)U，而且c(Y)=U的结点Y都要被杀死；如果U是一个单纯的上界，它是由一可行结点X的u值修改而得，U=u(X)+。对于X的儿子只杀死c(Y)U的Y，c(Y)=U的Y不被杀死，Y入堆；虽然找到了一个答案结点X,但它的成本值大于它的上界值u(X),这说明,这个答案结点的子孙中还有
8、成本更小的答案结点,U取u(X)+,对于X的儿子结点Y,只杀死c(Y)U的Y，c(Y)=U的Y不被杀死,Y入堆。8.3 0/1背包问题的LC-分枝限界求解的 实现 例8.3 0/1背包问题。问题可描述如下：极小化：规范函数 xi=0 或 xi=1,1in 成本函数 为了使最小成本答案结点与最优解对应，成本函数定义如下：如果X是答案结点，如果X是不可行的叶子结点，C(X)=；如果X是非叶子结点,C(X)=minC(LCHI LD(X),C(RCHILD(X)。算法8.3 procedure UBOUND(P，W，k，M)；/P：当前效益总量;W:当前背包质量;k:上次处理的物品的下标号;M:背包
9、容量;W(i)：第i种物品的质量;P(i):第i种物品的效益值,并且P(i)/W(i)P(i+1)/W(i+1),1in/begin bP；cW；for ik+1 to n do if c+W(i)M then begin cc+W(i)；bb-P(i)；end；return(b)；endp；算法8.4 算法中涉及的说明同算法8.3.procedure BOUND(P，W，k，M)；begin bP；cW；for ik+1 to n do begin cc+W(i)；if cM then bb-P(i)else return(b-(1-(c-M)/W(i)*P(i)；end；return(b)
10、；endp；图8.6 0/1背包问题的一个实例的分枝限界检索 解决以下问题：被检查的状态空间树中结点的结构；如何生成一个儿子结点；如何识别答案结点；活结点表的表示以及其上的操作。算法8.5 1)计算上、下界 Procedure LUBOUND(P,W,rw,cp,N,k,LBB,UBB),/rw：背包的剩余容量,cp：已获得的效益,还有k，N个物品作选择,LBB=-u(X),UBB=-C(X)/begin LBBcp；crw；for ik to N do begin if cW(i)then begin UBBLBB+c*P(i)/W(i)；for ji+1 to N do if cW(j)t
11、hen begin cc-W(j)；LBBLBB+P(j)；end；return；end；cc-W(i)；LBBLBB+P(i)；end；UBBLBB；endp；2)生成一个新结点 Procedure NEWNODE(par，lev，t，cap，prof，ub)/生成一个新结点i，将它加入活结点表中/begin call GETNODE(i)；ARENT(i)par;LEVEL(i)lev;TAG(i)=t；CU(i)cap；PE(i)prof；UB(i)ub；call ADD(i)；endp；3)输出解 procedure FINISH(L，ANS，N)begin for jN to 1 s
12、tep-1 do begin if TAG(ANS)=1 then printf(j)；ANSPARENT(ANS)；end；endp；算法8.6 procedure LCKNAP(P，W，M，N，)1 begin 2 call INIT；/初始可用结点表以及活结点表/3 call GETNODE(E)；/生成根结点/4 PARENT(E)0;LEVEL(E)1;CU(E)M；PE(E)0；5 call LUBOUND(P，W，M，N，0，1，LBB，UBB)；6 LLBB-；UB(E)UBB；7 repeat 8 iLEVEL(E)；capCU(E)；prof PE(E)；9 case 10
13、 i=N+1/解结点/11 if profL then 12 begin 13 Lprof；14 ANSE；15 end；16 iN+1/E有的两个儿子/17 begin 18 if capW(i)then/生成左儿子/19 ca ll NEWNODE(E，i+1，1，cap-W(i)，prof+p(i)，UB(E)；/看右儿子是否会成为活结点/20 call LUBOUND(P，W，cap，prof，N，i+1，LBB，UBB)；21 if UBBL then /右儿子会活/22 begin 23 call NEWNODE(E，i+1，0，cap，prof，UBB)；24 Lmax(L，LB
14、B-)；25 end；26 endcase；27 if 不再有活结点 then exit；28 call LARGEST(E)；29 until UB(E)L；30 call FINISH(L，ANS，N)；31 endp；下面是该算法用C语言实现的程序清单。/*this is the fixed number*/#define n 8#define lit 0.000 1#define m 110.0#define nn 20#define len sizeof(struct point)/*this is the data structure*/struct point int paren
15、t；int level；int tag；float cu；float pe；float ub；struct list struct point *dot；struct list bagnn；struct point*e；float apn，awn；float l，lbb，ubb；int pc，lpc，ans；int llnn；/*the more number*/float max(a，b)float a，b；float more；if(ab)more=a；else more=b；return(more)；main()float cap，prof，x，y；Int i，j，k，la，jobok；
16、void lubound()；void newnode()；void add()；void finish()；int largest()；printf(*this is a programme about 0/1 bag problem*n)；printf(input p and w!n)；for(i=0；i=n-1；i+)scanf(%f，&x)；scanf(%f，&y)；j=0；while(j=i-1)&(x/y)(apj/awj)j=j+1；for(k=i；k=j+1；k-)apk=apk-1；awk=apk-1；apj=x；awj=y；jobok=0；pc=0；lpc=0；e=(str
17、uct point*)malloc(len)；e-parent=-1；e-level=1;e-cu=m；e-pe=0.0；e-tag=-1；la=0；lubound(m，0.0，0)；l=lbb-lit；e-ub=ubb；bagpc.dot=e；ans=0；do i=e-level;cap=e-cu；prof=e-pe；if(i=n+1)printf(*the best result is：*n)；if(profl)l=prof；ans=la；else if(cap=awi-1)newnode(la，i+1，1，cap-awi-1，rof+api-1，e-ub)；lubound(cap，pro
18、f，i)；if(ubbl)newnode(la,i+1,0,cap,prof,ubb)；l=max(l，lbb-lit)；if(lpc=0)printf(the num of livelist is%dn，lpc)；jobok=1；break；if(!jobok)la=largest()；e=bagla.dot；while(e-ub)l)；finish(ans，l)；printf(*my programme have finished*n)；/*the bound of the point*/void lubound(rw，cp，k)float rw，cp；Int k；int i，j；floa
19、t c；lbb=cp；c=rw；for(i=k；i=n-1；i+)if(cawi)ubb=lbb+c*api/awi；for(j=i+1；j=n-1；j+)if(c=awj)c=c-awj；lbb=lbb+apj；goto exit；c=c-awi；lbb=lbb+api；ubb=lbb；exit；/*add to livelist */void add(y)Int y；int j，addok；lpc=lpc+1；addok=0；j=lpc；while(!addok)&(j1)if(bagy.dot-ub)=(bagll j/2.dot-ub)llj=llj/2；j=j/2；else addo
20、k=1；llj=y；/*delete the largest number from the livelist and form the max-stock again*/int largest()int lar，i，j，t，delok；lar=ll1；ll1=lllpc；lpc=lpc-1；i=1；j=2*i；t=ll1；delok=0；while(j=lpc)&(!delok)if(jlpc)&(bagllj.dot-ub)(bagllj+1.dot-ub)j=j+1;if(bagt.dot-ub)=(bagllj.dot-ub)delok=1；else lli=llj；i=j；j=2*i
21、；lli=t；return(lar)；/*NEWNODE form a new point*/void newnode(par，lev，t，cap，prof，vub)int par，lev，t；float cap，prof，vub；pc=pc+1；e=(struct point*)malloc(len)；e-parent=par；e-level=lev；e-tag=t；e-cu=cap；e-pe=prof；e-ub=vub;bagpc.dot=e；add(pc)；/*print the result */void finish(ans，l)Int ans；float l；printf(VALU
22、E OF OPTIMAL FILLING IS：%fn,l)；printf(OBJECTS IN KNAPSACK ARE:)；while(ans0)if(bagans.dot-tag=1)rintf(%d-，bagans.dot-level-1)；ans=bagans.dot-parent；printf(endn)；第9章 内存分类法 分类也叫排序。根据待分类的记录的数量的多少，可将分类分为两类：一类是内存分类，这种分类是指待分类的记录的关键字的数量不是很多，可一次调入计算机的内存进行分类；另一类是外存分类，这种分类指的是待分类的数据的数量很大，内存一次不能容纳全部数据，在分类过程中，需要进
23、行内外存的交换进行分类的过程。本章介绍的是第一种,但只介绍内存分类法中两个问题:求第K个元素(也叫顺序统计);另一个是堆排序。9.1 求第K个元素图9.1 锦标赛过程示意图 算法9.1 找出序列S=x1，x2，xn的第K小元素。输入：有n个元素的序列S以及整数K，1 Kn；输出：S的第K小元素。pocedure Kthmin(S，K)；begin if S64 then begin sort S;/任一种分类法,对S直接分类/return S的第K小元素；end else begin 将S分成 个子序列，每个子序列有15个元素。如果有剩余元素放入子序列L，对它们分别进行分类；设C是15个元素子
24、序列的中值组成的序列；mKthmin(C，c/2 )；/求m的序数/if m的序数=K then return m else if m的序数K then Kthmin(S-A，k1=K-A)else Kthmin(S-B，k)；end；endp；对算法9.1的了解可参考图9.2，不妨设n刚好是15的倍数。设T(n)是从S(S=n)中选出第K小元素所需时间，则图9.2 算法9.1的示意图 解这个递归式 T(n)=O(n)。算法9.2 寻找序列S的第K小元素。Procedure quickmin(S，K)；begin if S=1 then return S中的单个元素 else else beg
25、in 从S中随机地选出一个元素a；用快速分类法求出S1，S2，S3；/S1：小于a的元素序列；S2：等于a的元素序列；S3：大于a的元素序列；/if S1K then return quickmin(S1，K)else if S1+S2K then return a else return quickmin(S3,K-S1-S2);end；endp；假设T(n)是对长度为n的序列S求第K小元的平均时间耗费。S中的n个元素xi是互不相同的。在利用快速分类时，作为“枢轴”的元素a是S的第i个最小元，其中i=1，2，n是等概率的。如果iK，则在S1上调用quickmin的时间耗费为：O(n)+T(i
26、-1)；如果iK，则在S3上调用quickmin的时间耗费为：O(n)+T(n-i)；如果i=K，时间耗费为：O(n).当i遍取1，2，n时，可选T(1)c，用归纳法证明：对于所有n2，有T(n)4cn。对于n=2，有 T(1)=3c4c2；假定有T(n)4cn，对所有的n，2nm成立；对于n=m 由于T(n)是n的非降函数,因此当 时,取极大值，所以 所以T(n)4cn成立，即T(n)=O(n)。9.2 堆 分 类 在数据结构中已作介绍,当待分类的元素没有明显的结构特征时,只能施行“比较”操作,以此确定两个元素的顺序。这种“比较”分类,理论上已证明至少需要作log2n!次比较,而log2n!
27、nlog2n-1.44n+log2 +1.325，此作为比较分类的时间复杂性的理论下界。设A=a1，a2，an是待分类的序列，T是一棵二叉树，T中每个结点都对应着A中的一个元素。T是一个极大/极小堆，当且仅当满足以下条件：T是一棵完全二叉树；aia2i且aia2i+1 或 aia2i且aia2i+1 (i=1，2，n/2).利用堆可以将待分类的序列A分类，其基本步骤是：将A建成堆；A1An；置nn-1，即在T中把极大结点输出，得到一棵非堆的二叉树；恢复堆。在当前T中，将根结点(或子树的根结点)与它的两个儿子结点中较大的结点交换,直到每个结点都大于它的子孙为止；重复、，直到n=1，将输出分类后的
28、结果。这种分类方法叫堆分类。1)建立初始堆 算法9.3 procedure HEAPFIFY(i，j)；/将数组元素AiAj建成堆/begin while (2i+1j)(AiA2i)(AiA2i+1)do /i不是一片叶子且若i的儿子含有比i大的元素/begin if(A2iA2i+1)then begin Ai A2i；HEAPFIFY(2i，j)；end else begin AiA2i+1；HEAPFIFY(2i+1，j)；end；if(2i=j)(AiA2i)then Ai A2i；end；endp；算法9.4 Procedure BUILDHEAP；begin for i n/2s
29、tep-1 until 1 do call HEAPFIFY(i，n)；endp；2)分类 算法9.5 Heapsort：输入：待分类的数组Ai，1in；输出：已分类的数组A。procedure Heapsort；begin call BUILDHEAP；mn；while m1 do begin AiAm；mm-1；call HEAPFIFY(1，m)；end；endp；对于深度为K的堆,HEAPFIFY进行关键字比较的次数至多为2(k-1)次,则在建含有n个元素，深度为h的堆时,由于第i层上的结点数至多为2i-1,以它为根的完全二叉树的深度为h-i+1。则调用n/2次HEAPFIFY总共进行
30、的关键字比较次数不超过下式之值：对于堆分类,每次调用HEAPFIFY算法的比较次数最多是深度的2倍,即2 log2m,2 mn-1，所以总的比较次数是：图9.3 初始堆示例 算法9.6 procedure UPANDUP(i，j)；begin if i不是叶子 then begin 令k是i的带有较大元素的儿子；AiAk；call UPDANDUP(k，j)；end else begin Ai Aj+1；/将最后一片叶子放在完全二叉树中当前所缺的叶子结点上。如果所缺的叶子刚好是完全二叉树上的最后一片叶子，则将最后一片叶子自己赋给自己/while AiA i/2 do begin Ai A i/
31、2；i i/2；end；end；endp；算法9.7 procedure Heapsort1；begin call BUILDHEAP；for jn step-1 until 2 do begin BA1；call UPANDUP(1，j-1)；AjB；end；endp；下面对Heapsort1进行时间复杂性分析：初始堆之后，为了输出分类序列，用了15次比较图9.4 Heapsort的实现过程初始堆之后，为了输出分类序列，用了9次比较图9.5 Heapsort1的实现过程 算法9.8 procedure UPORDOWN(i，j)；begin if id then begin 令k是i的较大儿
32、子；AiAk；call UPORDOWN(k，j)；end else begin AiAj+1；if AiA i/2 then call HEAPFIFY(i，j)else while AiA i/2 do begin AiA i/2；i i/2；end；end；endp；算法9.9 procedure Heapsort2；begin call BUILDHEAP；for jn step-1 until 2 do begin d2 ；BA1;UPOR DOWN(1，j-1)；AjB；end；endp；同上对Heapsort1的分析，算法9.9的时间耗费包括两部分：调用BUILDHEAP，初始化
33、堆，其耗费是O(n)。for循环的耗费。第10章 图的算法 图是应用极为广泛的数学工具。许多工程和科学技术中的问题可以抽象为图，将图作为其数学模型。图的研究分为两类：一是图论，研究图的一些代数性质；二是图的应用，主要研究图的最优化问题。本章介绍这两方面的一些基本算法。10.1 图的两种遍历DFS，BFS 图本身是一种无序结构。在解决图的问题时,几乎所有算法都需要处理图的顶点或边,为了尽可能少地对顶点和边作重复检查,需要人为地规定图的检索顺序。在数据结构中已介绍过图的遍历的两种方式DFS（Depth First Search）遍历和BFS（Breadth First Search)遍历两种方式,
34、这两种方式实际上都是对图这种无序结构作线性化处理。算法10.1 dfs的递归算法。Procedure dfsrecursive（G，v）。begin 访问v；标记v；while有一个邻接于v的未标记的顶点w do dfsrecursive（G，w）；endp；算法10.2 dfs的非递归算法。Procedure dfs（G，v）；/S是一个栈，初始为空，在任何时候，栈顶元用top表示/begin 访问v；标记v；push（S，v）；while S非空 do begin while top有邻接点w且w未标记 do begin 访问w；标记w；push（S，w）;end；pop（S）；end；e
35、ndp；算法10.3 Procedure bfs（G，v）；/Q是一个队列，初始为空/begin 访问v；标记v；enqueque（Q，v）；while Q非空do begin xdelqueque（Q）；for 每个邻接于x而未标记的顶点w do begin 访问w；标记w；enqueque（Q，w）；end；end；endp；上述算法仅访问了以v为始点，以及v的可达顶点，如果要访问G中每个顶点，则 算法10.4 图的遍历。Procedure travel（G）；begin for v1 to n do v标记0；for v1 to n do if v未标记 then dfs/bfs（G，v
36、）；endp；10.2 DFS 树 在一个图（有向图或无向图）上作DFS时，引向未标记顶点的边构成一棵有限树称为DFS树，这种边称为树边。如果从始点出发，图中所有顶点不是始点的可达顶点，则对图的遍历生成DFS森林。对于无向图，这种搜索给图的每条边一个定向，按通过边的方向对边定向。如果是有向图，则只能按预先给定边的方向对边进行访问。算法10.5 求图G的DFN数组 Procedure dfsDFN（G，v）；/G的存储用邻接表l/var t：link；begin visit（v）；markv1；DFNvx;xx+1；t1v；（a）有向图G （b）有向图G的DFS森林图10.1 while tni
37、l do begin if markt，v=0 then dfs-DFN（G，t，v）；tt.next；end；endp；Procedure travel（G）；begin for v1 to n do markv0；x1；for v1 to n do if markv=0 then gfs2（v）；endp；顶点的深度优先数与顶点的先辈后代关系的关系如下，以此去识别G的四种类型的边：如果w是v的后代，则：DFN(v)DFN（y）；如果有向边（x，y）是子孙边，则：DFN（x）DFN（y）。如果x,y不满足,则x,y是兄弟关系,或属于不同的连通分支,所以和用来判定横跨边,、则作为判定回边与子孙
38、边。10.3 无向图的双连通分支 定义10.1 设G=(V，E)是一个连通的无向图，顶点aV,如果存在顶点v,wV和a互不相同，并且v和w之间的每一条路径都包含a,则称a是图的一个关节点,也叫图的割点。定义10.3 E上的一个等价关系R定义为：e1Re2 e1=e2或者G中有一个回路既包含e1又包含e2。定义10.4 等价关系R将E分成等价类，E1，E2，Ek，使得两条不同边在同一个类当且仅当它们位于同一个回路上。设Vi是Ei中边的关联顶点集，每个图Gi=（Vi，Ei）是G的一个双连通分支。例10.1 图10.2（a）是一无向图。B，E，F是关节点，G有4个双连通分支，位于公共回路的边的等价类
39、是：（a）图G （b）G的4个双连通分支图10.2 E1=(G,B),(B，I),(I，G)E2=(B,E),(E，C),(C，B)E3=(E,F)E4=(H,E),(E,I),(H,A),(A，F),(F,D),(A,D),(I,D)有几点注意：一条边（例如E3）没有回路，也产生一个双连通分支。R是E上的等价关系,R对E产生一个分划,并不对V产生分划,因此一个顶点可能在几个分支中,比如,B现在G1=（E1,V1）又出现在G2=（E2,V2）中。算法10.6 计算无向图G计算low数组。Procedure dfs-low(G,k)；/假 定 G 用 邻 接 表 l 存储,mark,low,DF
40、N,father数 组 分 别 是 标 记 数组,low数组和DFS数数组,以及顶点的父亲。/图10.3 DFS树T中的一个关节点V var t：link；begin markk1；DFNkx；xx+1;lowkDFNk；t1k；while tnil do begin if markt.k=0 then begin fathert.kk；dfs-low（t.k）；lowkminlowk，lowt.k；/如果顶点k在dfs树中有一个儿子w=t.k,且low（w）DFN（top）do begin tag（x）1；output x；pop（SC）；end；/输出一个强连通分支/end else be
41、gin push（SC，top）；ZS上的第二个顶点（从top起）low(Z)minlow(Z)，low(top)end；pop（S）；/从top返回到Z，即新的top/if S不空 then goto forward；endp；10.5 流 的 算 法 许多系统涉及流量问题，比如车辆运行系统中的车流，控制系统的信息流，金融系统的金融流等，这些研究对象抽象为数学问题时，数学模型是网络中的流。它本身属于运筹学和组合数学讨论的内容，本节内容作为有向图的应用。10.5.1 基本概念（1）网络与流 定义10.5 G=(V,E)是一带权的有向图,在V中指定了一点称为发点(source),vs以表示;指定
42、 了另一点称为收点(sink),以vt表示;其余的点叫中间点。G中边上的权大于或等于0,称为弧的容量,记为C(vi，vj),简记为Cij。所谓网络上的流,是指定义在E上的一个函数f=f(vi，vj),称f(vi,vj)(简记为fij)为弧(vi,vj)上的流量,f称为网络G上的一个流,如图10.8。(a)网络G，边上的数表弧的容量Cij(b)G上的一个流，边上的数表弧的流量fij图10.8 网络上的流(2)可行流与最大流 在网络的实际问题中，对于流有两个明显的要求：一是每个弧上的流量不能超过该弧的容量；二是中间点的流量为零。因为对于每个点，运出这点的产品总量与运入这点的产品总量之差，是这点的净
43、输出量，简称为这一点的流量。由于中间点只起转运作用，所以中间点的流量必为零，而发点的净流出量和收点的净流入量必相等，也是一个系统的方案的总输出量。定义10.6 满足下列条件的流f称为可行流。弧流量限制条件：平衡条件：式中的v（f）称为可行流f的流量。(3)增广链 对于一个给定的可行流，f=fij,称fij=Cij的弧为饱和弧,使fij 0的弧称为非零流弧。若是G中从vs到vt的一条链，定义链的方向是从vs到vt，则链上的弧分为两类：一类是弧的方向与链的方向一致,叫做前向弧。前向弧的全体记为+,另一类弧与链的方向相反,称为后向弧,后向弧的全体记为-。定义10.7 设f是一个可行流，是从vs到vt
44、的一条链，若满足下列条件，称之为关于可行流的一条增广链。+中每一条弧是非饱和弧,即0fijCij，(vi，vj)+;-中每一条弧是非饱和弧,即0fijCij，(vi，vj)-。(4)截集和截量 定义10.8 对于给定网络G=(V，E),把V剖分为两个非空集合Vs和 ,使vsVs,vt ，Vs =,Vs =V，把从Vs指向 的弧的全体,记为(Vs，)=(vi，vj)|viVs,vj ，(vi，vj)E，称作网络G的一个截集。截集(Vs，Vs)中所有弧的容量之和称为该截集的截量，记作c(Vs，)，G的所有截集中，截量最小的为最小截集。显然，任何一个可行流的流量v(f)都不会超过任一截集的容量。即：
45、定理10.1 可行流f是最大流，当且仅当不存在关于 f 的增广链。定理10.2 (最大流最小截量定理)任一网络G中，从vs到vt的最大流的流量等于分离vs，vt的最小截集的容量。10.5.2 寻求最大流的(Ford-Fulkerson)标号法 算法10.10 求最大流。1）给出一个初始可行流 f，(例如f=0)，经过标号与调整过程。2）给顶点标号。3）如果V0非空，则反复按以下、进行，否则转5)。4）在增广链上进行调整，得到新的可行流 f。设vtV0，利用的vt标号和Vs中各点的标号的第一分量，从vt反向追踪到vs，得到一条从vs到vt的增广链，按：5)写出最大流f*=f*ij的流量v(f*)
46、和最小截集(V*s,V*s)，终止计算。例10.3 试用(Ford-Fulkerson)标号法求图10.12所示的网络最大流，弧上的数是 (Cij,fij)。图10.9图10.10 10.5.3 最小费用最大流问题 最大流问题仅仅反映了网络通过物量能力的大小，在实际生活中，涉及“流”的问题时，不仅考虑流量，而且还要考虑费用，本节介绍如何解决这类问题，即求最小费用最大流问题。对于给定的网络G=(V，E，C)，除了已知每条弧(vi，vj)E上的容量Cij外,还知道(vi，vj)上每个单位流量的费用b(vi，vj)0(简记为bij)，最小费用最大流问题就是求一个最大流，使流的总输送费用 取极小值。具体实现是构造一个带权的有向图G，它的顶点是G的顶点，把G中的每一条弧(vi，vj)变成两个相反方向的弧(vi，vj)和(vj，vi)，定义G中弧上的权wij为：算法10.11 求最小费用最大流。图10.11 网络G 例10.4 以图10.11为例，求最小费用最大流，弧上的对偶为(bij，Cij)。图10.12
