第十章图与网络优化一、基本概念与定理网络D中的任一条弧(vi,vj)的流量记为f(vi,vj)，(简记fij)，显然，fij≤Cij；一系列流量的集合f={f(vi,vj)}构成网络D上的流（运输方案）。例连接某产品产地v1和销地v6的交通网如下：2、可行流与最大流如(b)图是网络上的一个可行流（运输方案）3、增广链µ=(v1,v2,v3,v4,v5,v6)定义3设f是一个可行流,µ是从vs到vt的一条链,若µ满足下列条件,称之为(关于可行流f的)一条增广链。4、截集与截量v2定义5给定截集（V1，V1），把截集（V1，V1）中所有弧的容量之和称为这个截集的容量（简称为截量），记为C（V1，V1），即不难证明，任何一个可行流的流量V(f)都不会超过任一截集的容量。即1、从一个可行流f开始，寻找关于f的增广链；2、如果不存在关于f的增广链，可行流f就是最大流f*；3、如果存在关于f的增广链，则以适当的调整量对可行流f进行调整，得到一个流量更大的可行流，不断重复调整过程，直到不再存在增广链时，就得到了最大流。二、寻求最大流的标号法标号过程首先给vs标号（0，+∞），此时vs是未检查的标号点，其余各点都是未标号点。取一个未检查的标号点vi进行检查，给与vi相邻的所有未标号点vj标号：（1）如果在前向弧（vi，vj）上，有fij<cij，则给vj标号（vi，l(vj)）。其中l(vj)=min{l(vi)，cij-fij}，此时新标号点vj成为未检查的标号点。（2）如果在后向弧（vj，vi）上，有fji>0，则给vj标号（-vi，l(vj)）。其中l(vj)=min{l(vi)，fji}，此时新标号点vj成为未检查的标号点。至此，点vi成为已检查过的标号点。重复标号过程，一旦vt被标号，即得到一条从vs到vt的增广链µ，转入调整过程。（二）调整过程。找出增广链µ，并沿增广链µ调整流量。去掉所有的标号，对新的可行流f'={f'ij}，重新进行标号。重复标号过程和调整过程，直到标号过程进行不下去且vt未获得标号为止，说明当前可行流不存在增广链，即得到了最大的可行流。例用标号法求下图网络的最大流。弧旁的数字是（Cij,fij)。继续检查vs，在vs的前向弧（vs，v2）上，fs2=Cs2=3,不满足标号条件。此时，未检查的标号点为v1v2v2（二）调整过程:去掉各点标号，从vs开始，重新标号。第五节最小费用最大流问题为增广链µ的费用。求最小费用最大流的原理：构造赋权有向图W(f)方法如下：它的顶点就是网络D的顶点,W(f)中弧及其权wij按弧（vi，vj）在D中的情形分为：赋权有向图W（f）的权是单位流量的费用，故W（f）成为流f的费用网络图。vs（3）在原网络D中，与这条最短路对应的增广链为:按照上述算法依次得f1，f2，f3，f4，流量依次为V(f1)=5，V(f2)=7，V(f3)=10，V(f4)=11，构造相应的增量网络为W(f1)，W(f2)，W(f3)，W(f4),如图(a),(e),(g),(i)所示。v2v2v2图（i）中，不存在从vs到vt的最短路，所以f4为最小费用最大流。