山东科技大学本科毕业设计（论文）
eit?[vit,vit?1](t?1,2,?k?1)，则称之为一条联结vi1和vik的链，记为(vi1,vi2,?,vik),若vi1?vik，则称之为圈。
定义5：在有向图D中，若存在一个点弧交错序列
(vi1,ai1,vi2,ai2,?vik?1,aik?1)，弧ait的始点为vit，终点为vit?1，记为ait?(vit,vit?1)，则称这条点弧的交错序列为从vi1到vik的一条路，记为(vi1,vi2,?,vik)。若路的第一点和最后一点相同，则称之为回路。链与路中
的点互不相同，则为初等链(路)，以后说到的链与路，均指初等链(路)。 定义6：如果对于一个无向图G的每一条边，相应有一个权数wij，则称这样的图为赋权图，记为G?(V,E,C)。
定义7：如果对于一个有向图D的每一条弧，相应有一个权数cij，称这样的图为网络,记为D?(V,A,C)。
一般在网络图中，每条弧的权，不是表示弧的长度、而是表示弧的宽度，即代表距离、费用、通过能力(容量)等等。例如，公路运输网络中路面的宽度或管道输送网络中管道的直径，它是单位时间内允许通过实体的数量。所以将弧权称为弧的容量，网络称为容量网络（参见文献[17]）。 定义8：在图G中，若任何两个点之间至少有一条链（或一条路），则称G是连通图，否则，称为不连通图。
2.2 网络的基本概念
假设要把起点的一批流转物运送到终点去，在每一弧上通过流转物的总量不能超过这条弧上的容量，问题是应该怎样安排运送，才能使从起点
5
山东科技大学本科毕业设计（论文）
运送至终点的总量达到最大，这样的问题就称为网络上最大流问题，最大流问题是网络流问题中的一个非常重要的研究内容（参见文献[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，SS?V,SS??，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的增广路径，而对任意
i?S,j?S，不存在从vi到vj的增广路径，由定义可知对任意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