网络流

定义

有向图\(G=(V,E)\)中:

有唯一的一个源点\(S\)和汇点\(T\),每一个图都有一个非负容量\(C_{u,v}\)

满足上述条件的图\(G\)称为网络流图(又称网络),记为\(G=(V,E,C)\)

对于网络流图\(G=(V,E,C)\)的每一条边\((u,v)\),给定一个数\(f_{u,v}\),且满足下列条件:

1、运量不能超过容量

2、除源点和汇点外,其余顶点\(v\)恒有流入=流出

这时\(G=(V,E,C)\)中的流称为\(G\)的可行流\(f\)

为了方便和出于对称性,我们认为:\(f_{u,v}=-f_{v,u}\)

当所有的\(f\)都为0时,那么就称\(f\)为零流,零流一定是可行流。

网络流的流量\(W\)=流向终点的流量。

求解最大流

只要不断地在现有的流网络上累加小的流,当不能累加的时候就得到了最大流。

如果现有的流并不是最大流的一部分,是否还能累加形成最大流呢?

可以,因为流是会与相反方向的流相互抵消的,我们可以发现,通过不同的流之间的叠加,我们可以通过回溯之前的流的部分路段,从而修正得到正确的选择。

所以之前的对称性得到了应用。

切割

定义:设\(G=(V,E,C)\)是一直的网络流图,假定\(s\)是\(V\)的一个子集,\(s’\)是\(s\)的补集,这样把顶点集\(V\)分成\(s\)和\(s’\)两个部分,满足\(S\in s\),\(T\in s’\)

对于一个端点在\(s\),另一个端点在\(s’\)的所有边的集合,叫做网络流图\(G\)的一个切割,用\((s,s’)\)表示。

切割容量:在切割中,把所有边容量和叫做这个切割的容量。

\[C_{s,s’}=\sum_{u \in s,v \in s’}C_{u,v}\]

净流量\(f_{s,s’}\):横跨切割\((s,s’)\)流量的代数和 – 净流量的值=当前的流量\(W\)

\[f_{s,s’}=\sum_{u \in s,v \in s’}f_{u,v}-\sum_{u \in s, v \in s’}f_{v,u}\]

最大流-最小割定理

引:对于已知的网络流图,从源点\(S\)到汇点\(T\)的流量\(W\)的最大值小于等于任何一个切割的容量,记\( W_{max} \geq min(C_{s,s’}) \)

最大流最小割定理(\(Ford-Fulkerson\)定理):

在一个给定的网络流图上,流的最大值等于切割容量的最小值,即

\[W_{max}=minC_{s,s’}\]

证明:

在网络流图\(G=(V,E,C)\)中,定义从源点\(S\)到汇点\(T\)的道路:设(\(V0=S,V1,V2,V3……Vn=T\))为\(G\)上的顶点序列,对于\(i=0,1,2……n-1\),都有(\(Vi,Vi+1\))或\(Vi+1,Vi\)属于\(E\),则称\(V0,V1,V2,……Vn\)是一条从\(S\)到\(T\)的道路。

由于\(G\)是有向图,道路上边的方向与道路方向一致的边称为前向边\(P^+\),反之称为后向边\(P^-\)。

道路上边的饱和:前向边若\(f_{u,v}=C_{u,v}\),后向边若\(f_{u,v}=0\)(对称性),则称边\((u,v)\)为关于该条道路上的饱和边。

若从\(S\)到\(T\)的道路上所有的边均不饱和,即对于\(P^+\)有\(f_{u,v}<C_{u,v}\),\(P^-\)有\(f_{u,v}>0\),则称这条边为可增广道路。

修改可增广道路上每条边的流量,同时保持网络流的可行性,达到流量的增加,其增量的确定方法如下:

令\( \delta(u,v)=\begin{cases} C_{u,v} – f_{u,v} , P+ \\ f_{u,v’} , P- \end{cases} \)

取\(δ=min{δ_{u,v}}\)为增量。

然后对可增广路的每一条前向边流量增加δ,每一套后向边减少\(δ\),从而使得整个网络流的流量增加。

设网络流图\(G\)的流量\(f\)达到最大,我们构造一个点的集合\(s\)如下:

  • \(S \in s\)

  • \(x \in s , f_{x,y} < C_{x,y}\ \ ->\ y \in s\)

  • \(x \in S , f_{y,x} > 0\ \ ->\ y \in s\)

由此可见,\(s\)就是从\(S\)出发、有空余流量的边所关联的点击,因此\(T\not\in s\),否则\(S\)到\(T\)不饱和,\(f\)不是最大流。

设\(s’\)是\(s\)的补集,那么\(T\in s’\) ,我们构造出了一个切割\((s,s’)\).

按照\(s\)的定义,若 \(x\in s\),\(y\in s’\) , 则\(f_{x,y}=C_{x,y}\) , \(f_{y,x}=0\)

所以

\[W_{max}=\sum (f_{x,y}-f_{y,x})=\sum f_{x,y}=C_{s,s’}\]

即:已证明最大流-最小割定理

求解最大流

我们已经证明了算法的正确性。每次新增一条刘鹗的时候,我们都要满足每条边的容量限制。即当前这条边的流量加上新的流量,不能超过边的剩余流量限制。

一个便捷的处理方式就是:记录这条边还能容纳的流量,即边的容量加上能够被回溯(对称边)的流量,称为”残存容量”。将所有的残存容量看成一个残存网络,也就是一个新的网络流问题,我们在新的图上继续寻找不饱和路径。

我们要做的就是记录每条边和它的反向边(对称性)以及每条边的剩余容量,写一个\(dfs\)每次寻找不饱和路径并修改容量,找不到时退出。此时我们得到了最大流。

使用\(dfs\)时间复杂度\(O(E)\),设最大流的流量为\(w\),由于每次流量最少+1,所以时间复杂度为\(O(Ew)\)

但是由于该算法\(FF\)每次只增广一条路径,缺点就是当最大流量较大时,寻找的路径错误可能使运行时间变长,出现反复增广。

当我们用\(bfs\)优化\(FF\)时,就得到了一个新的算法\(EK\),每次寻找残存网络上\(S\)到\(T\)的最短路径

所以时间复杂度为

\[O(VE^2)\]

为了加快算法的运行时间我们需要一次增广多条路径,就得到了\(Dinic\)算法。

每次对残存网络\(bfs\)标记每个点距离S的深度(容量有剩余的边才会出现在残余网络上),dfs的时候只对与当前点有边且深度大1的点继续增广。

记录当前顶点\(u\),以及到目前为止剩余能分配的容量\(limit\)。

每次更新完之后,残余网络上所有源点到汇点的最短路径都被阻塞。所以,最多只要\(V\)次更新就可以找到最大流。

每次更新时间复杂度为\(O(VE)\)

总复杂度为\(O(V^2E)\)

实际更快。


By:Wahacer

资料来源:某学姐的ipad~

2017.9.30

发表评论

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