发布时间 : 星期二 文章信息与计算科学毕业论文最大流问题及应用更新完毕开始阅读
山东科技大学本科毕业设计（论文）
第二章 预备知识
2.1 图论
所谓“图论”，顾名思义也就是是研究“图”的理论。图论中的“图”是由许多实际问题经过抽象而得到，由点及点与点之间的连线构成，它可以反映一些对象之间的关系。图形中的点表示对象(如工序、选手、通讯站等)，两点之间的有向或无向连线表示对象之间具有某种特定的关系(如先后关系、胜负关系、传递关系、连接关系等)。
物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等都可以用点和线连 接起来的图进行模拟。这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间有无连线，至于连线的方式是直线还是曲线，点与点的vi,vj相对位置如何，都是无关紧要的。 定义1：两点之间不带箭头的连线称为边，一条连接vi,vj的边记为vs (或
[vi,vj])，表示边的集合。
定义2：两点之间带箭头的连线称为E?{e1,e2?,em}弧，一条以vi为始点vj 为终点的弧记为ai?(vi,vj),A?{a1,a2,?am}表示弧的集合。
定义3：由点和边构成的图为无向图，记为G?(V,E)；由点和弧构成的图为有向图，记为D?(V,A).
定义4：在无向图G中，若存在一个点边交错序列
(vi1,ei1,vi2,ei2,?vik?1,eik?1,vik)，满足
4
山东科技大学本科毕业设计（论文）
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