网络流

作者: ffacs 分类: 总结 发布时间: 2020-01-16 08:48

网络流基本概念

流网络

$G=(V,E)$是一个有向图,图中每条边$(u,v,)\in E$有一个非负的容量值$c(u,v)\geq 0$,而且,如果边集合$E$包含一条边$(u,v)$,则图中不存在反方向的边$(v,u)$。如果$(u,v)\notin E$,则为方便起见,定义$c(u,v)=0$,并且在图中不允许自循环。在流网络的所有结点中,我们特别分辨出两个特殊结点:源结点$s$和汇结点$t$。为方便起见,假定每个结点都在从源结点到汇点的某条路径上。也就是说,对于每个结点$v \in V$,流网络都包含一条路径$s \sim> v \sim > t$。因此,流网络图是联通的,并且由于除源结点外的每个结点都至少有一条进入的边,我们有$|E| \geq |V| - 1$。

设$G=(V,E)$为一个流网络,其容量函数为$c$,设$s$为网络的源结点,$t$为汇点。$G$中的是一个实值函数$f: V \times V \rightarrow R$,满足下面两条性质

容量限制:对于所有的结点$u,v\in V$,要求$0 \leq f(u,v)\le c(u,v)$。

流量守恒:对于所有的结点$u \in V- \left\{ s,t \right\}$,要求$\sum\limits_{v\in V}f(u,v) = \sum\limits_{v\in V}f(v,u)$

当$(u,v) \notin E$时,从结点$u$到结点$v$之间没有流,因此$f(u,v)=0$。

我们称非负值$f(u,v)$为从结点$u$到结点$v$之间的流。一个流$f$的值$|f|$定义如下:
$$
|f|=\sum\limits_{v \in V}f(s,v)-\sum\limits_{v \in V}f(v,s)
$$
也就是说,流$f$的值三从源点流出的总流量减去流入源结点的总流量。

残存网络

设$f$为流网络$G$中的一个流,考虑结点$u,v \in V$,定义残存容量$c_f(u,v)$如下:
$$
c_f(u,v)=\left\{
\begin{aligned}
c(u,v)-f(u,v)\ \ \ 若(u,v) \in E\\
f(v,u)\ 若(v,u)\in E \\
0\ 其它
\end{aligned}
\right.
$$

给定一个流网络$G=(V,E)$和一个流$f$,则由$f$所诱导的残存网络为$G_f=(V,E_f)$,其中
$$
E_f=\left\{ (v,u)\in V \times V:c_f(u,v) >0\right\}
$$

增广路径

给定网络$G=(V,E)$和流$f$,增广路径$p$是残存网络$G_f$中一条从源结点$s$到汇结点$t$的简单路径。

网络流的切割

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

若流$f$是一个流,则定义横跨切割$(S,T)$的净流量$f(S,T)$如下:
$$
f(S,T)=\sum\limits_{u \in S}\sum\limits_{v \in T}f(u,v)-\sum\limits_{u \in S}\sum\limits_{v \in T}f(v,u)
$$
切割$(S,T)$的容量是:
$$
c(S,T)=\sum\limits_{u \in S}\sum\limits_{v \in T}c(u,v)
$$
一个网络的最小切割是整个网络中容量最小的切割。

最大流

给定一个流网络$G$,一个源结点$s$,一个汇结点$t$,我们希望找到值最大的一个流。

最大流最小割定理

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

1.$f$是$G$的一个最大流

2.残存网络$G_f$不包含任何增广路径

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

Ford-Fulkerson方法

只要有一条从源点到汇点的路径,在所有的边上都有可用容量,就沿着这条路径发送一个流。 然后再找到另一条路径,一直到网络中不存在这种路径为止。

因为有不同复杂度的实现,所以只能叫做方法

Edmonds–Karp算法

用bfs寻找增广路,即每次找最短的增广路。时间复杂度为$O(VE^2)$

Dinic

用bfs对图上结点根据残存网络上到源点的单位距离进行分层。然后再用dfs寻找增广路。增广路上的结点必须是不同层的。时间复杂度为$O(V^2E)$,在二分图上的时间复杂度为$O(\sqrt VE )$

给定一个流网络$G$,一个源结点$s$,一个汇结点$t$,我们希望找到值最大的一个流。

发表评论

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