求解含负权弧的网络最小截问题  

Solving minimal cut problem of network with negative weight arcs

作　　者：苏志雄[1] 魏汉英[1] SU Zhixiong;WEI Hanying(School of Business Administration,Nanchang Institute of Technology,Nanchang 330099,Chin)

机构地区：[1]南昌工程学院工商管理学院,江西南昌330099

出　　处：《南昌工程学院学报》2017年第6期13-18,共6页Journal of Nanchang Institute of Technology

基　　金：江西省教育厅科技项目(GJJ161114)

摘　　要：对于经典网络最小截问题,所有弧权数非负,可运用最大流算法求解。但是对于广义最小截问题,若某些弧权数为负,则运用算法难以求解。针对含负权弧网络最小截问题,通过与经典最小截问题的对比,提出简单截集和复合截集概念,并给出广义网络最小截概念——截量最小的简单截集;引入负容量和负流量,给出求解含负权弧网络最小截问题的原理,并设计求解含负权网络最小截问题的网络流算法;最后,通过应用举例对算法进行演示。Classic minimal network cut problem could be solved by using maximal network flow algorithm since weights of arcs in network are all non-negative. But for generalized minimal network cut problem,if weights of some arcs in network are negative,the problem cannot be solved by using existing network flow algorithm. Aiming at the minimal cut problem of net-work with negative weight arcs,the nature of the problem was analyzed,and by comparing with classic minimal network cut problem, concepts of simple cut and complex cut were proposed, and generalized minimal network cut was defined as simple cut with minimal capacity. The classic network flow problem was extended by introducing concepts of negative capacity and negative flow mainly, and then principles of solving the minimal cut problem of network with negative weight arcs were pro-posed. Based on these principles, one network flow algorithm was designed to solve the minimal cut problem of network with negative weight arcs, and correctness of the algorithm was proved. Finally, the algorithm was illustrated with application ex-ample.

关 键 词：运筹学 最小截 网络流算法 含负权弧的网络 

分 类 号：O221[理学—运筹学与控制论]