如图6－76（a）所示：C（u，v）＝6，f（u，v）＝4，W（u，v）＝3.我们来考虑流量在边（u，v）上的增减情况.

图6－76

边e＝（u，v）至多可以再多输送C（e）－f（e）＝6－4个单位流量，至多可以少输送f（e）＝4个单位流量.此时，若自顶点u至顶点v沿边（u，v）减少一个单位的流量，则可以理解为：在从顶点u沿边（u，v）输送4个单位流量到顶点v的同时，有1个单位流量自顶点v沿一条虚设边（v，u）（以后用弧边来表示这类虚设的有向边）输送到顶点u.故有向边（u，v）上流量目前所能增减的情况如图6－76（b）所示：沿（u，v）至多能增送2个单位流量，沿（v，u）至多能增送4个单位流量.在图6－76（b）中，我们令

显然，在图6－76（b）中，沿边（u，v）运送一个单位流量，相当于在图6－76（a）沿边（u，v）增送一个单位流量，因而，要增加代价W（u，v）＝3；在图6－76（b）中，沿边（v，u）运送一个单位流量，相当于在图6－76（a）沿边（u，v）减送一个单位流量，因而要减少代价W（u，v），在图6－76（b）中，我们令

我们称中的边为正规边，E－f中的边为非正规边.

例6－38　对下列网络N及其上流f分别作伴随f的增流网络Nf.

（1）网络N1如图6－77所示；

（2）网络N2如图6－78所示（边旁参数为C（e），f（e），W（e））.

图6－77

图6－78

解　网络N1的伴随f的增流网络如图6－79所示，网络N2的伴随f的增流网络如图6－80所示.

图6－79

(www.daowen.com)

图6－80

由此可知，若f为N上流，Valf＝λ，且Nf中存在一个W′（Q）＜0的负回路，则f一定不是流值为λ的最小代价流.

我们有如下定理

定理6－9　设f为网络N上流，Valf＝λ，则

（1）f为N中流值为λ的最小代价流的充分必要条件为：在Nf中不存在负回路.

（2）如果f为N中流值为λ的最小代价流，P为Nf中一条从x到y的最短路径，δ为任一不超过C′（P）的正整数，则f关于P，δ的修改流为N中流值为λ＋δ的最小代价流.

（3）f为N中最大流的充分必要条件为：Nf中不含一条从源x至汇y的路径.

例如，网络N2图6－80的伴随f的增流网络图6－80中无负回路，所以，根据定理6－9（1），图6－80中的流f是流值为5的最小代价流.

例6－39　求网络N2图6－78中流值λ为6的最小代价流.

解　我们已经知道，图6－78中流f是流值为5的最小代价流.

图6－81

在Nf图6－80中，最短路径为

取δ＝min｛C′（P），λ－Valf｝＝min｛2，6－5｝＝1.

f关于P，δ的修改流如图6－81所示.为流值为6的最小代价流.