-----备忘------
转于:http://www.cnblogs.com/kuangbin/archive/2011/07/26/2117636.html
图-1
如图-1所示,在这个运输网络中,源点S和汇点T分别是1,7,各边的容量为C(u,v)。图中红色虚线所示就是一个可行流。标准图示法如图-2所示:
其中p(u,v) / c(u,v)分别表示该边的实际流量与最大容量。
关于最大流:
熟悉了什么是网络流,最大流也就很好理解了。就是对于任意的u∈V-{s},使得p(s,u)的和达到最大。
上面的运输网络中,最大流如图-3所示:
MaxFlow=p(1,2)+p(1,3)=2+1=3。
在介绍最大流问题之前,先介绍几个概念:残余网络,增广路径,反向弧,最大流定理以及求最大流的Ford-Fulkerson方法。
残余网络 增广路径 反向弧
观察下图-4,这种状态下它的残余网络如图-5所示:
也许现在你已经知道什么是残余网络了,对于已经找到一条从S 到T的路径的网络中,只要在这条路径上,把C(u,v)的值更新为C(u,v)-P(u,v),并且添加反向弧C(v,u)。对应的增广路径Path为残留网络上从S到T的一条简单路径。图-4中1,2,4,7就是一条增广路径,当然还有1,3,4,7。
此外在未做任何操作之前,原始的有向图也是一个残余网络,它仅仅是未做任何更新而已。
最大流定理:
如果残留网络上找不到增广路径,则当前流为最大流;反之,如果当前流不为最大流,则一定有增广路径。