最大流问题------Ford-Fulkerson算法（增广路径）

留言

Ford-Fulkerson算法（增广路算法）

增广路定理：设容量网络 G(V, E) 的一个可行流为 f, f 为最大流的充要条件是在容量网络中不存在增广路。

从任何的一个可行流开始，寻找增广路对网络进行增广，直到网络中不存在增广路径。

怎么证明当无法再寻找到增广路径时，就证明当前网络是最大流网络呢？

最大流最小割定理：网络的最大流等于最小割。

证明：

  1. 任意一个流 <= 任意一个割

    自来水厂通水，水流从自来水厂到家，形成一个流。

    当小偷偷走其中的几个管道，相当于形成一个割。

    这时，几个管道的缺失部分都会有水流出来，流出的水的和 == 原来的流。

    几个管道的容量加起来就是割

    那么流必定小于割

  2. 当一个流 == 一个割 ，就构造出和最大流的割

    达到最大流时，必定没有增广路，即残留网络中源汇点之间没有通路。

    （ 源点能到的点 ） -> （ 源点到不了的点 ） 的边必定会满流，否则就能增广。

    这些中间的满流边之和就是最大流

    把这些满流边作为割。

  3. 最大流等于最小割

    假设残留网络Gf不存在增广路，所以在残留网络中不存在从源点到汇点的路。

    S集合 = 残留网络中源点能够到达的点。

    T集合 = 残留网络中源点不能够到达的点

    (S,T)构成割(S,T)

    f(u,v)=c(u,v)。即满流边。

    f(u,v)<c(u,v)时，源汇点之间有连通路，与v属于T矛盾。

所以当找不到增广路时，此时f一定是最大流。