Max-flow min-cut (最大流-最小割定理)

最大流-最小割定理是网络信息流理论(Network infomation flow)的基石。这个定理我的理解就是“多粗的管子,水就最多多大流量”,比如从自来水厂到用水大户工业小区A 能达到的水的最大流量是多大?考虑到可能从水厂到小区有不少到达的水管,那么最大的流量等于拆掉最少最细的水管后水厂不能给小区A 供水的那些水管流量的集合。当然这种说法并不不严谨,因为这里水管不是双向的,而在网络中谈论的信息流却可是是双向的。下面详细介绍最大流—-最小割定理。

流网络图G = (V,E) 是有向图,其中

V 是所有节点(vertex)的集合;

E 是所有边(edge)的集合;

源点s 是信息的起始点

宿点t 是信息的到达点

其中(u,v)∈E 代表节点u,v 之间存在一条边,边容量由c(u,v) 表示(可以理解为网络带宽或者能达到的最大流量),如果(u,v)∉E ,那么c(u,v) = 0 。那么可以用有向图矩阵来表示图G:[C]|V|×|V| Ci,j = c(i,j) 其中i,j ∈ V 。

f(u,v) 称为从u 点到v 点的流,c 进一步扩展为两个点之间的容量函数,如果u 和v 是相邻节点,那么c(u,v) 是两点之间的容量,这和前面的定义的一致的。流满足三个性质:

  1. 容量约束:所有 u,v ∈ V ,要求 f(u,v) ≤ c(u,v)
  2. 反对称性:所有 u,v ∈ V ,要求 f(u,v) = -f(v,u)
  3. 流守恒性:对于所有 u ∈ V-{s,t},要求 ∑ f(u,v) = 0

最大流问题实际上是在给出一个具有源点、宿点的流网络,找出从源点到宿点的最大值流。

残留网络(residual network),增广路径(augmenting path)和割(cut)是最大流—最小割定理的精髓,该定理用割来描述最大流问题。

f 是图G 中一个流,u,v 是其中的节点,在不超过容量c(u,v) 的条件下,节点u 和v 之间可以加入的额外网络流量就是u,v 的残留容量(residual capacity)。

节点还是原来图G 中的节点,只是边上的容量为残留容量:cf(u,v) = c(u,v) -f(u,v),那么由于流f ,可以得到一个残留网络Gf = (V,Ef),其中 E= {(u,v)∈V×V : cf(u,v)>0}。残留网络本身也是一个流网络,其容量受cf 限制(还是拿水管打比方,流f 好比从水厂到用水小区的一次通水,水管种剩余还可以流水的流量组成了残留网络)。

已知一个流网络G = (V,E) 和流f ,增广路径p 为残留网络Gf 中s 到t 的一条简单路径。称能够沿增广路径p 的每条边传输的网络流的最大量为p 的残留容量。其形式化定义为:

cf(p) = min{cf(u,v) : (u,v)在p 上}

根据增广路径可以定义在残留网络Gf 上的一个流fp ,流量|fp | 等于路径p 的残留容量cf(p) > 0 。

f’ = f + fp 也是G 的一个流,并且它比f 更接近最大值流。

Ford-Fullkerson 给出的方法就是不断增加流,直至找到最大流为止。一个流是最大流当且仅当它的残留网络不包含增广路径(那么源点在残留网络中不可达宿点)。

流网络中的(S,T) 将节点集合V 划分为S 和T=V-S 两部分,割(S,T) 的容量定义为c(S,T) ,它等于从S 中所有节点直接连接到T 中所有节点边的容量和。一个网络中最小割即是网络的所有割中具有最小容量的割。流f 通过割(S,T) 的净流被定义为f(S,T) 。虽然通过割的流可能包括点之间的负网络流,但是,割的容量是非负的。也就是说,通过割(S,T) 的净流由正反双向网络流构成,即记上S→T 的正网络流,减去T→S 的正网络流。

f 是G 中的一个流,(S,T) 是G 中的一个割,那么通过割(S,T) 的净流为f(S,T) = |f|。因此,通过任意割的净流都是相同的,并且与流的值相同。对于一个流网络G 中任意流f 来说,其值的上限为G 的任意割的容量。显然网络的最大流一定不会超过该网络最小割的容量(计算割的净流是要算上反向流量的,但是如果是算容量就不用算。如下图 i/j 表示的是i:流量,j:容量,那么割的净流是19,容量是26)。

cut

最大流—最小割定理  如果f 是具有源点s 和宿点t 的流网络G=(V,E) 中的一个流,则下列条件是等价的:

(1)f 是G 的一个最大流

(2)残留网络Gf 不包含增广路径

(3)对G 的某个割(S,T),有|f| = c(S,T)

网络最大流的值等于某一个最小割的容量。

Max-flow min-cut (最大流-最小割定理)》上有2条评论

  1. 如下图 i/j 表示的是i:流量,j:容量,那么割的净流是19,容量是24)。容量不是26???

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据