资源描述：
《网络最大流问题算法研究【毕业论文】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、本科毕业论文（20届）网络最大流问题算法研究专业：数学与应用数学19摘要网络最大流问题是一个应用极为广泛的问题,在交通运输系统和金融系统中都有广泛应用,网络最大流是计算机科学和运筹学的重要内容.20世纪50年代,由福特(Ford)、富克逊（Fulkerson）建立的“网络流理论”成为网络应用的重要组成部分.最近几十年来关于网络最大流方面的研究有很大进展,研究成果也是层出不穷,本文基于以往学者的研究成果上对网络最大流问题进行了分析与总结,并给出了网络最大流算法中标号算法的求解过程,也涉及在实际生活中的应用.最后介
2、绍了现在流行的一些最大流主要算法和实例.关键词:网络最大流;标号;增广链;算法19Networkmaximal-flowproblemresearchAbstractNetworkmaximumflowproblemisawiderangeofapplicationsproblem.Itiswidelyusedintransportationsystemsandfinancialsystems,thenetworkmaximumflowisanimportantcomputerscienceandoperati
3、onsresearchcontent.The"NetworkFlowTheory",establishedbyFordandFulkersonin1950hasbecomeanimportantpartofnetworkapplications.Inrecentdecadesthemaximumflowonthenetworkofresearchhasmadegreatprogress,theachievementsarefruitful,thisdissertationisbasedontheprevious
4、studiesaboutthemaximumflowproblemonnetworkanalysisandsummary,anditgivesthesolvingprocessoflabelingalgorithmonnetworkmaximumflow,italsoinvolvestheapplicationinreallife.Finally,weintroducesomeofthemainalgorithmswhicharepopularandgivesomeexamples.Keywords:Maxim
5、umnetworkflow;Labelingalgorithm;AugmentedchainAlgorithm19目录摘要IABSTRACTII1前言……………12理论基础……………………………………………………………………………...………..32.1相关定义32.2最大流最小割定理53标号算法73.1标号过程73.2调整过程73.3标号算法的matlab实现……………………………………………………………...83.4标号法应用举例…………………………………………………………………….....94网络最大流其
6、他算法简要介绍…………………………………………………….........155小结…………………………………………………………………………………………...19参考文献20致谢21191前言网络最大流应用非常广泛,在交通运输网络中有人流、车流、货物流,供水网络中有水流,金融系统中有现金流,通讯网络中有信息流等.还用于求电力传输问题、供销通路问题中的最大流.最大流问题已经有几十年的研究历史,在这几十年中,人们建立了最大流问题比较完善的理论,从Ford和Fulkerson提出第一个最大流算法到现在,很多学者都对其进
7、行了改进并提出了很多新的算法,同时开发出了大量优秀的算法,如Ford和Fulkerson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法以及Goldberg和Rao的二分长度阻塞流算法等等,这些经典算法及其中用到的相关技术对网络最大流问题的研究和发展起到了非常重要的推动作用.近年来,随着网络和计算机科学的飞速发展,最大流问题得到了更深的研究.多年来,尽管在众多学者的共同努力下最大流问题的研究取得了极大的进展,但是关于最大流问题的研究还远远没有结束.首先,在理论算法研究方面,还没有发现最大流问题
8、算法时间复杂度的精确下界,更没有任何一种通用算法达到或接近问题的下界;其次,在算法的实际性能方面,目前算法的实际性能也不能满足很多应用问题的需求.最大流算法的研究过程中最早是Dantzig提出的网络单纯形法和Ford和Fulkerson的增载轨算法,他们都是伪多项式算法.20世纪70年代出现了多项式时间算法,分别由Dinic、Edmonds和Karp等提出.从最大流问题的提出到现在的发
