最大流-最小割定理是网络信息流理论（Network infomation flow）的基石。这个定理我的理解就是“多粗的管子，水就最多多大流量”，比如从自来水厂到用水大户工业小区A 能达到的水的最大流量是多大？考虑到可能从水厂到小区有不少到达的水管，那么最大的流量等于拆掉最少最细的水管后水厂不能给小区A 供水的那些水管流量的集合。当然这种说法并不不严谨，因为这里水管不是双向的，而在网络中谈论的信息流却可是是双向的。下面详细介绍最大流—-最小割定理。

流网络图G = (V,E) 是有向图，其中

V 是所有节点（vertex）的集合；

E 是所有边（edge）的集合；

源点s 是信息的起始点

宿点t 是信息的到达点

其中(u,v)∈E 代表节点u，v 之间存在一条边，边容量由c(u,v) 表示（可以理解为网络带宽或者能达到的最大流量），如果(u,v)∉E ，那么c(u,v) = 0 。那么可以用有向图矩阵来表示图G：[C]_|V|×|V| C_i,j = c(i,j) 其中i,j ∈ V 。

f(u,v) 称为从u 点到v 点的流，c 进一步扩展为两个点之间的容量函数，如果u 和v 是相邻节点，那么c(u,v) 是两点之间的容量，这和前面的定义的一致的。流满足三个性质：

1. 容量约束：所有 u,v ∈ V ，要求 f(u,v) ≤ c(u,v)
2. 反对称性：所有 u,v ∈ V ，要求 f(u,v) = -f(v,u)
3. 流守恒性：对于所有 u ∈ V-{s，t}，要求 ∑ f(u,v) = 0

最大流问题实际上是在给出一个具有源点、宿点的流网络，找出从源点到宿点的最大值流。

残留网络（residual network），增广路径（augmenting path）和割（cut）是最大流—最小割定理的精髓，该定理用割来描述最大流问题。

f 是图G 中一个流，u，v 是其中的节点，在不超过容量c(u,v) 的条件下，节点u 和v 之间可以加入的额外网络流量就是u，v 的残留容量（residual capacity）。

节点还是原来图G 中的节点，只是边上的容量为残留容量：c_f(u,v) = c(u,v) -f(u,v)，那么由于流f ，可以得到一个残留网络G_f = (V,E_f)，其中 E_f  = {(u,v)∈V×V : c_f(u,v)>0}。残留网络本身也是一个流网络，其容量受c_f 限制（还是拿水管打比方，流f 好比从水厂到用水小区的一次通水，水管种剩余还可以流水的流量组成了残留网络）。

已知一个流网络G = (V,E) 和流f ，增广路径p 为残留网络G_f 中s 到t 的一条简单路径。称能够沿增广路径p 的每条边传输的网络流的最大量为p 的残留容量。其形式化定义为：

c_f(p) = min{c_f(u,v) : (u,v)在p 上}

根据增广路径可以定义在残留网络G_f 上的一个流f_p ，流量|f_p | 等于路径p 的残留容量c_f(p) > 0 。

f’ = f + f_p 也是G 的一个流，并且它比f 更接近最大值流。

Ford-Fullkerson 给出的方法就是不断增加流，直至找到最大流为止。一个流是最大流当且仅当它的残留网络不包含增广路径（那么源点在残留网络中不可达宿点）。

流网络中的割(S,T) 将节点集合V 划分为S 和T=V-S 两部分，割(S,T) 的容量定义为c(S,T) ，它等于从S 中所有节点直接连接到T 中所有节点边的容量和。一个网络中最小割即是网络的所有割中具有最小容量的割。流f 通过割(S,T) 的净流被定义为f(S,T) 。虽然通过割的流可能包括点之间的负网络流，但是，割的容量是非负的。也就是说，通过割(S,T) 的净流由正反双向网络流构成，即记上S→T 的正网络流，减去T→S 的正网络流。

f 是G 中的一个流，(S,T) 是G 中的一个割，那么通过割(S,T) 的净流为f(S,T) = |f|。因此，通过任意割的净流都是相同的，并且与流的值相同。对于一个流网络G 中任意流f 来说，其值的上限为G 的任意割的容量。显然网络的最大流一定不会超过该网络最小割的容量（计算割的净流是要算上反向流量的，但是如果是算容量就不用算。如下图 i/j 表示的是i：流量，j：容量，那么割的净流是19，容量是26）。

最大流—最小割定理  如果f 是具有源点s 和宿点t 的流网络G=(V,E) 中的一个流，则下列条件是等价的：

（1）f 是G 的一个最大流

（2）残留网络G_f 不包含增广路径

（3）对G 的某个割(S,T)，有|f| = c(S,T)

网络最大流的值等于某一个最小割的容量。