Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (33): 13-15.DOI: 10.3778/j.issn.1002-8331.2009.33.005
• 博士论坛 • Previous Articles Next Articles
SHE Xiang-yang
Received:
Revised:
Online:
Published:
Contact:
厍向阳
通讯作者:
Abstract: Facing the question of max-flow in network,based on cut set define and max-flow min-cut theorem,with adjacency matrix to deposit network data,using the data structure of stack to organise network data,traversing all cut sets,the minimum capacity in all cut sets is max-flow in network.The other branches,besides the branches of the minimum cut set,are calculated by solving the node flow balance equation in network.The algorithm pioneers a new way to solve the question of max-flow in network,and breaks the localization of cut set define and max-flow min-cut theorem that have only theory value,do not solve practic max-flow in network.The key branches in network that decide max-flow in network are made easily by the way of the minimum cut set.The direct technology support for enlarging max-flow in network is provided by the algorithm.Algorithm testing shows:The new max-flow algorithm in network based on stack is completely feasible and available.
Key words: max-flow in network, cut set, stack, max-flow min-cut theorem
摘要: 针对网络最大流问题,在割集定义和最大流-最小割定理基础上,以邻接矩阵为网络数据存储结构,利用栈作为数据组织形式,遍历网络中所有割集,最小容量的割集即为网络最大流。流量网络其余分支流量由网络结点流量平衡条件来求解。该算法具有:开辟了一种求解流量网络最大流的新的方法,克服了割集和最大流-最小割定理仅仅具有理论价值、没有实用价值的局限性;根据最小容量的割集可以方便确定决定网络最大流的关键分支,为扩展网络流量提供直接技术支持。算法测试表明:基于栈的网络最大流算法是完全可行和有效的。
关键词: 网络最大流, 割集, 栈, 最小容量割集
CLC Number:
TP393.3
SHE Xiang-yang. New max-flow algorithm in network based on stack[J]. Computer Engineering and Applications, 2009, 45(33): 13-15.
厍向阳. 基于栈的网络最大流算法[J]. 计算机工程与应用, 2009, 45(33): 13-15.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.2009.33.005
http://cea.ceaj.org/EN/Y2009/V45/I33/13