图论讲义第9章-网络流理论

第九章网络流理论流什么是流？流就是永恒。当生命停止，呼吸不再，流，并未结束。因为一个生命的终止是另一个生命的开始，因为地球仍在运转，太阳还在发光，时间还在奔流。个体的生命有限，宇宙的生命无穷，流，与时光共存，和无限相伴。流是风，流是雨，流是奔腾的江河，流是起伏的山川。流是婀娜的小草，在微风中摇曳。流是我缥缈的思绪，在缥缈的地方遨游。§9.1网络与网络流的基本概念定义9.1.1一个网络N=(V,A)是指一个连通无环弧且满足下列条件的有向图：(1)有一个顶点子集X，其每个顶点的入度都为0；(2)有一个与X不相交的顶点子集Y，其每个顶点的出度都为0；(3)每条弧都有一个非负的权，称为弧的容量。注：上述网络N可写作N=(V,X,Y,A,C)，X称为网络的发点集或源点集，Y称为网络的收点集或汇点集，C称为网络的容量函数。例：定义9.1.2网络N=(V,X,Y,A,C)中的一个(可行)流是指定义在A上的一个整值函数f，使得：(1)对,0()()aAfaca∀∈≤≤，(容量约束);(2)对(),()()vVXYfvfv−+∀∈−=∪，(流量守恒)。其中()fv−表示点v处入弧上的流量之和，()fv+表示点v处出弧上的流量之和。注：(1)可行流总是存在的，比如0f≡。(2)现实问题中有许多关于网络和流的实例。比如：产销物资输送网络；输油管线网络；通信数据传输网络等。定义9.1.3设f是网络N=(V,X,Y,A,C)中的一个可行流，则必有()()fXfY+−=。()fX+(或()fY−)称为流f的流量，记为Valf。网络最大流问题：给定网络N=(V,X,Y,A,C)，求N中流量最大的可行流(称为最大流)。注：如果一个网络中的源点集和汇点集都只含一个顶点，则称该网络为单源单汇网络。任一网络N=(V,X,Y,A,C)都可导出一个单源单汇网络。方法如下：(1)给N添加两个新顶点s和t；(2)对xX∀∈，从s向x连一条弧，其容量为∞(或()(,)vNscsv+∈∑);(3)对yY∀∈，从y向t连一条弧，其容量为∞(或()(,)uNtcut−∈∑)。新添的顶点s和t分别称为人工源和人工汇，所得的新网络为(,,,,)NVstAC′′′′。y1x2x1v2y3v1x3y2v3v4444222222222222113v1yv3v2v4x2x136523412523此后的讨论中主要考虑单源单汇网络。定义9.1.4设N=(V,x,y,A,C)是一个单源单汇网络。SV⊆，SVS=−。用(,)SS表示尾在S中而头在S中的所有弧的集合(即从S中的点指向S之外点的所有弧之集)。若xS∈，而yS∈，则称弧集(,)SS为网络N的一个割。一个割(,)SS的容量是指(,)SS中各条弧的容量之和，记为Cap(,)SS。例：对网络令1235{,,,,}Sxvvvv=，则割(,)SS14345456{,,,}vvvvvvvv=。注：一个网络N可能有多个割，各个割的容量不一定相等。其中容量最小的割称为N的最小割。引理9.1.1对网络N中任一流f和任一割(,)SS，均有()()ValffSfS+−=−.证明：设f是网络N=(V,x,y,A,C)中的流，(,)SS是N的一个割，由流的定义，(),()0,()()0,({})fxValffxfvfvvSx+−+−==−=∀∈−。故{}()()[()()][()()][(,)(,)](,)(,)(,)(,)(,)(,).vSxvSvSuuvSuvSuvSuSvSuSvSuSvSuSValffxfxfvfvfvfvfvufuvfvufuvfvufvufuvfuv+−+−+−∈−∈∈∈∈∈∈∈∉∈∈∈∉=−+−=−=−=−=+−−∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑∑上式中第一式和第三式都表示S内部弧上流量之和，故相等；第二式表示从S的顶点指向S之外点的所有弧上流量之和，因此它等于()fS+；第四式表示从S之外的顶点指向S中点的所有弧上的流量之和，因此等于()fS−。从而()()ValffSfS+−=−。证毕。定义9.1.5.对弧a，若()0fa=，则称a是f零的；若()0fa，则称a是f正的；若()()faca=，则称a是f饱和的；若()()faca，则称a是f非饱和的。v7v1v4v3v6v8v5413342132322225655xyv2定理9.1.1.对网络N中任一可行流f和任一割K=(,)SS，均有ValfCapK≤。其中等式成立当且仅当(,)SS中每条弧都是f饱和的而且(,)SS中每条弧都是f零的。证明：因f是可行流，故()()()aKaKfSfacaCapK+∈∈=≤=∑∑，并且(,)()()0aSSfSfa−∈=≥∑。由引理9.1.1,()()ValffSfSCapK+−=−≤,可见第一个结论成立。另外注意到()fSCapK+=当且仅当(,)SS中每条弧都是f饱和的；而()0fS−=当且仅当(,)SS中每条弧都是f零的，故定理的第二个结论也成立。证毕。注：网络N的一个割K称为最小割，如果网络N中不存在割K′使得CapKCapK′。推论9.1.1设*f是网络N的一个最大流，K*是N的一个最小割，则**ValfCapK≤.证明显然。推论9.1.2设f是N的一个可行流，K是N的一个割，若ValfCapK=，则f是最大流而K是最小割。证明：由推论9.1.1，**ValfValfCapKCapK≤≤≤，因ValfCapK=，故由上式知，*ValfValf=，*CapKCapK=。证毕。SSK§9.2最大流最小割定理及求最大流的标号算法一、最大流最小割定理问题：给定网络(,,,,)NVxyAC=，如何求N中的最大流？定义9.2.1设1kPxvvy=…是网络(,,,,)NVxyAC=中一条x-y路(无向)，若弧1(,)iivvA+∈，则称此弧为路P的一条正向弧(或称前向弧，顺向弧)，若弧1(,)iivvA+∈，则称此弧为路P的一条反向弧(或称后向弧，逆向弧)。例如：在右图所示的路P上，所有弧都是正向弧；在路Q上，弧(v1,v3)和(v2,v6)是正向弧，而(v2,v4)和(v4,v3)是反向弧。可见，一条弧是正向弧还是反向弧与路有关。定义9.2.2设f是网络(,,,,)NVxyAC=中的一可行流，P是N中一条x-y路。如果对于P上任一条弧a，都有(1)若弧a是P的正向弧，则()()()0facafaΔ−；(2)若弧a是P的反向弧，则()()0fafaΔ.则称P是流f的一条可增路。沿路P可增加的流量为()min()aPfPfa∈Δ=Δ，称为路P上流的增量或可增量。例如：在下图中，每条弧上括号内的数字表示弧的容量，括号外的数字是当前流的流量。图（1）中虚线所示的路P是一条可增路。因13(,)615fvvΔ=−=，34(,)2fvvΔ=，42(,)5fvvΔ=，26(,)404fvvΔ=−=，故路P上的可增量()min{5,2,5,4}2fPΔ==。沿P增流后的流网络如图(2)所示。图(1)图(2)由此可见，如果能找到N中一条f可增路，则可沿着P修改流的值，得到一个流值更大的新流ˆf，修改办法如下：()()ˆ()()()(),aPaPPfafPfafafPfaa+Δ=−Δ⎧⎪⎨⎪⎩若是的正向弧若是的反向弧不在上，，(*)修改后的流值为：ˆ()ValfValffP=+Δ。这给出了求网络N的最大流的一个途径：反复找N中的可增路，沿可增路将流量扩大，直到找不出可增路为止。直观上想，此时应该已达到最大流。下面的定理证实了这一点。PQv2v5xyv3v4v1v6v2v5(x)(y)v3v4v1v64(4)3(6)1(1)0(3)2(3)3(5)3(5)0(1)2(4)5(5)v2v5(x)(y)v3v4v1v64(4)1(6)1(1)2(3)2(3)5(5)3(5)0(1)0(4)5(5)P定理9.2.1(,,,,)NVxyAC中的流f是N的最大流当且仅当N中不存在f可增路。证明：：必要性：若N有f可增路，则f不是最大流，因为沿P按(*)式修改流可得流值更大的流ˆf。充分性：设N中不存在f可增路，我们来证明f是最大流。令{|SvV=∈从源x到v有可增路}{}x∪，则yS∉，而xS∈，从而(,)KSS=是N中的一个割(见割定义)。对(,)SS中的任一条弧(,)auv=，必定()()faca=，(否则，若()()faca，因uS∈，从x到u有可增路P，Pa+是S到v的可增路，故vS∈，矛盾)；同理，对于(,)SS中任一条弧(,)avu=，必定()0fa=。这说明(,)SS中每条弧都是f饱和的而(,)SS中每条弧都是f零的。由定理9.1.1，ValfCapK=，再由推论9.1.2便知f是最大流(而且当前的K是最小割)。由定理9.2.1的证明立即可知：推论9.2.1(最大流最小割定理，Ford,Fulkerson,1956)任一个网络N中，最大流的流量等于最小割的容量。由推论9.2.1又知：推论9.2.2(整值最大流定理)，任一网络中，若所有弧的容量都是整数，则最大流的流值也必为整数。二、求最大流的Ford－Fulkerson标号法前面已得到求网络N中最大流的一种思想：从一个已知流(例如零流)开始，递推地构作流值严格增加的流序列。在每一个新的流f得出之后，若能找到一条f可增路P，则沿P修改流的值，得到一个更大的流ˆf，作为这个序列中的下一个流；若不存在ˆf可增路，则由定理9.1.1，f就是最大流，算法终止。问题：对一个流f,如何找f可增路或判断f可增路不存在？解答：Ford－Fulkerson标号法：标号过程描述：设当前可行流为f。从源点x开始。首先给x标上∞,即l(x)＝∞，[x称为已标未查顶点，其它顶点称为未标未查顶点]。任选一已标未查顶点u，检查其所有尚未标号的邻点。(1)对u的尚未标号的出邻点v(即()u,vA∈)，若(,)(,)cuvfuv，则给v标号：{}()min(),(,)(,)lvlucuvfuv=−，[v称为已标未查顶点]；否则，不给v标号。(2)对u的尚未标号的入邻点v(即()v,uA∈)，若(,)0fvu，则将v标号：{}()min(),(,)lvlufvu=，[v称为已标未查顶点]；否则，不给v标号。当检查完u的所有邻点之后，u称为已标已查顶点。反复进行上述标、查过程，最终必出现两种结果之一：(i)汇点y获得标号，此时已得到f可增路。沿该路增流。(ii)y点未获得标号，但已没有已标未查顶点(所有已标顶点都已被查，没有更多的新标号顶点)。此时当前的流f即为最大流[设当前已标已查的顶点之集为S，则(,)SS为最小割]例如：网络N(V,x,y,A,C)及其上一个流f,（括号内数字是弧容量）。情况(i)：获得一条f可增路情况(ii)：已得到最大流和最小割求网络最大流的Ford－Fulkerson标号算法：输入：网络(,,,,)NVxyAC输出：网络N中一个最大流。第0步(初始化)：对aA∀∈，令()0fa=；第1步：给源点x标号(,)x∞。:{},LxS==Φ。其中L表示已标未查集，S表示已标已查集。第2步：任取uL∈，检查u的每个尚未标号的邻点v。(1)若()vNu+∈，v尚未标号且(,)(,)Cuvfuv，则给v标号(,,())ulv+，其中()min{(),(,)(,)}lvluCuvfuv=−。令:{}LLv=∪。(2)若()vNu−∈，v尚未标号且(,)0fvu，则给v标号(,,())ulv−，其中()min{(),(,)}lvlufvu=。令:{}LLv=∪。第3步：重复第2步，直到汇点y被标号，或y未被标号但L=Φ为止。若是后者，算法结束，当前流是最大流；若是前者，转下步。第4步：令zy=。第5步：若z的标号为(,,())wlz+，则令(,)(,)()fwzfwzly=+；若z的标号为(,,())wlz−，则令(,)(,)()fzwfzwly=−。注：不论z是哪个点，此处总是l(y)，因l(y)是最大的可增量(沿可增路)。第6步：若wx≠，则令zw=，转第5步；否则，去掉所有的顶点标号，转第1步。v4v1v