论文部分内容阅读
对于经典网络最小截问题,所有弧权数非负,可运用最大流算法求解。但是对于广义最小截问题,若某些弧权数为负,则运用算法难以求解。针对含负权弧网络最小截问题,通过与经典最小截问题的对比,提出简单截集和复合截集概念,并给出广义网络最小截概念——截量最小的简单截集;引入负容量和负流量,给出求解含负权弧网络最小截问题的原理,并设计求解含负权网络最小截问题的网络流算法;最后,通过应用举例对算法进行演示。