【咕咕咕】

概念

流网络

倒是费了半天劲画了个图

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

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

割