【咕咕咕】
概念
流网络
倒是费了半天劲画了个图
这个有向图就是一个流网络。并且我们在接下来的讨论中默认没有自环(默认没有反向边)(即u->v后无v->u的边)。主要是可能比较更加的难理解。我们记录该流网络 $G=(V,E)$即所有的点集$V$和边集$E$。
容量
参考上图,其中每两个点之间上的值就叫流量。例如,上图中点S->点1的容量为5.记作 $c(s,1)=5$
一般的记录为$c(u,v)$。
流量
同样参考上图,但是这个流量是可以定义的。例如我们可以假设点S->点1的流量为5。记作$f(s,1)=5$一般的记录为$s(u,v)$
可行流
当我们知道了前面的定义,我们可以开始定义可行流。当这个流网络符合以下规则即为可行流。同样不考虑反向边
- $f(u,v)≤c(u,v)$ 即所有边的流量都应该小于对应边的容量。(容量限制)
- $ \sum_{E \in (u,v) \notin S,T}f(u,v)=\sum_{E \in (v,x) \notin S,}f(v,x)$ [heimu]可能不太会写公式[/heimu]大概就是所有入的变的流量等于出边的流量(流量守恒)
符合以上规则的流网络即为可行流
最大可行流
顾名思义就是求$max\{sum_{f(s,v)}\}$(最大的所有从起点出的流量)
残留网络
此处会应用到反向边。
此处反向边的作用是(给网络流一个反悔的可能)
那么残留网络是怎么操作的呢:
- 保留点集$V$,删除边集$E$
- 将所有原有边集有向边$(u,v)$连权为$f(u,v)$(流量),$from=u,to=v$即$u-^{E(u,v)}->v $。
- 将所有原有边集有向边$(u,v)$连反向边为$c(u,v)-f(u,v)$,$from=u,to=v$即 $v -^{\space 0}->u$
记残留网络为$G_f$,其中$f$是原有可行流。
关于残留网络相关的定理
残留网络本身就是一种可行流。所以记残留网络为$f'$.
增广路
沿着非零的可行流$f(u,v)$走,能从$S$(起点)走到$T$(终点)。
性质:最大可行流没有增广路
One comment
前排!