网络流的预流算法.pdf

《网络流的预流算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中国料孽敢求犬誊硕士学位论网络流的预流算法作者姓名：学科专业：导师姓名：完成时间：贾友应用数学徐俊明教授二。一二年五月又UniversityofScienceandTechnologyofChinaAdissertationformaster’SdegreePreflowAlgorithmToTheMax—．flowProblemAuthor’SName：YouJiaSpeciality：AppliedMathematicsSupervisor：Prof．JunmingXuFinishedTime：May．2012中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本

2、人在导师指导下进行研究工作所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名：j吻趸签字日期：矽9，)-3中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和

3、纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。／叼公开作者签名：口保密——年嚷石．导师签名：签字日期：3堂!兰皇13＼签字日期：力啦：￡：丝多目录目录⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．ABSTRACT⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯第1章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．1．1研究背景和意义．⋯⋯．⋯．⋯．⋯．⋯．⋯．⋯⋯⋯⋯．⋯．1．1．1研究背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．1．1．2研究意义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．1．1．3本文的结构安排⋯⋯．⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯⋯第2章相关知识简

4、介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．2．1网络流相关简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2．1．1网络流概述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2．2FordandFulkerson算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2．3Dinic算法(最短增广路算法)⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．第3章压入重标记最大流算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．3．1预流算法简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．3．1．1预流算法简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．3．2压入重标记算法的实施⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯3．2．1压入重标记算法的实施⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．第4章总结与展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯4．1总结．．

5、．．．．⋯．⋯．⋯．．．．．．．．．⋯．．．．⋯⋯．．．．．．．．．⋯．．．．4．2展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．IⅢv1235BB""俎殂殂拐巧原书空白页不缺内容摘要网络流算法问题是图论中经典的算法问题o’多数的经典算法用寻找增广路方法，其中Ford和Fulkerson的算法和Dinic的算法都是比较经典的。而Karzanov提出来的预流的概念对于问题的理解更加的简单，产生了一些更高效的算法。我们在本文中在主要的结果和方法上引用Karzanov，Goldberg，Tarj

6、an的证明方法和结论，在一些小的证明上和以上的证明方法稍有不同，并和经典的算法进行对比。我们对于压入重标记最大流算法这一算法进行了较为详细的讨论，在预流这一概念下，我们可以得到结论最大距离压入重标记最大流算法能够在0(他3)时间内实施。关键词：算法，最大流问题，预流，1II原书空白页不缺内容ABSTRACTNetworkfloWalgori啦misaclassicalalgorithmproblem．Someknownefticlen—tm强mmm-日owalgorithmslikeFordandFulkersonalgorithmandtheapproacnofDinicar

7、eauwor幽gbyfindingaugmentingpaths．AnalternativemethodbasedonthepreflowconceptofKarzanovisintroducedtOmaketheproblemmoreeaslertountier—stand．WeusethemainconclusionandmethodofKarzanov，Goldberg，’I确an’spaper’andhavesomechangeinsomesmallpartofprove．Wecom