山东科技大学本科毕业设计（论文）
运送至终点的总量达到最大，这样的问题就称为网络上最大流问题，最大流问题是网络流问题中的一个非常重要的研究内容（参见文献[15]），以下讨论的网络均为只有一个发点vs和一个收点vt的容量网络D?(V,A,C)。 定义9：对任意容量网络D?(V,A,C)中的弧(vi,vj)有流量fij，称集合
f?{fij}为网络D上的一个流，称满足下列条件的流f为可行流：
(1)容量限制条件：对D中每条弧(vi,vj)，有0?fij?cij； (2)平衡条件：
①对中间点vi，有?jfi??ikf(即中间点vi的物资的输入量与输出
jk量相等)。
②对收、发点vt,vs有?fsi??fjt?W(即从vs点发出的物资总量
ij等于vt点入的量) ，W为网络流的总流量。
在容量网络D?(V,A,C)中cij表示弧(vi,vj)的容量，令xij为通过弧
(vi,vj)的流量，显然有0?xij?cij，流{xij}应遵守点守恒规则，即：
??W?x?x??ij?ji?0??W?称为守恒方程。
定义10：对任意容量网络D?(V,A,C)，寻求一可行流f使得流量W取得 极大值，这个可行流f便称为最大流。
定义11：在容量网络D?(V,A,C)中，若?为网络中从发点vs到收点vt的一条路，给?定向为从vs到vt，?上的弧凡与?同向称为前向弧。凡与?反
6
i?si?s,t
i?t山东科技大学本科毕业设计（论文）
向称为后向弧，其集合分别用??和??表示，f是一个可行流，如果满足
???0?fij?cij(vi,vj)?? ????cij?fij?0(vi,vj)??则称?为从vs到vt的(关于f的)增广链。
定义12：在容量网络G?(V,A,C)中，若有弧集A'为A的子集，将D分为两个子图D1,D2，其顶点集合分别记S,S，S?S?V,S?S??，vs,vt分别属于S,S，满足：①D(V,A?A')不连通；②A''为A'的真子集，而D(V,A?A'')仍连通，则称A'为D的割集，记A'?(S,S)。
割集(S,S)中所有始点在S，终点在S的边的容量之和，称为(S,S)的割集容量，记为C(S,S)。
2.3 最大流问题核心依据——Ford-Fulkerson最大流最小割定
理
Ford-Fulkerson最大流最小割定理是由Ford和Fulkerson在1956年提出的，是图论的核心定理。
定理1：（Ford-Fulkerson最大流最小割定理）任一容量网络D中，从vs到vt 的最大流{fij}的流量等于分离vs,vt的最小割的容量。
证明：设在D中从vs到vt的任一可行流{xij}的流量为W，最小割集为
(S,S)，最小割集的容量为C(S,S)。这个定理的证明分两步：
7
山东科技大学本科毕业设计（论文）
? 我们先证明W?C(S,S)：
由守恒方程可得：
W??(?xij??xji)i?Sjj???(xij?xji)???(xij?xji)
i?Sj?Si?Sj?S???(xij?xji)i?Sj?S(3.1)因此有：W???(xij?xji)???xij???cij?C(S,S)。
i?Sj?Si?Sj?Si?Sj?S? 下面我们证明一个可行流是最大流，当且仅当不存在关于它的从的增广路径：
vs到
vt必然性：显然，因为如果存在增广路径，还可以继续增广，流就不是最大流。
充分性：假设可行流{xij}是一个不存在关于它的增广路径的流，对于最小割集(S,S)，有对任意i,j?S，存在从vi到vj的增广路径，而对任意不存在从vi到vj的增广路径，由定义可知对任意i?S,j?S有： i?S,j?S，
xij?cij,xji?0
由公式(3.1)可知：W???cij?C(S,S)。
i?Sj?S即流的值等于割集的容量，定理得证。
8
山东科技大学本科毕业设计（论文）
第三章 最大流问题的几种算法
最大流问题是社会经济生活和军事活动中经常出现的优化问题。如在经济建设和国防建设中，经常遇到一些物资调运的问题。如何制定调运方案，将物资尽快运到指定点，而且不影响费用的计划开销，即为最大流问题。下面用数学语言来说明最大流问题：
1.设有一个有向连通图G(V,A)，在V中指定一点称为发点s,和另外一点为收点t，其余的称为中间点，弧（arc）集A中每条弧（i，j）上有非负数cij称为这弧的容量，记容量集为c={cij}，称这样的图为一个网络，记为G(V,A, c)（注：当（i，j）不是弧时cij=0）。
2.在弧集A上的弧（i，j）定义一非负数fij，称为弧（i，j）上的流量，流量的集合f={fij}称为网络的一个流，满足下列条件的称为可行流：
1）容量限制条件，所有的弧的流量fij不大于弧的容量cij； 2）平衡条件，对所有的中间点，流入的流量和等于流出的流量和，发点流出的流量F等于流进收点的总流量F.
最大流问题就是求总流量最大达可行流。
求解最大流问题存在许多算法，这一节将介绍几种常用算法。
3.1 标号法(Ford-Fulkerson算法)
3.1.1标号法(Ford-Fulkerson算法)思想
Ford-Fulkerson标号法是一种找最大流f的算法。它是由Ford和Fulkerson于1957年最早提出的，其基本思想是从任意一个可行流出发寻
9
山东科技大学本科毕业设计（论文）
找—条增广路径，并在这条增广路径上增加流量，于是便得到一个新的可行流，然后在这新的可行流的基础上再找一条新的增广路径，再增加流量……，继续这个过程，一直到找不到新的增广路径为止（参见文献[2]）。
采用Ford-Fulkerson标号法求解最大流问题时，在标号过程中，一个点仅有下列三种状态之一：标号已检查(有标号且所有相邻点都标号了)；标号未检查(有标号，但某些相邻点未标号)；未标号（参见文献[6]）。
Ford-Fulkerson标号算法分为两个过程：一是标号过程，通过标号过程找到一条增广路径；二是增广过程，沿着增广路径增加网络流流量的过程（参见文献[18]）。现在我们考虑只有一个发点vs和一个收点vt的容量网络，应用Ford-Fulkerson标号算法求解它的最大流
3.1.2 Ford-Fulkerson标号法的具体步骤 A:标号过程
步骤0 确定一初始可行流{fij}，可以是零流。 步骤1 给发点vs以标号[?,vs]。
步骤2 选择一个已标号但未检查的点vi，并作如下检查：
① 对每一弧(vi,vj)，若vj未给标号，而且cij?fij时，即流出未饱和弧,给vj以标号[?j,vi]；
② 对每一弧(vj,vi)，若vj未给标号，而且fji?0时，即流入非零流弧，给vj以标号[?j,?vi]；
??cij?fij其中：?j?min{?i,?},?????fji10
若(vi,vj)为流出未饱和弧若(vj,vi)为流入非零流弧