smallfang

网络流笔记
【咕咕咕】概念流网络倒是费了半天劲画了个图这个有向图就是一个流网络。并且我们在接下来的讨论中默认没有自环(默认没有...
扫描右侧二维码阅读全文
16
2021/08

网络流笔记

【咕咕咕】

概念

流网络

image.png

倒是费了半天劲画了个图

这个有向图就是一个流网络。并且我们在接下来的讨论中默认没有自环(默认没有反向边)(即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)$

可行流

当我们知道了前面的定义,我们可以开始定义可行流。当这个流网络符合以下规则即为可行流。同样不考虑反向边

  1. $f(u,v)≤c(u,v)$ 即所有边的流量都应该小于对应边的容量。(容量限制)
  2. $ \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)}\}$(最大的所有从起点出的流量

残留网络

此处会应用到反向边。

此处反向边的作用是(给网络流一个反悔的可能)

那么残留网络是怎么操作的呢:

  1. 保留点集$V$,删除边集$E$
  2. 将所有原有边集有向边$(u,v)$连权为$f(u,v)$(流量),$from=u,to=v$即$u-^{E(u,v)}->v $。
  3. 将所有原有边集有向边$(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$(终点)。

性质:最大可行流没有增广路

Last modification:August 18th, 2021 at 07:41 pm
End.

One comment

  1. WyyOIer

    前排!

Leave a Comment