北京交通大学 高级运筹学-网络问题.PPT

3、增广链对可行流f={fij}：非饱和弧：fijCij饱和弧：fij=Cij非零流弧：fij0零流弧：fij=0链的方向：若μ是联结vs和vt的一条链，定义链的方向是从vs到vt。前向弧：与链的方向一致的弧，前向弧全体记为μ+。后向弧：与链的方向相反的弧，后向弧全体记为μ-。v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2μ=(v1,v2,v3,v4,v5,v6)μ+={(v1,v2),(v2,v3),(v3,v4),(v5,v6)}μ-={(v5,v4)}后向弧v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2定义3设f是一个可行流,μ是从vs到vt的一条链,若μ满足下列条件,称之为(关于可行流f的)一条增广链。(vi,vj)∈μ-0fij≤CijCij.fijV3V1V2V4V58.45.03.35.4(vi,vj)∈μ+0≤fijCij前向弧是非饱和弧，后向弧是非零流弧，4、截集与截量设S，T?V，S?T=?，始点在S，终点在T中的所有弧的集合，记为（S，T）。ST网络D=（V，A，C），若点集V被剖分为两个非空集合V1和V1，使vs∈V1，vt∈V1，则把弧集（V1，V1）称为是分离vs和vt的截集。v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2=(v1,v2,v3)V11=(v4,v5,v6)v2v53.34.18.3v3v1v4v65.110.511.66.317.23.25.2=(v1,v2,v3)V11=(v4,v5,v6)截集为红色弧集定义5给一截集（V1，V1），把截集（V1，V1）中所有弧的容量之和称为这个截集的容量（简称为截量），记为C（V1，V1），即不难证明，任何一个可行流的流量V(f)都不会超过任一截集的容量。即可行流f*，截集(V1*，V1*),若V(f*)=C(V1*，V1*），则f*必是最大流，(V1*，V1*)必是D的最小截集。定理1可行流f*是最大流，当且仅当不存在关于f*的增广链。证明：若f*是最大流，设D中存在关于f*的增广链μ，令?=min由增广链的定义，可知?0,令??不难验证，是一个可行流，且这与f*是最大流的假设矛盾。?设D中不存在关于f*的增广链，证明f*是最大流。若vi∈V1*,且(vi，vj)上，fij*Cij,则令vj∈V1*，因为不存在关于f*的增广链，故vt∈V1*，记V1*=V\V1*，得截集（V1*，V1*），显然有V1*vsvivjfij*Cijvjvifji*0定义V1*:令vs∈V1*，若vi∈V1*，且(vj，vi)上，fji*0，则令vj∈V1*。所以V(f*)=C（V1*，V1*）。于是f*必是最大流定理2最大流最小截定理。任一个网络D中，从vs到vt的最大流的流量等于分离vs，vt的最小截集的容量。二、寻求最大流的标号法（Ford—Fulkerson）从任一个可行流f出发（若网络中没有给定f，则从零流开始），经过标号过程与调整过程。（一）标号过程开始，vs标上（0，∞），vs是标号未检查的点，其余点都是未标号点，（1）若弧（vi，vj）上，fjiCij，则给vj标号(i，l(vj))，l(vj)=min[l(vi),Cij-fij],vj成为标号而未检查的点。（2）若弧（vj，vi）上，fji0，则给vj标号(-i，l(vj))，l(vj)=min[l(vi),fji],vj成为标号而未检查的点。标号：（前点，前点到该点的这条弧流量可调整量)一般地，取标号未检查点vi，对一切未标号的点vj。vjfjiCijvi(i，l(vj))，vjvifji0(-i，l(vj))（二）调整过程从vt开始，反向