建模
寻求最大流问题的方法： 寻求最大流问题的方法： 先任一假设网络的一个流， 然后由此出发， 设法逐渐增大流值。 这里假定弧的容量为正整数 (若弧的容量为有理数， 则可化为整数 后再进行) 。 令 uij f ij , 当(i, j )为前向弧 ， δ ij = 当(i, j )为后向弧 f ij , δ = min{δ ij } 则在这条可增广轨上每条前向弧的流都可以增加一个量 δ , 而 相应的后向弧的流可减少 δ ,这样就可使得网络的流量获得增加， 同时可以使每条弧的流量不超过它的容量， 而且保持为正， 也不影 响其它弧的流量。总之，网络中 f 可增广链的存在是有意义的， 因为这意味着 f 不是最大流。