基于层次网络的最大流求解方法  

A Simple Algorithm of Maximum Flow Basing on Layer Network

作　　者：徐翠霞[1] 

机构地区：[1]潍坊学院,山东潍坊261061

出　　处：《潍坊学院学报》2010年第4期42-45,共4页Journal of Weifang University

基　　金：潍坊市2009年科学技术发展计划(200901129)

摘　　要：针对最大流问题的研究现状,提出了分层求解最大流的简单方法,并给出了该方法可行的严格证明。该方法首先求得层次网络的阻塞流,进而最终求得一个最大流。另外,该方法还针对有向流网络的特点,将算法中涉及的流网络、剩余网络和层次网络共用一个网络结构,既有效地降低了算法的空间复杂度,还大大提高了算法的执行效率。In order to solve the problem of maximum flows,a new feasibility approach was proposed according to the present research situation.This method used to find block flows in layer networks,and then finally find a maximum flow.It is proved that the method is efficient and feasible.It can help teaching improvement and practice application.It is also worth popularization.

关 键 词：剩余网络 层次网络 饱和弧 最大流 阻塞流 

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