在我们分析Ford-Fulkerson算法的过程中, 产生了许多自然的结果, 现在展示另一个重要的结果, 通过算法, 我们总可以获得一个整数值的流, 接着我们 以最大流结束.
因此有: 如果流网络中所有的负载能力都是整数, 因此存在一个最大的流, 并且每个f(e)都是整数.
注意到, 以上没有声明每个最大流都是整数值, 只是部分最大流拥有这个性质,
实数作为负载:
最后, 在进一步分析之前, 我们可以考虑一些关于所有负载都是整数值的假设的关键性.
首先, 允许实数负载, 不会使情况更一般化, 因为我们可以决定负载的最小公约数, 从而转化为整数问题.
但是, 如果我们有实数负载, 将会怎样? 在证明中, 那些部分基于整数值? 事实上, 整数值假设是很关键的,: 我们证明了流值每步至少增加一个单位. 在实数负载中, 我们必须考虑, 我们的流值一值在增加, 但是增加可以任意小,; 因此不能保证迭代次数有限. 在增强路径的选择, 一个有实值的Ford-Fulkerson 算法可能会永远运行下去.
然而, 我们仍能证明最大, 最小原理成立. 因为仅仅假设没有s-t的路径存在, 目的在于证明存在同样值的分割存在. 很明显, 对于任意的最大值流f, Gf中都没有s-t路径,; 否则存则增加流值的路径, 因此证明仅需要, 每个流网络存在最大值流.
当然, 网络流的实际应用中, 负载肯定是整数, 或者有理数,. 然而. 错误的选择, 对于增强路径来讲, 即使是整数负载也会显式出他本身.: 他可能导致算法过多的迭代.
作者：liyonghelpme 发表于2010/6/20 14:19:00 原文链接
阅读：140 评论：0 查看评论