图的网络流基本概念

Published on 2016 - 06 - 26

基本概念

网络最大流、增广路、残留网络、最小割这几个概念是构成最大流最小割定理(定理5)的基本概念,而该定理是网络流理论的基础。

容量网络和网络最大流

容量网络(Capacity Network):设G(V,E)是一个有向网络,在V中指定了一个顶点,称为源点(记为Vs),以及另一个顶点,称为汇点(记为Vt);对于每一条弧<u,v>∈E,对应有一个权值c(u,v)>0,称为弧的容量(Capacity)。通常把这样的有向网络G称为容量网络。

例如,图2(a)所示的有向网络就是一个容量网络,每条弧上的数值表示弧的容量。

弧的流量(Flow Rate):通过容量网络G中每条弧<u,v>上的实际流量(简称流量),记为f(u,v)。

网络流(Network Flow):所有弧上流量的集合f={f(u,v)},称为该容量网络G的一个网络流。

在图2(b)中,每条弧旁边括号内的两个数值(c(u,v),f(u,v)),第1个数值表示弧容量,第2个数值表示通过该弧的流量。例如,弧<Vs,V1>上的两个数字(8,2),前者是弧容量,表示通过该弧最大流量为8,后者表示目前通过该弧的实际流量为2。

从图2(b)中可见如下几点。

  1. 通过每弧的流量均不超过弧容量。
  2. 源点Vs流出的总量为3+2=5,等于流入汇点Vt的总量2+3=5。
  3. 其他中间顶点的流出流量等于其流入流量。例如,中间顶V2的流入流量为3,流出流量为:2+1=3。

可行流(Feasible Flow):在容量网络G(V,E)中,满足以下条件的网络流f,称为可行流。

  • 弧流量限制条件:

  • 平衡条件:

对于任何一个容量网络,可行流总是存在的,如f={0},即每条弧上的流量为0,该网络流称为零流(Zero Flow)

伪流(Pseudoflow):如果一个网络流只满足弧流量限制条件(式1),不满足平衡条件,则这种网络流称为伪流,或称为容量可行流。

最大流(Maximum Flow):在容量网络G(V,E)中,满足弧流量限制条件和平衡条件、且具有最大流量的可行流,称为网络最大流,简称最大流。

链与增广路

在容量网络G(V,E)中,设有一可行流f={f(u,v)},根据每条弧上流量的多少以及流量和容量的关系,可将弧分为以下4种类型。

  1. 饱和弧,即f(u,v)=c(u,v)。
  2. 非饱和弧,即f(u,v)<c(u,v)。
  3. 零流弧,即f(u,v)=0。
  4. 非零流弧,即f(u,v)>0。

例如,在图2(b)中,弧<V1,V4>、<V1,V3>是饱和弧;弧<Vs,V2>、<V2,V1>等是非饱和弧;弧<V2,V4>、<V3,V4>是零流弧;弧<V1,V4>、<V3,Vt>等是非零流弧等。

不难看出,饱和弧与非饱和弧,零流弧与非零流弧这两对概念是交错的,饱和弧一般也是非零流弧,零流弧一般也是非饱和弧。

链(Chain):在容量网络中,称顶点序列(u,u1,u2,...,un,v)为一条链,要求相邻两个顶点之间有一条弧,如<u,u1>或<u1,u>为容量网络中的一条弧。

设P是G中从Vs到Vt的一条链,约定从Vs指向Vt的方向为该链的正方向。注意,链的概念不等同于有向路径的概念,在链中,并不要求所有的弧都与链的正方向同向。

沿着Vs到Vt的一条链,各弧可分为两类。

  1. 前向弧(方向与链的正方向一致的弧),其集合记为P+。
  2. 后向弧(方向与链的正方向相反的弧),其集合记为P-。

注意,前向弧和后向弧是相对的,即相对于指定链的正方向。

例如,在图3(a)中,指定的链为:P={Vs,V1,V2,V4,Vt},这条链在图3(a)中用粗线标明。则P+和P-分别为:

P+={<Vs,V1>,<V2,V4>,<V4,Vt>}
P-={<V2,V1>}

注意,同一条弧可能在某条链中是前向弧,而在另外一条链中是后向弧。例如,如图3(b)所示,弧<V2,V1>在链P1={Vs,V1,V2,V4,Vt}是后向弧,而在链P2={Vs,V2,V1,V3,Vt}是前向弧。

增广路(Augmenting Path)。设f是一个容量网络G中的一个可行流,P是从Vs到Vt的一条链,若P满足下列条件。

  1. 在P的所有前向弧<u,v>上,0≤f(u,v)<c(u,v),即P+中每一条弧都是非饱和弧。
  2. 在P的所有后向弧<u,v>上,0<f(u,v)≤c(u,v),即P-中每一条弧是非零流弧。

则称P为关于可行流f的一条增广路,简称为增广路(或称为增广链、可改进路)

那么,为什么将具有上述特征的链P称为增广路呢?原因是可以通过修正P上所有弧的流量f(u,v)来把现有的可行流f改进成一个值更大的流f1。

沿着增广路改进可行流的操作称为增广(augmenting)

下面具体地给出一种方法,利用这种方法就可以把f改进成一个值更大的流f1。这种方法是:

  1. 不属于增广路P的弧<u,v>上的流量一概不变,即f1(u,v)=f(u,v);
  2. 增广路P上的所有弧<u,v>上的流量按下述规则变化:(始终满足可行流的2个条件) ①在前向弧<u,v>上,f1(u,v)=f(u,v)+α; ②在后向弧<u,v>上,f1(u,v)=f(u,v)-α。

称α为可改进量,它应该按照下述原则确定:α既要取得尽量大;又要使变化后f1仍满足可行流的两个条件——容量限制条件和平衡条件。

不难看出,按照这个原则,α既不能超过每条前向弧的c(u,v)-f(u,v),也不能超过每条后向弧的f(u,v)。因此α应该等于每条前向弧上的c(u,v)-f(u,v)与每条后向弧上的f(u,v)的最小值。即:

图4(a)给出了一条增广路P(Vs,V1,V2,V4,Vt)。现在就按照上面讲的方法将流f改进成一个更大的流。首先应该确定改进量α,先看P的前向弧集合:

P+={<Vs,V1>,<V2,V4>,<V4,Vt>}
Cs1-fs1=8-2=6
C24-f24=4-0=4
C4t-f4t=7-3=4

再看P的后向弧集合:P-={<V2,V1>},在这条弧上f21=2。

因此α最多取2,这样既可以使改进后的每条前向弧上的流量有所增加,又可以使改进后的每条后向弧上的流量在减少α之后不至于变成负数。改进后的流如图4(b)所示,改进后的流,其流量为7。

残留容量与残留网络

残留容量(residual capacity):给定容量网络G(V,E)及可行流f,弧<u,v>上的残留容量记为c′(u,v)=c(u,v)-f(u,v)。每条弧的残留容量表示该弧上可以增加的流量。因为,从顶点u到顶点v流量的减少,等效于顶点v到顶点u流量增加,所以每条弧<u,v>上还有一个反方向1的残留容量c′(v,u)=-f(u,v)。

残留网络(residual network):设有容量网络G(V,E)及其上的网络流f,G关于f的残留网络(简称残留网络)记为G′(V′,E′),其中G′的顶点集V′和G的顶点集V相同,即V′=V,对于G中的任何一条弧<u,v>,如果f(u,v)<c(u,v),那么在G′中有一条弧<u,v>∈E′,其容量为c′(u,v)=c(u,v)-f(u,v),如果f(u,v)>0,则在G′中有一条弧<v,u>∈E′,其容量为c′(v,u)=f(u,v)。残留网络也称为剩余网络。

从残留网络的定义可以看出,原容量网络中的每条弧在残留网络中都化为一条或两条弧。例如图5(a)所示的容量网络G,其残留网络G′为图5(b)。

残留网络中每条弧都表示在原容量网络中能沿其方向增广,弧<u,v>的容量c′(u,v)表示原容量网络能沿着u到v的方向增广大小为c′(u,v)的流量。因此,在残留网络中,从源点到汇点的任意一条简单路径都对应一条增广路,路径上每条弧容量的最小值即为能够一次增广的最大流量。

例如,在图5(b)中,源点到汇点的一条路径为(Vs,V2,V4,Vt),这条路径有3条弧,容量分别为1、4、5,因此沿着这条路径增广可以增加1个单位的流量。

残留网络与原网络有如下关系。

定理1(残留网络与原网络的关系) 设f是容量网络G(V,E)的可行流,f′是残留网络G′的可行流,则f+f′仍是容量网络G的一个可行流。(f+f′表示对应弧上的流量相加。)

割与最小割

割(Cut):在容量网络G(V,E)中,设E′⊆E,如果在G的基图中删去E′后不再连通,则称E′是G的割。割将G的顶点集V划分成两个子集S和T=V—S。将割记为(S,T)。

S—t割:更进一步,如果割所划分的两个顶点子集满足源点Vs∈S,汇点Vt∈T,则称该割为S—t割。S—t割(S,T)中的弧<u,v>(u∈S,v∈T)称为割的前向弧,弧<u,v>(u∈T,v∈S)称为割的反向弧。(注意,如无特别说明,所说的割均指S—t割。)

割的容量:设(S,T)为容量网络G(V,E)的一个割,其容量定义为所有前向弧的容量总和,用c(S,T)表示。即:

例如在图6(a)中,如果选定S={Vs,V1,V2,V3},则T={V4,Vt},(S,T)就是一个S—t割。其容量c(S,T)为图中粗线边<V2,V4>,<V1,V4>,<V3,V4>,<V3,Vt>的容量总和,即:

c(S,T)=C24+C14+C34+C3t=4+2+6+9=21

最小割(Minimum Cut):容量网络G(V,E)的最小割是指容量最小的割。

割的净流量:设f是容量网络G(V,E)的一个可行流,(S,T)是G的一个割,定义割的净流量f(S,T)为:

注意:

  1. 在统计割的净流量时:在式(6-5)中,反向弧的流量为负值,即如果<v,u>∈E,那么在统计割的净流量时f(u,v)是一个负值。
  2. 在统计割的容量时:在式(6-4)中,不统计反向弧的容量。

例如,在图6(b)中,S={Vs,V1},则T={V2,V3,V4,Vt},割(S,T)的容量c(S,T)为:

c(S,T)=Cs2+C14+C13=4+2+2=8

割(S,T)的净流量为:f(S,T)=fs2+f21+f14+f13=3+(-2)+2+2=5

定理2(网络流流量与割的净流量之间的关系) 在一个容量网络G(V,E)中,设其任意一个流为f,关于f的任意一个割为(S,T),则有f(S,T)=—f—,即网络流的流量等于任何割的净流量。

例如,在图6(b)中,f(S,T)=5,—f—=5,两者相等。

定理3(网络流流量与割的容量之间的关系) 在一个容量网络G(V,E)中,设其任意一个流为f,任意一个割为(S,T),则必有f(S,T)≤c(S,T),即网络流的流量小于或等于任何割的容量。

根据下面的定理5可知,定理3中的关系式当且仅当f为最大流,(S,T)为最小割时取等号。例如,在图6(b)中,c(S,T)=8,该图所示的割实际上是一个最小割,在后面的讨论中可以看到,该容量网络的最大流为8。

最大流最小割定理

如何判定一个网络流是否是最大流?有以下两个定理。

  • 定理4(增广路定理) 设容量网络G(V,E)的一个可行流为f,f为最大流的充要条件是在容量网络中不存在增广路。
  • 定理5(最大流最小割定理) 对容量网络G(V,E),其最大流的流量等于最小割的容量。

根据定理4和5,可以总结出以下4个命题是等价的(设容量网络G(V,E)的一个可行流为f)。

  1. f是容量网络G的最大流。
  2. │f│等于容量网络最小割的容量。
  3. 容量网络中不存在增广路。
  4. 残留网络G′中不存在从源点到汇点的路径。

例如,图7(a)所示的网络流是容量网络中的最大流,其流量为8。粗线所表示的弧组成了一个最小割,其容量也为8。在图7(a)中,不存在增广路,而在图7(b)所示的残留网络中,也不存在从源点到汇点的路径。

参考文档


  1. 当该条为反向弧时,这条弧较少的量即为流量增加的量,所以可以得出这里的结论。