摘 要

本文主要讲解最大流问题，以及在最大流问题中最常用的一种方法——Ford-Fulkerson方法。Ford-Fulkerson方法更多的是一种算法思想，它具有多种不同的实现方式。该方法依赖于三种重要概念：残留网络，增广路径和割。本文将会详细介绍这些内容，对不同的实现进行了比较，所得结果对具体问题采用何种方法实现具有重要的指导意义。本文中所提到的算法均给出了具体实现步骤，并针对其中一种给出了完整的代码。

论文主要研究了图论中的最大流问题，更具体一点是研究求解问题的一种常用方法Ford-Fulkerson算法。

研究结果表明：在Ford-Fulkerson算法中，使用不同的解法，会有不同的运行效率。此处，不同的解法是指：第一，存储图的数据结构使用邻接表和邻接矩阵两种方式；第二，寻找残留网络中的增广路径的方式使用了多种不同的方法。

本文的特色在于：不仅研究了Ford-Fulkerson算法的不同实现具体步骤，还进一步讨论了最大流最小割算法在实际中的应用，如图像分割等。

关键词：最大流；残余网络；增广路径；Ford-Fulkerson

Abstract

This article focuses on the Ford-Fulkerson solution to the maximum flow problem. But it is a method, not a single specific algorithm, because it contains several implementations with different run times. The method relies on three important ideas: residual network, augmented path and cut. This article will detail the contents of the different implementation of the comparison, the results of the specific problems with what method to achieve an important guiding significance. The algorithms mentioned in this paper give concrete implementation steps and give complete code for one of them.

In this paper, we study the maximum flow minimization problem in graph theory, and more specifically, we study one of the methods of finding the maximum flow of a network flow Ford-Fulkerson algorithm.

The results show that in the Ford-Fulkerson algorithm, the use of different solutions, there will be different operating efficiency. Here, the different solutions are: first, the data structure of the graph using the adjacent table and adjacency matrix; Second, the search for the remnant network in the algorithm of the increase in the use of depth-first search and breadth-first search in two ways.

The characteristics of this paper are as follows: not only the concrete steps of Ford-Fulkerson algorithm are studied, but also the application of the maximum flow minimum cut algorithm in practice, such as image segmentation.

Key Words: maximum flow; residual network; augmented path; Ford-Fulkerson

目 录

摘 要 I

Abstract II

1绪论 1

1.1研究背景及意义 1

1.2课题的研究现状 1

1.3本文研究内容及预期 1

2网络流中的基本概念及定理 3

2.1出弧和入弧的概念 3

2.2网络的概念 3

2.3流的概念 4

2.4割的概念 5

2.5残留网络的概念 5

2.6增广路径的概念 7

2.7增广路径定理 8

2.8最大流最小割定理 9

2.9整数最大流定理 9

3 Ford-Fulkerson算法 11

3.1算法基本思想 11

3.2标号法 11

3.2.1算法详细过程 11

3.2.2算法复杂度分析 13

3.2.3改进措施 13

3.3分层网络法 13

3.2.1算法详细过程 14

3.4采用深度优先搜索的算法 15

3.4.1算法详细过程 15

3.4.2算法复杂度分析 16

3.5实验结果分析 17

3.5.1人工模拟结果 17

3.5.2程序运行结果 20

3.5.3结果分析 20

3.6 FF算法的应用 21

4无向图中的FF算法 23

5总结与展望 24

参考文献 25

致 谢 26

附 录 27

1绪论

1.1研究背景及意义

现实生活中有许多问题，可以将其建模，抽象为一个最大流问题。最大流问题在经济学和运筹学中很常见。假设在一个网络中，每条弧都有容量的限制，最大流问题的研究就是试图解决这样的问题：从源点到汇点，如何选择路径、分配流量，能够使整个系统的流量达到最大。最大流问题广泛存在于那些需要调度流量的系统中,如：交通系统中的车流、信息系统中的信息流、供水系统中的水流等。现实社会中，在很多方面是通过各种网络来管理与控制。网络可以是运输货物时的运输网，或者如运送石油时的输油管道网络，或者如传输数据的数据网络，诸如此类，在这些网络中，考虑得最多的两个方面的问题，一个是成本问题，还有一个是流量问题。事实上，这两个问题便分别是我们所讨论的网络的最小费用问题和最大流量问题。

1.2课题的研究现状

对最大流问题的研究，从很多年前就有了，至今已有五十多年的时间。人们在相关领域建立起了较为完善的理论体系，并且提出了许多算法。其中，比较经典的算法有Ford-Fulkerson算法（也即本文所讨论的对象），最短增广路径算法，预流推进算法，以及Dinic算法^[1]。但是，尽管这么多年来在最大流问题的研究上取得了很大进展，目前仍有一些问题尚未得到解决。首先，人们还没有办法求出最大流问题的精确下界；其次，在解决一些由实际问题抽象而来的最大流问题上，现有的算法存在着严重的性能问题，不能满足实际需要^[2]。实际上，无论是是Ford-Fulkerson算法还是最短增广路径算法都存在着一些不足：Ford-Fulkerson算法的算法思想相对明确，但是它并没有对增广链如何选择做出统一的标准，因此在实际使用过程中，如果增广路径选择地不好的话，那么可能会使计算量会变得很大，换句话说，就是增广路径的选择具有任意性，因此引入了一些不确定因素^[3]。