Ford–Fulkerson算法铁路运输系统中车辆流问题的研究(3)
表1.1 最大流算法时间复杂度进展[9]
（不包括随机算法和近似算法）
注： 介于 和 之间， 在 的多项式量级上
1.3 网络流基本概念及其数学模型
1.3.1 基本概念
定义 1：一个网络（Network）是一个有两个不同顶点的有向图 ，一点称为网络的源点（source），记为 或 ，而另一点称为收点（sink），记为 或 ，其余的点叫中间点（intermediate vertices）。对于每一个弧（arc） ，对应有一个 (或简写为 ) , 称为弧的容量（capacity）。为了方便起见，我们通常把网络记作 。
网络上的流（flow），是指定义在弧集合 上的一个函数 ，并称 为弧 上的流量(也简记作 )。
定义 2：满足下述条件的流 称为可行流：
(1 ) 容量限制条件：对每一弧 ， ；
(2 ) 平衡条件：
对于中间点：流出量等于流入量，即对每个 有
对于发点 ，记
对于收点 ，记
式中 称为这个可行流的流量，即源点的净输出量(或收点的净输入量) 。并称其为可行 流。
可行流总是存在的。比如令所有弧的流量 ，就得到一个可行流(称为零-流)，其流量 。
定义 3：网络中的一个流是最大流，如果网络中没有其它的流量比其大的流。
若给一个可行流 ，我们把网络中使 的弧称为饱和弧（saturated arc）, 使 的弧称为非饱和弧（unsaturated arc）。使 的弧称为零流弧（flow-zero arc）, 使 的弧称为非零流弧（flow-positive arc）。
若 是网络中连接源点 和收点 的一条路径，我们定义路径的方向是从 到 ，则路径上的弧被分为两类: 一类是弧的方向与路径的方向一致，叫做前向弧（forward arc）。前向弧的全体记为 。另一类弧与路径的方向相反，称为后向弧（backward arc）。后向弧的全体记为 。
定义 4：设 是一个 可行流， 是从 到 的一条路径，若 满足下列条件，称之为关于可行流 的增广路（augmenting path），或 增广路。
在弧 上， ，即其中每一条弧都是非饱和弧；
在弧 上， ，即其中每一条弧都是非零流弧。
设 ， ，我们把始点在 中, 终点在 中的所有弧构成的集合, 记为 。
定义 5：给网络 ，若点集 被剖分为两个非空集合 和 使 ， ，则把弧集 称为是(分离 和 的) 割集（cut set）。
给定一 割集 ，把割集 中所有弧的容量之和称为这个割集的容量(简称为割量) , 记为 ，即
1.3.2 数学模型
网络最大流问题的数学模型可以描述为：
并且满足：
最大流问题是一个特殊的线性规划问题。
二 Ford–Fulkerson算法
Ford–Fulkerson算法是1956年提出的，是被广泛使用的一种经典算法。Ford和Fulkerson的算法首次使用组合优化的方法来解决最大流问题。该算法引进了剩余网络、增广路等概念[1]，把最大流问题的求解归结为从一个初值（即一个可行流）开始，不断递增（即增广）直到求得最优解的迭代过程，这个过程奠定了用组合方法求解最大流问题的基础。
2.1 Ford–Fulkerson算法的思想及原理
定理1（最大流最小割定理[1]）：设 是一个源为 收点为 的网络。关于 中的每个可行 流，有下列相互等价的命题：
（a）流 是一个最大 流；
（b） 中不存在一条 增广路；
（c）存在一个 割 ，使得 。
由于本文的目的并不是研究最大流的理论，在这里只证明 [13]。
证明： ：若 是最大流，设 中存在关于 的增广路，令
由增广路的定义，可知 ，令
不难验证 是一个可行流，且 。这与是最大流的假设矛盾。