您的位置:首页  > 论文页面

基于关键边的网络图最大流问题研究

发表时间:2012-07-15  浏览量:1343  下载量:591
全部作者: 房茂燕,汪民乐,毕义明,郭慧
作者单位: 第二炮兵工程大学数学与军事运筹教研室;第二炮兵驻159厂军事代表室
摘 要: 提出了可去节点的概念,并给出最大流网络图的简化方法。定义了关键边,给出选择可行线路和关键边的方法,并将所有可行路的关键边构成一个集合,网络图的一个割集必定是此集合的子集,证明了所有关键边的容量之和便是网络的最大流。此方法与标记法相比,操作简单,易于计算机编程实现,具有很强的操作性和实用性。
关 键 词: 运筹学;最大流;关键边;网络图;容量
Title: Study on network maximum flow problem based on key lines
Author: FANG Maoyan, WANG Minle, BI Yiming, GUO Hui
Organization: Department of Mathematics and Military Operation, The Second Artillery Engineering University; The Second Artillery Military Representative Office in 159 Plants
Abstract: This paper presents the definition of past point and a method to simplify the network for reducing the calculation firstly, and the definition of key lines. It also presents the way how to select possible path. Every possible path has a key line. These lines are in a set, and one cutting-set is the set’s child. It’s proved that the sum of the key lines’ capacity is the network’s maximum flow. These methods are easier to operate and realize by computer program than others.
Key words: operational research; maximum flow; key lines; network map; capability
发表期数: 2012年7月第13期
引用格式: 房茂燕,汪民乐,毕义明,等. 基于关键边的网络图最大流问题研究[J]. 中国科技论文在线精品论文,2012,5(13):1242-1245.
 
0 评论数 0
暂无评论
友情链接