下面一切基础知识都是为求出最大流而服务的。
以 定义（ \(\text D\) ）和 引理、定理、结论、推论（ \(\text T\) ）的形式呈现。
（ \(\text D\) ）网络 Network ：网络是一个有向图 \(G=(V,E)\) ，对于每一条边，有一个容量 capacity \(c(u,v)\) 。同时在图中还有两个特殊点 \(s,t\) ，一个叫源点一个叫汇点。
注意在网络中我们不考虑负容量，我们总认为 \(c(u,v)\ge 0\) 。
注意在网络中我们不考虑反向边，如果有反向边我们也可以拆开，就没有反向边了：
（ \(\text D\) ）可行流 Flow ：一个流给每一条边提供了一个函数值 \(f(u,v)\) ，当满足如下条件时，它是可行流：
性质一：容量限制 \(\forall (u,v)\in E,0\le f(u,v)\le c(u,v)\)
性质二：流量守恒 \(\forall v\in V,\sum_{(u,v)\in E}f(u,v)=\sum_{(v,w)\in E}f(v,w)\)
网络可以想象为一个排水系统（此处应有 [NOIP2020] ），其中 \(s\) 为一个大水库， \(t\) 就是一个大池塘，我们可以通过带有每秒流量上限的管道将水从 \(s\) 运输到 \(t\) 。一个流的两个限制等价于水管不能爆，且中间的节点不能存水。
我们可以接着定义可行流的流量 \(|f|\) 为 \(s\) 流出的净流，也即：
此时我们就知道了最大流为网络上的最大可行流。
（ \(\text D\) ）残留网络 Residual Network ：这是对于原图 \(G\) 和 \(G\) 上的任意可行流 \(f\) 定义的。我们定义 \(G_f=(V_f,E_f)\) 为：
可以发现，我们在残留网络中引入了反向边，但是仍然强调原图中是没有反向边的。
当然，可以发现残留网络也是一个网络，所以说上面也有可行流。于是就有了下面的定义及性质：
（ \(\text D\) ）流的加法：对于 \(G\) 上的可行流 \(f\) 和 \(G_f\) 上的可行流 \(f‘\) ，我们定义 \(g=f+f‘\) 在原图上的流为：
此时反向边可以理解为 " 退流 " 。虽然直观上很好理解，但我们仍有必要证明一下 \(g\) 也是可行流：
（ \(\text T\) ）对于 \(G\) 上的可行流 \(f\) 和 \(G_f\) 上的可行流 \(f‘\) ，\(g=f+f‘\) 是原图的可行流：
性质一
根据可行流的定义，对于原图上任意的 \((u,v)\in E\)，有：
根据第二条有 \(f(u,v)-f‘(v,u)\ge 0\) ，再根据 \(f‘(u,v)\ge 0\) 可以推出 \(g(u,v)\ge 0\) 。
根据第一条有 \(f(u,v)+f‘(u,v)\le c(u,v)\) ，再根据 \(f‘(v,u)\ge 0\) 可以推出 \(g(u,v)\le c(u,v)\) 。
可知流 \(g\) 满足性质一。
性质二
对于 \(f‘\) 有：
移项之后有：
然后加到 \(f\) 上面就能发现 \(g\) 也是守恒的。
综上可知 \(g\) 是可行流。
这个性质告诉我们，如果 \(G_f\) 上面有 \(|f‘|>0\) 的可行流 \(f‘\)，那么 \(f\) 一定不是 \(G\) 的最大流 。
（ \(\text D\) ）增广路 Augmenting Path ：增广路定义为任意网络上的一条从 \(s\) 到 \(t\) 的简单路径 \(P\) 。定义增广路的容量 \(\delta(P)=\min\{c(u,v)|(u,v)\in P\}\) 。
本质上增广路就是一种最简单的可行流。结合性质 5 可以发现，最大流 \(f\) 的 \(G\) 上也不会有 \(\delta(P)>0\) 的增广路。
此时困扰我们的问题就是：对于 \(G\) 上的可行流 \(f\) ，如果 \(G_f\) 上不存在 \(\delta>0\) 的增广路， \(f\) 是否是最大流？我们还无法断言，因为有可能我们会陷入局部最优解。为了解决这个问题，我们将要引入割这个概念。
（ \(\text D\) ）鸽咕咕咕 割 Cut ：网络上的一个割定义为对于点集 \(V\) 的一个划分 \([S,T]\) 。它们需要满足：
性质一： \(S\cup T=V,S\cap T=\varnothing\)
性质二：\(s\in S,t\in T\)
注意 \(S\) 和 \(T\) 并不需要各自内部联通。因此一个网络的割的划分数为 \(2^{n-2}\) 。
（ \(\text D\) ）割的容量：定义 \(G\) 的一个割 \([S,T]\) 的容量为：
为了方便，我们也可以认为 \((u,v)\not \in E\Rightarrow c(u,v)=0\) 。因此上式可以简化。
此时我们知道了最小割为网络上的最小容量割。
（ \(\text D\) ）割的流量：定义 \(G\) 的一个割 \([S,T]\) 对于 \(G\) 上任意一个可行流 \(f\) 的流量为：
注意这里的定义是不对称的。割的容量只考虑正向边，而割的流量同时考虑正向和反向边。
并且，显然有 \(f(S,T)\le c(S,T)\) 。
仔细思考我们不难提出如下猜想：是否有 \(|f|=f(S,T)\) ？
感性理解是很自然的，对于任意一个割，我们将 \(S\) 分为与 \(s\) 相通的 \(S_c\) 和不相通的 \(S_c‘\) 。那么 \(S_c‘\) 的部分流量守恒，而 \(S\) 流到 \(T\) 流必然会经过 \(S_c\) 到 \(T\) 的边。下面我们将一步步证明这一点。
（ \(\text D\) ）任意点集的流量：定义 \(G\) 上的任意两个点集 \(X,Y\) 对于任意一个可行流 \(f\) 的流量为：
这个定义存在如下性质：
（ \(\text T\) ）对于 \(G\) 上的任意两个点集 \(X,Y\) 和任意一个可行流 \(f\) ， \(f(X,Y)\) 存在如下性质：
性质一
证明略。
性质二
证明也略。
性质三
当 \(Y\cap Z=\varnothing\) 时，存在：
这是因为 \(X\) 流向 \(Y\) 的流量和 \(X\) 流向 \(Z\) 的流量一定不会有重复计算。
（ \(\text T\) ）割的流量与流的流量：对于 \(G\) 上的任意一个割 \([S,T]\) 和任意一个可行流 \(f\) ，存在性质：\(|f|=f(S,T)\) 。
证明：
首先有 \(|f|=f(\{s\},V)\) 。
而 \(f(S,V)=f(\{s\},V)+f(S-\{s\},V)\) 。
注意到 \(S-\{s\}\) 里面的点都满足流量守恒，因此有 \(f(S-\{s\},V)=0\) 。
于是 \(|f|=f(S,V)\) 。
接着考虑 \(f(S,V)=f(S,S\cup T)=f(S,S)+f(S,T)=f(S,T)\) 。
因此 \(|f|=f(S,T)\) 。
可以发现我们的猜想中已经把证明口胡过一遍了。
结合定义 9 中提到的，有 \(|f|\le c(S,T)\) 。下面我们将要证明最大流最小割定理！
（ \(\text T\) ）最大流最小割定理 Maximum-flow-minimum-cut Theorem ：对于网络 \(G\) ， \(G\) 上的一个可行流 \(f\)，以下三个命题是等价的：
证明：
原文：https://www.cnblogs.com/crashed/p/14124220.html