级连层次图的网络最大流算法研究  

Research on network maximum flows algorithm of cascade level graph

作　　者：潘荷新[1] 伊崇信[2] 李满[2] 

机构地区：[1]常州纺织服装职业技术学院信息技术系,江苏常州213164 [2]山东华宇职业技术学院计算机系,山东德州253034

出　　处：《计算机工程与应用》2011年第19期78-81,135,共5页Computer Engineering and Applications

摘　　要：给出一种通过构造网络级连层次图的方法,来间接求出最大网络流的算法。对于给定的有n个顶点,e条边的网络N=(G,s,t,C),该算法可在O(n2)时间内快速求出流经网络N的最大网络流及达最大流时的网络流。This paper gives an algoritm that structures a network cascade level graph to find out maximum flow of the network indirectly.For the given network N=（G,s,t,C） that has n vetexes and e arcs,this algorithm finds out the maximum value of the network flow fast in O（n2） time that flows from the network N and the network flows when the value of the one reach maximum.

关 键 词：网络 级连层次图 最大流 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]