网络最大流问题研究进展[1]

第!"卷第#期$""%年#月

计算机研究与发展

，6789!"*79#

3:9$""%;&’()*+,’-.’/0(12))232+).4+*55262,’0/2*1!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

网络最大流问题研究进展

张宪超陈国良万颖瑜

（国家高性能计算中心（合肥）合肥$）%""$>

（中国科学技术大学计算机科学与技术系合肥$）%""$>（）ABCDEF"@="!HIFE9B7J9BFG

摘

要

网络最大流问题和它的对偶问题———最小截问题，是一对经典组合优化问题，它们在许多工程领域和科学领域

近年来，随着各种网络的飞有重要的应用，是计算机科学和运筹学重要的内容9最大流问题已经有!"多年的研究历史，速发展，最大流问题的研究也取得了很大的进展并对下一步研究趋势进行了预测9对最大流问题研究做了详细的总结，9关键词

组合优化；线性规划；网络优化；最大流；最小截

；中图法分类号10%"=9K10%#%

!"#"$%&’()*’"+$,-./.0"*1(%234(15%(64".

，，L4+*?MIEF<.DE7.42*?N7<,IEFEFOP+*QIF<QNGG

（!（(），）"#$%&"’($*+,-%-/"&0,1%/3#$&,&#,-,,$(,,$$%""$>).2)1..（4）,"-#/,&#%%/3#,-50$,&0,"&67,0*&%’%9&$:,-;$#%0$,&0,"&67,0*&%’%%*$&"，(,,$$%""$>2.12)8，8.5)8.1.

76#*%$&*1D:JEAIJNJR87S;T7U8:JEFOIVHONE8T7U8:J—VD:JIFIJNJBNVT7U8:JET:EEIT7RB8EHHI<;;;

，BE8B7JUIFEV7TIE87VIJICEVI7F;T7U8:JHSDIBDETIH:IFJEFFIF::TIFFOHBI:FVIRIBE8IBEVI7FH91D:;W:GGE;;WET:IJ7TVEFVETVH7RB7JNV:THBI:FB:EFO7:TEVI7FE8T:H:ETBD91D:T:H:ETBD7FVD:JEAIJNJR87S;T7U<;;;;

，，SIVDVD:TEIOO:X:87J:FV7RXETI7NHF:VS7TYHVD:T:<8:JDEHEDIHV7T7RJ7T:VDEF!"W:ETH9):B:FV8;;WWH:ETBD7FVD:JEAIJNJR87S;T7U8:JDEHJEO:T:JETYEU8:EBDI:X:J:FVH95:VEI8:OHNJJETICEVI7F7RVD:T:<

，H:ETBD7FVD:;T7U8:JIHJEO:EFOVD:T:H:ETBDOIT:BVI7FHET:R7T:BEHV:O9；；；8"(%:#B7JUIFEV7TIE87VIJICEVI7F8IF:ETT7TEJJIFF:VS7TY7VIJICEVI7FJEAIJNJR87S；JIF<;;GG;91IJNJBNV

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

外，最大流问题在许多工程领域和物理、化学、生物以及管理科学和应用数学等科学领域有着广泛的应

在实际的网络中，网络的结点和边都是有容量限制的9很多情况下我们需要知道在一个有容量限

制的网络中两个指定结点（分别称为源和汇）之间最多能传输多少流量，并确定达到这个最大流量的传（简称最大流问题）就是描输策略9网络最大流问题述这个问题的数学模型9

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

收稿日期：；修回日期：$""$<"!<=#$""%<"=<$>基金项目：国家“九七三”重点基础研究发展规划项目（?）万方数据=##@"%"!"%

［］=用最大流问题是计算机科学和运筹学的9因此，

;引

言

重要研究内容9

［］

最大流问题已有!"多年的研究历史$9在这人们建立了最大流问题较为完善的理!"多年中，论，同时开发了大量的算法随着各种网络9近年来，和计算机科学的飞速发展，最大流问题得到了更深入的研究9历年来重要的国际理论计算机科学会议如31’.，3+.等都有最大流问题最新研究成果的