最小费用最大流问题的相关定义

Question

如题所述

Answer 1

在网络D(V,A) 中,如果对连接发点vs和收点vt 的一条链P，方向规定为从vs 到vt，则当链P 中弧(vi,vj)
的方向与规定的方向一致时，称弧（vi,vj) 为前向弧，否则称为后向弧。不在这条链上的弧，不定义前向弧和后向弧。 设{fij}为一可行流（假设为非负值），如果存在从发点vs 到收点vt 的链P，在链P 上，下列两条同时满足，则称P 为可扩充链：
①对于P 上的前向弧（vi,vj) 有fij<cij。
②对于P 上的后向弧（vi,vj) 有fij>0。 设对于可行流f 存在可扩充链P，当以ε=1 调整f 而得到可行流f' 时，两流的费用之差成为可扩充链p 的费用。其中P+和P- 分别表示p 上的前向弧和后向弧。