网络最大流

第40卷第9期

2003年9月

计算机研究与发展

J

OURNALOFCOMPUTERRESEARCHANDDEVELOPMENT

Vol140,No19Sep12003

网络最大流问题研究进展

张宪超　陈国良　万颖瑜

(国家高性能计算中心(合肥)　合肥　230027)

(中国科学技术大学计算机科学与技术系　合肥　230027)(xczhang0810@sina1com1cn)

摘　要　网络最大流问题和它的对偶问题———最小截问题,,有重要的应用,是计算机科学和运筹学重要的内容140,,速发展,最大流问题的研究也取得了很大的进展11关键词　组合优化;线性规划;网络优化;;中图法分类号　TP3016ResearchNetworkFlowProblem

ZHANGXian2Chao,CHENGuo2Liang,andWANYing2Yu

(NationalHighPerformanceComputingCenter(Hefei),Hefei230027)

(DepartmentofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei230027)

Abstract　Themaximumflowproblemanditsdualproblem—theminimumcutproblemareapairofclassi2calcombinatorialoptimizationproblems,whichariseinmanyengineeringandscientificapplications1Theyareimportantpartsofcomputerscienceandoperationalresearch1Theresearchonthemaximumflowprob2lemhasahistoryofmorethan40years1Recently,withtherapiddevelopmentofvariousnetworks,there2searchonthemaximumflowproblemhasmaderemarkableachievements1Detailedsummarizationofthere2searchontheproblemismade,andtheresearchdirectionsareforecasted1

Keywords　combinatorialoptimization;linearprogramming;networkoptimization;maximumflow;min2imumcut

1　引　　言

在实际的网络中,网络的结点和边都是有容量限制的1很多情况下我们需要知道在一个有容量限制的网络中两个指定结点(分别称为源和汇)之间最多能传输多少流量,并确定达到这个最大流量的传输策略1网络最大流问题(简称最大流问题)就是描述这个问题的数学模型1

最大流问题是网络流理论的重要组成部分,它是一个经典的组合优化问题,同时也可以看做是特

　收稿日期:2002204219;修回日期:2003201227

　基金项目:国家“九七三”重点基础研究发展规划项目(G1998030403)

殊的线性规划问题1除了解决实际网络中的问题以

外,最大流问题在许多工程领域和物理、化学、生物以及管理科学和应用数学等科学领域有着广泛的应用[1]1因此,最大流问题是计算机科学和运筹学的重要研究内容1

最大流问题已有40多年的研究历史[2]1在这40多年中,人们建立了最大流问题较为完善的理

论,同时开发了大量的算法1近年来,随着各种网络和计算机科学的飞速发展,最大流问题得到了更深入的研究1历年来重要的国际理论计算机科学会议如STOC,SAC等都有最大流问题最新研究成果的