网络流基础知识

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

几个基本概念&＃xff1a;

　　1)、残留网络&＃xff1a;一个流网络图G &＃61; &＃xff08;V&＃xff0c; E&＃xff09;中&＃xff0c;在不超过容量c(u, v)的条件下&＃xff0c;从节点u到v之间可以再压入的额外的网络流量就是&＃xff08;u&＃xff0c;v&＃xff09;的残留容量。

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

由这些残留容量最后构成的新的流网络G‘ &＃61; &＃xff08;V&＃xff0c; E&＃xff09;就是残留网络。

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

如图b) 就是残留网络:

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

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

　　4)、最大流最小割定理&＃xff1a;

If f is a flow in a flow network G &＃61; (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| &＃61; c(S, T) for some cut (S, T) of G.