最大流问题

发布于 2020-06-16 21:44:14   阅读量 52  点赞 0  

一、定义

1. 流网络

流网络 G=(V,E) 是一个有向图,图中每边都有一个非负的 容量值 c(u,v)\geq0,且图中不存在反向边。在网络的结点中有两个特殊的结点:源点 s汇点 t

 而流的形式化定义如下:设 G=(V,E) 为流网络,其 容量函数c,设 s 为网络的源结点,t 为汇点。G 中的流为一个函数 f: V \times V \rightarrow R,且函数 f(流)满足以下性质:

  • 容量限制:对于所有结点 u,v \in V,都有 0 \leq f(u,v) \leq c(u,v)

  • 流量守恒:对于所有结点 u \in V-{s,t},都有 \sum f(v,u) = \sum f(u,v)

    对于除源点与汇点之外的结点,流入等于流出(无堆积)。

 称 f(u,v) 为从结点 u 到结点 v 的流。

 而 网络的流 f 定义为:|f| = \sum f(s,v) - \sum f(v,s) ,即为从源结点流出的总流量减去流入源结点的总流量。

 在最大流问题中,一般给定义一个流网络 G、一个源结点 s、一个汇点 t,来求取流的最大值。


反平行边问题

 若使用流网络模拟存在反向平行边的问题,则必须将该问题转换为一个等价但不包括反平行边的网络。这样得出的网络满足限制条件:若一条边属于流网络,则其反向边不属于该网络。


具有多个源结点与汇点的网络

 在具有多个源结点与汇点的网络中,确定最大流的问题可以归约为一个普通的最大流问题。转换方法为加入一个 超级源结点 s,且对于源点 i=1,2,...,m,加入有向边 (s,s_i) 与其容量 c(s,s_i)=\infty;同时,创建一个 超级汇点,且对于汇点 i=1,2,...,n,加入有向边 (t_i,t),其容量 c=(t_i,t=\infty)

 单源结点 s 能够给原来的多个源结点 s_i 提供所需的流量,单汇点 t 则可以消费原来多个汇点 t_i 所消费的流量。



2. 残存网络

 给定流网络 G 与流量 f残存网络 G_f 由流网络 G 中仍有空间对流量进行调整的边构成。

 残存网络的边由残存流量构成,残存流量可能为:

  • 某边允许的额外流量
     若流网络中的某边允许额外的流量通过,则将该边加入残存网络,且其 残存容量 设为 c_f(u,v)=c(u,v)-f(u,v)

  • 某边正流量的缩减(反向流量)
     残存网络可能包含流网络中不存在的边。算法操作的目标是增加总流量,因此能对特定边上的原有流量进行缩减。为表示对正流量 f(u,v) 的缩减,将边 (v,u) 添加到 G_f 中,并将其 残存流量 设为 c_f(v,u)=f(u,v),一条边所允许的反向流量最多将其正向流量抵消。残存网络中的这些反向边允许算法将已发送出来的流量发送回去。


 即,流网络中某边与残存网络中边的对应为:


残存流量 c_i(u,v) 的形式化定义为:


 对于给定流网络 G=(V,E) 和一个流 f,则由 f 诱导的 残存网络G_f=(V,E_f),其中 E_f=\{(u,v)\in V\times V , c_f(u,v) > 0\},即 E_f 中的边要么是 E 中原有的边,要么是其反向边,因此有 |E_f| \leq 2|E|

 残存网络类似一个容量为 c_f 的网络,但该网络并不满足对流网络的定义,因其包含反向边。


递增

残存网络中的一个流给我们指出了一条路线图:如何在原来的流网络中增加流。f 是流网络的一个流,f' 是对应残存网络中的一个流,定义 f \uparrow f' 为流 f' 对流 f递增

引理

 若 G_f 为流 f 所诱导的 G 的残存网络,设 f'G_f 的一个流,则函数 f \uparrow f' 是原流网络 G 的一个流,其值为 |f \uparrow f'|=|f|+|f'|

即递增也是流网络中的一个流。


增广路径

 增广路径 p 是指残存网络 G_f 中一条从源结点 s 到汇点 t 的简单路径。

 根据残存网络的定义,对于一条增广路径上的边 (u,v),可以增加其流量的幅度最大为 c_f(u,v),而不会违反原始流网络中对 (u,v)(v,u) 的限制。

残存容量

 一条增广路径 p 上能够为每条边增加的流量的最大值为路径 p残存容量c_f(p) = min\{ c_f(u,v),(u,v) \in p \}

引理

 设 p 为残存网络 G_f 中的一条增广路径,定义一个函数 f_p:V \times V \rightarrow R

 则 f_p 是残存网络 G_f 中的一个流,其值为 |f_p|=c_f(p) > 0



推论

 设 f 是流网络 G 中的一个流,设 p 为残存网络 G_f 中的一条增广路径,f_p 是残存网络的一个流,则函数 f \uparrow f_p 是图 G 的一个流,且其值 |f \uparrow f_p| = |f|+|f_p| > |f|

 即 若将流 f 增加 f_p 的量,则将获得 G 的另一个流,该流的值更加接近最大值。

一个流是最大流当且仅当其残存网络不包含任何增广路径。



3. 切割

 流网络 G=(V,E) 中的一个切割 (S,T) 将结点集合 V 划分为 ST=V-S 两个集合,并使得 s \in S,t \in T

净流量

 若 f 是一个流,则横跨切割 (S,T) 的净流量 f(S,T) 定义为:f(S,T)=\sum{u \in S}\sum{v \in T}f(u,v)-\sum{u\in S}\sum{v\in T}f(v,u)

对于给定流 f,横跨任何切割的净流量都相同,等于 |f|,即流的值。



容量

 切割 (S,T) 的容量是:c(S,T)=\sum{u \in S}\sum{v \in T}c(u,v)一个网络的最小切割是整个网络中容量最小的切割

 流的定义与切割容量的定义之间存在不对称性。对于流,我们考虑的是从 ST 的流量减去从 TS 的流量;而切割的容量只计算从集合 S 进入集合 T 的边的容量,而忽略反向边上的容量。



推论

 流网络 G 中任意流 f 的值不能超过 G 的任意切割的容量。即 一个流网络中最大流的值不能超过该网络最小切割的容量

这也表明,一个最大流的值等于一个最小切割的容量。



4. 最大流最小切割定理

 若 f 是流网络 G=(V,E) 中的一个流,该流网络源结点为 s,汇点为 t,则以下条件是等价的:

  1. fG 的一个最大流;

  2. f 对应的残存网络 G_f 不包含任何增广路径;

  3. |f|=c(S,T),其中 (S,T) 是流网络 G 的某个切割。



二、Ford-Fulkerson

 Ford-Fulkerson 方法包含了几种不同的具体实现,它们都依赖于:残存网络、增广路径与切割。

1. 基本的 Ford-Fulkerson 算法

 Ford-Fulkerson 方法循环增加流的值。在开始时,令所有 f(u,v)=0,在每一次迭代中,寻找某条增广路径 p,然后使用 p 来对流 f 进行修改(增加)。

伪代码:

 该算法的时间复杂度取决于第 3 行中是如何寻找增广路径,若使用 DFS/BFS 来寻找增广路径,则算法运行时间将是多项式的时间复杂度。


Last Modified : 2020-06-29 19:34:51