论文部分内容阅读
设G=（N,A,u）是一个顶点集为N,弧集为A,始点为s∈A,终点为t∈N,有限容量向量u={u<sub>ij</sub>:（i,j）∈A}及正整数K的网络。一个基本K-通道流是从始点到终点t∈N的发送K个单位流,使得在每个弧上的流是0或1。一个K-通道流是一个从s到t的流,使得这个流可以表示成基本K-通道流的非负线性组合的流。因此,K-通道流问题是求解从s到t不仅要满足顶点平衡（s和t除外）和弧的容量限制下通常的最大流问题,而且这个流必需满足沿着K条弧不交的s-t路发送。给出了另