网络流基础知识

　　前段时间看了一点网络流，可惜每写总结。也每复习，所以今天拿过来再看照样抓瞎。。。这里好好谢谢总结。

几个基本概念：

　　1)、残留网络：一个流网络图G = （V， E）中，在不超过容量c(u, v)的条件下，从节点u到v之间可以再压入的额外的网络流量就是（u，v）的残留容量。

c_f(u,v) = c(u, v) - f(u, v);　　(其中f(u, v)为u到v之间可以再压入的额外流量)

由这些残留容量最后构成的新的流网络G‘ = （V， E）就是残留网络。

说白了就是已经压入一些流量，消耗掉c(u, v)的一部分容量，然后剩下的容量构成的图就是残留网络。

如图b) 就是残留网络:

　　2)、增广路径：已知一个网络G = (V, E)和流f，增广路径p为残留网络G‘种从s 到 t 的一条简单路径。在不违反边的容量限制的条件下，增广路径上的每条边(u, v)可以容纳从u到v的某额外正网络流。上图中用黑线标出的路径p就是一条增广路径。

　　3)、网络流的割：流网络G = (V, E)的割（S， T）径V划分为S 和T = V - S两个部分。使得s ∈ S， t ∈ T。如果f是一个流，则穿过割(S, T)的净流被定义为f(S, T)。割（S, T）的容量为c（S， T）。一个网络流的最小割也是所有割种具有最小容量的割。

　　

　　4)、最大流最小割定理：

If f is a flow in a flow network G = (V, E) with source s and sink t, then the following conditions are equivalent:

1. f is a maximum flow in G.

2. The residual network G_f contains no augmenting paths.

3. |f| = c(S, T) for some cut (S, T) of G.