山东科技大学本科毕业设计（论文）
第五章 结论
本课题主要以图论的知识为理论基础，来讨论最大流问题。最大流问题是一类应用极为广泛的问题，20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。
最大流问题的核心依据是Ford-Fulkerson最大流最小割定理，在这个定理的基础上，解决最大流问题的几种算法有Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法等本论文分别介绍了这几种算法，并举实例说明各个算法具体的解题过程，各算法的优劣各不相同，
Ford-Fulkerson标号法是最原始的算法，由Ford和Fulkerson提出，Edmonds和Karp针对该算法增广路径选取的任意性这一缺点对它做了修正算法产生了Edmonds-Karp修正算法，而Dinic算法则兼取前两种算法的优点，是这三种算法中最有效的算法。
最大流问题是网络流问题的一个重要的内容，研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。
在很多情况下，实际遇到的问题可能是很复杂的，甚至是无从下手，不过通过分析建立模型，如果可以建立成一个网络图，转化成为最大流问题，就会找到相应的解决方法。由此，最大流问题在现实生活中是非常重要的。
30
山东科技大学本科毕业设计（论文）
参 考 文 献
[1] 熊义杰．运筹学教程．天津：国防工业出版社，2004
[2] 徐俊明. 图论及其应用. 合肥：中国科学技术大学出版社，2005 [3] 卢开澄. 图论及其应用. 北京：清华大学出版社，1984 [4] 吴育华，杜纲．管理科学基础．天津：天津大学出版社，2001 [5] 谢政，李建平. 网络算法与复杂性理论. 北京：国防科技大学出版社，1995
[6] 刁在筠，郑汉鼎，刘家壮，刘桂真. 运筹学. 第2版. 北京：高等教育出版社，2001
[7] 田丰，马仲蕃. 图与网络流理论. 北京：科学出版社，1987 [8] 卜月华，吴建专. 图论及其应用. 南京：东南大学出版社， 2000 [9] Bondy JA, Mutry USR. Graph Theory with Applications. London and Basingstoke: MacMillan Press, 1976
[10] 王树禾. 图论及其算法. 合肥：中国科学技术大学出版社，1990 [11] 戴一奇. 图论及其应用. 北京：水利电力出版社，1988 [12] 展丙军．运筹学．哈尔滨：哈尔滨地图出版社，2005
[13] 《运筹学》教材编写组. 运筹学. 第3版. 北京: 清华大学出版社，2004 [14] 胡运权．运筹学教程．北京：清华大学出版社，2007 [15] 谢金星，邢文顺. 网络优化. 北京：清华大学出版社，2000 [16] 李向东. 运筹学：管理科学基础. 北京：北京理工大学出版社，1990 [17] 李建中, 骆吉洲(译). 图论导引. 北京：机械工业出版社，2006 [18] 王朝瑞. 图论. 北京：北京工业学院出版社，1987
31
山东科技大学本科毕业设计（论文）
致谢辞
本科毕业论文即将完成，回顾我大学四年的学习生涯，我得到了众多老师的教诲，同学的支持和帮助，再次对他们表示中心的感谢。
首先感谢我的导师王朝阳老师，他生活中待人十分热情诚恳，给予我无微不至的关怀和照顾；工作中他治学严谨，思维活跃，在研究课题阅读文献、论文写作上给予我许多指导和帮助，使我对数学的认识有了很大的提高，我将铭记恩师的教诲、关心和帮助。
还要感谢大学四年来所有的老师，为我们打下坚实的数学专业知识基础，在论文的写作过程中，还要感谢班内同学的帮助，他们在我完成论文的过程中，给我提了许多宝贵的建议，正是因为有了你们的支持和鼓励。此次毕业设计才能够顺利的完成。
感谢所有给予我帮助和锻炼的人。
最后，衷心感谢所有老师对我的栽培、支持和鼓励，感谢所有朋友的关心和帮助。向在百忙中抽出时间对此论文进行评审并提出宝贵意见的各位专家表示衷心地感谢！
衷心祝愿母校山东科技大学明天更加美好！
32
山东科技大学本科毕业设计（论文）
附录1英文原文
Maximum flow problem in the introduction, we listed one of the largest flow of goods delivery. If this issue also includes the known conditions of delivery of each unit while the cost of goods, then how to transport, to get the most traffic, and transportation costs to a minimum? This is the so-called maximum flow problem minimum cost. The maximum flow based on the definition, if each side of a first-priority claim to the number of c(e)(that the edge capacity) but also have another weights w(e) (that the unit cost flow), and has been seeking a maximum flow of the network value of F, then the minimum cost maximum flow problem, it is clear the following linear programming model can be used to describe:
min?w(e)f(e) e?E
Satisfy 0?f(e)?c(e) for all e?E
f?(v)?f?(v)
for all v?V f?(x)?F(maximum flow constraints)(Orf?(y)?F) Algorithm ideas Solve the minimum cost maximum flow problem, there are two general ways. Way is to use a maximum flow algorithm to calculate the maximum flow, and then based on the cost side, check whether it is possible to balance the flow by adjusting the flow side, so that to reduce the total cost? As long as there is a possibility, on such adjustments. After adjusting for a new maximum flow. Then, on the basis of the new flow to continue to check and adjust. This iteration continues until no adjustment may be, they will have the minimum cost maximum flow. The characteristics of this line of thought is to
33
山东科技大学本科毕业设计（论文）
maintain the feasibility of the problem (always maintain maximum flow), to promote optimal. Solution to another and in front of the maximum flow algorithm, introduced a similar line of thought, first of all, given the general flow as the initial flow of zero. The cost of the flow to zero, of course, is the smallest cost. And then find a source to the Meeting Point by flow chain, but by the requirements of this chain must be a stream flow of all chain costs by a minimum. If we can find out by flow chain, the chain in the flow by increasing flow, a new flow. The flow will be treated as the initial flow, continue to search for links by increasing stream flow. This iteration continues, until found by flow chain, then the flow is the minimum cost maximum flow. Idea of the characteristics of this algorithm is to maintain the optimal solution of (each of the new fees are the smallest stream flow), but gradually close to the feasible solution (up to maximum flow is a feasible solution when). As a result of the second algorithm and has introduced close to the maximum flow algorithm and the algorithm by finding the minimum cost flow chain, can be turned into a source to find the shortest path to the Meeting Point, so this algorithm here. In this algorithm, in order to seek to increase the minimum cost flow chain, the current flow of each, accompanied by the need to establish a network flow by the flow network. For example, Figure 1 is a network G of minimum cost flow, next to parameters c(e),f(e), w(e), and Figure 2 is the network flow by the flow network G '. By the peak-flow network and the same as the original network. By the following principles in accordance with the establishment of the network edge flow:
If G in the edge (u,v) is not enough traffic, that is, f(u,v)?e(u,v), then
34