广义网络中流广义圈判断的算法  

Algorithm for Determining Existence of Flow-generating Cycle

作　　者：董丽薇[1] 

机构地区：[1]沈阳师范大学科信软件学院,辽宁沈阳110034

出　　处：《沈阳师范大学学报（自然科学版）》2008年第3期257-259,共3页Journal of Shenyang Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(10471096)

摘　　要：前人对广义网络流问题的研究都会讨论有流广义圈的网络和没有流广义圈的网络2种情况,但对于如何判断网络中是否有流广义圈都没做提及,针对这一问题,根据寻找图中平均权和最小圈的算法给出了判断流广义圈的算法,并对算法的正确性和时间复杂性给出证明.Because expert did not refer to how to determine whether there is flow-generating cycle in generalized network, this thesis presents the algorithm for determining whether there is a flow-generating cycle independendy based on searching minimum mean cycle, and prove the accuracy and complexity of the algorithm.

关 键 词：广义网络 流广义圈 时间复杂性 

分 类 号：O221.7[理学—运筹学与控制论] O157.5[理学—数学]