山 东 科 技 大 学
本科毕业设计（论文）
题 目 最大流问题以及应用
学 院 名 称 数学与系统科学学院 专业班级 信息与计算科学2011级2班 学生姓名 吕永强 学 号 201101051416
摘要
网络流问题是运筹学的重要研究课题。最大流问题是网络流问题的一个重要的内容，应用极为广泛。研究最大流问题并将其应用到工业、工程、商业、农业，运输业等领域可给我们的生活带来很大方便。
本论文讨论最大流问题，综述图论的历史背景、基本概念和基本知识；阐述网络的基本概念；介绍最大流问题的核心依据——Ford-Fulkerson最大流最小割定理；综述解决最大流问题的 几种算法Ford-Fulkerson标号法、Edmonds-Karp修正算法、Dinic算法，并比较各算法在解决不同问题中的优劣。
为了更加明确的展现最大流问题在生产生活中的应用，本文例举了一个实际生活中的问题——铁路货运列车的最优调度来突出研究最大流问题的重要意义，此实例需要求解的是在一定的限制条件下，设计出一个在一昼夜间能通过某段铁路的最多的货运列车数量并列出每 辆列车开出的时刻表。在此实例中，通过从实际问题中抽象出网络图，将实际问题转化为最大流问题并应用图的性质和Ford-Fulkerson标号法的算法依据，最终解决了问题。
本文采用理论与 实例相结合，重在应用理论依据解决实际问题，具有较强的实践性，突出的是应用。
Abstract
The network flow problem is an important operational research subject. The maximum flow problem is an important content of network flow problem, which has widely applications. The research of maximum flow problem and its applications to industry, engineering，commerce, agriculture, transportation and other areas can bring us great convenience.
The paper discusses the maximum flow problem, and summarizes the historical background of graph theory, basic concepts, basic knowledge and describes the basic concept of the network. The core basis of the maximum flow problem -- Ford-Fulkerson maximum flow minimum cut theorem is introduced. Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm, Edmonds-Karp correct algorithm, Dinic algorithm are summarized in this paper. It also compares various algorithms to solve different problems in the pros and cons.
In order to more clearly show the application of the maximum flow problem in the production life, the paper illustrates a real-life problem - -The optimal scheduling of railway freight train to highlight the importance of maximum flow. This instance is to be solved under certain constraints , to design the most freight train numbers through the railway in a day and night and to list out the schedules for each train. In this instance, by abstracting the network diagram from the real problems, transform the actual problem into the maximum flow problem, and use the properties of graph and Ford-Fulkerson labeling algorithm, and ultimately solve the problem.
In this paper, the combination of theory and examples focus on solving practical problems by applying theoretical basis. It has strong practicality and
highlights the applications.
Keywords： Graph Network flow Maximum flow
目录
第一章 绪论 ................................................................................................................. 1
1.1 最大流问题的研究内容及背景 .................................................................... 1 1.2 最大流问题的发展状况 ................................................................................. 1 1.3 选题的意义 ........................................................................................................ 2
第二章 预备知识 ....................................................................................................... 4
2.1 图论 ...................................................................................................................... 4 2.2 网络的基本概念 ............................................................................................... 5 2.3 最大流问题核心依据——Ford-Fulkerson最大流最小割定理 ......... 7
第三章 最大流问题的几种算法 .................................................................... 9
3.1 标号法(Ford-Fulkerson算法) ...................................................................... 9 3.2 Edmonds-Karp修正算法 ........................................................................... 12 3.3 Dinic算法 ...................................................................................................... 15
第四章 最大流问题的应用 ............................................................................. 19
4.1 铁路货运列车的最优调度 ........................................................................... 19
第五章 结论 ............................................................................................................. 30 参 考 文 献 ............................................................................................................... 31 致谢辞 ............................................................................................................................. 32 附录1英文原文 ....................................................................................................... 33 附录2中文译文 ....................................................................................................... 37