节点环流网络中的最大流算法  

Maximum flow algorithm in network with node loop

作　　者：徐光联[1] 孙文新[1] 

机构地区：[1]鹤壁职业技术学院电子信息工程学院,河南鹤壁458030

出　　处：《应用科技》2014年第1期48-53,共6页Applied Science and Technology

基　　金：河南省基础与前沿技术研究项目(122300410258)

摘　　要：为了求出节点有容量并有存储功能的网络中的最大流,提出使用改进的带有节点环流的网络模型。在改进的网络模型中,网络节点改由新的结构代替,即节点分为入点和出点,增加中转弧和节点环。提出了进出节点的配平算法,使用了改进的流量守恒约束,通过虚拟源、虚拟汇进行配平,使用最大流算法求出由节点环流调节过的最大流。在配平算法中,遇到入流容量小于出流容量,要判断节点环流量的大小;遇到入流容量大于出流容量,要判断节点环流的残容量大小。算法应用于流的分配或流的汇聚。In order to search maximum flow in the network with node capacity and node memory function, a network model with the node loop is proposed. The node of the network is substituted by the new structure of the node in the improved network, which is divided into enter-flow point and out-flow point, and added with the transfer arc and node loop. A balancing algorithm is proposed for entering and leaving the node and the improved flow conservation constraints are used;using the virtual source and virtual sink of balance, the maximum flow regulated by the node loop is calculated. In the balancing algorithm, when the enter-flow capacity is less than the out-flow capacity, the node ring flow size should be determined;otherwise, the residual capacity of the node loop should be determined. The algorithm is applied to the distribution or convergence of flow.

关 键 词：网络流 节点环流 最大流算法 流量守恒 

分 类 号：O157[理学—数学]