给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。
（2）网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。
§4 网络最大流问题
网络最大流问题是网络的另一个基本问题。
许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。
4.1 基本概念与定理
1．1．网络与流
定义14 （1）网络：
例1如图7-20是连结某产品产地和销地的交通图。弧表示从到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的产品数量最多。
可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个基本要求：
一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）；
二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。
因此有下面所谓的可行流的定义。
定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件：
（1）容量限制条件：对每一条弧，有
(7.9)
（2）平衡条件：
对于中间点：
流出量=流入量，即对于每一个i (i≠s,t)，有
(7.10)
对于出发带点，有
(7.11)
对于收点，有
(7.12)
则称为一个可行流，称为这个可行流的流量。
注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧；
收点是指只有弧指向，而没有从它的发出去的弧。
可行流总是存在的。例如令所有弧上的流，就得到一个可行流，（称为零流），其流量。
如图7-20中，每条弧上括号内的数字给出的就是一个可行流，它显然满足定义中的条件（1）和（2）。其流量。
所谓网络最大流问题就是求一个流，使得总流量达到最大，并且满足定义15中的条件（1）和（2），即
max
(7.13)
网络最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较直线性规划的一般方法要简便和直观的多。
例2写出图7-20所表示的网络最大流问题的线性规划模型。
解设，则其线性规划模型为
max
3. 增广链
在网络D=(V,A,C)中，若给定一个可行流，我们把网络中使的弧称
为饱和弧，使的弧称为非饱和弧。把的弧称为零流弧，把
的称为非零流弧。
如图7-20中的弧都是非饱和弧，而弧为零流弧。
，若是网络中联结发点和收点的一条链，我定义链的方向是从到
S
则链上的弧被分为两：
一类是：弧的方向与链的方向一致，我们称此类和为前向弧，所有前向弧的集合记为。
另一类是：弧的方向与链的方向一致，我们称此类弧为后向弧，所有后向弧的集合记为。
如图7-20中，设
是一条从到的链，则
,
定义15设是网络D=(V,A,C)上的一个可行流，是从到的一条链，若满足下列条件：
(1)在弧(v i,v j)∈μ+上，即中的每一条弧都是非饱和弧；
(2)在弧上，即中的每一条弧都是非零流弧。
则称是关于的一条增广链。
如前面所说的链就是一条增广链。因为其中μ+上的弧均非饱和，如(v s,v2)∈μ+,f s2=5
4.截集与截量
定义16给定网络D=(V,A,C)，若点集V被分割成两个非空集合V1和V2，使得V=V1+V2,V1∩V2=φ(空集)，且v s∈V1,v t∈V2，则把始点在V1,终点在V2的弧的集合称为分离v s和v t的一个截集，记为(V1,V2)。
如图9.26中，设V1=｛v s,v2,v5｝，V2=｛v3,v4,v6,v t｝则截集为
,
而弧(v3,v2)和(v4,v5)不是该集中的弧。因为这两条弧的起点在V2中，与定义17不符。
显然，一个网络的截集是很多的（但只有有限个），例如在图7-20中，还可以取,，则截集为
另外，若把网络D=(V,A,C)中某截集的弧从网络D中去掉，则从v s到v t便不存在路，所以直观上说，截集是从v s到v t的必经之路。
定义17在网络D=(V,A,C)中，给定一个截集(V1,V2)，则把该截集中所有弧的容量之和，称为这个截集的容量，简称为截量，记为c(V1,V2)，即
C(V1,V2)=(7.16) 例如在上面我们所举的两个截集中，有
而
显然，截集不同，其截量也不同。由于截集的个数是有限的，故其中必有一个截集的容量是最小的，称为最小截集，也就是通常所说的“瓶颈”。
不难证明，网络D=(V,A,C)中，任何一个可行流f=｛f ij｝的流量V(f)，都不会超过任一截集的容量，即
v( f ) ≤ c(V1,V2) (7.17) 如果存在一个可行流f*=｛f*ij｝，网络D=(V,A,C)中有一个截集，使得
(7.18) 则必是最大流，而必是D中的最小截集。
为了求网络最大流f*，我们也说明下面的重要定理。
定理4在网络D=(V,A,C)中，可行流是最大流的充要条件是D中不存在
关于f*的增广链。
证先证必要性。用反证法。若f*是最大流，假设D中存在着关于f*的增广链μ，令
(7.19) 由增广链的定义可知θ>0，令
(7.20)
不难验证是一个可行流，且有
这与f*是最大流的假定矛盾。
再证充分性：即证明设D中不存在关于f*的增广链，f*是最大流。
用下面的方法定义：令
若，且有，则令；
若，且有，则令。
因为不存在着关于的增广链，故
记，于是得到一个截集(V*,)。显然有
所以V(f*)=c，于是f*必是最大流。定理得证。
由上述证明中可见，若是最大流，则网络必定存在一个截集，使得(7.18)
式成立。
定理5（最大流——最小截集定理）对于任意给定的网络D=(V,A,C)，从出发点v s 到收点v t的最大流的流量必等于分割和的最小截集的容量，即
由定理4可知，若给定一个可行流，只要判断网络D有无关于的
增广链。如果有增广链，则可以按定理4前半部分证明中的办法，由公式(7.19)求出调整量Q，再按式（7.20）的方法求出新的可行流。如果流有增广链，则得到最大流。而根据定理
4后半部分证明中定义的办法，可以根据v t是否属于来判断D中有无关于f的增广链。
在实际计算时，我们是用给顶点标号的方法来定义的，在标号过程中，有标号的
顶点表示是
中的点，没有标号的点表示不是中的点。一旦有了标号，就表明找到一条从v s到v t的增广链；如果标号过程无法进行下去，而v t尚未标号，则说明不存在从v s到v t的增广链，于是得到最大流。这时将已标号的点（至少有一个点v s）放在集合中，将未标号点（至少有一个点v t）放在集合中，就得到一个最小截集。
4.2 寻求最大流的标号法（Ford , Fulkerson）
从一个可行流出发（若网络中没有给定，则可以设是零流），经过标
号过程与调整过程。
1）1）标号过程
在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点，每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量θ用的。
标号过程开始，总先给v s标上(0,+∞)，这时v s是标号而未检查的点，其余都是未标号点，一般地，取一个标号而未检查的点v i，对一切未标号点v j：
(1) 在弧上，，则给v j标号。这里。
这时点v j成为标号而未检查的点。
(2) 若在弧上，，给v j标号。这里。这
时点v j成为标号而未检查的点。
于是成为标号而已检查过的点，重复上述步骤，一旦被标上号，表明得到一条从到的增广链，转入调整过程。
若所有标号都是已检查过，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。
2）2调整过程
首先按及其它点的第一个标号，利用“反向追踪”的办法，找出增广链μ。例如设v t的第一个标号为（或），则弧（或相应地）是μ上的弧。接下来检查的第一个标号，若为（或），则找出（或相应地）。再检查的第一个标号，依此下去，直到为止。这时被找出的弧就构成了增广链。令调整量θ是，即的第二个标号。
令
去掉所有的标号，对新的可行流，重新进入标号过程。
下面，以例题说明此算法求解过程。
例3 用标号法求图7-20所示网络最大流。弧旁的数是
解:对图7-20中各顶点进行标号。
首先给标(0,+∞)，即
检查：
在弧上，因为，又有
,所以给标；
在弧上，因为，又有
,所以给标。
检查：
在弧上，因为，又有
,所以给标；
在弧上，因为，又有
,所以给标；
在弧上，因为，又有
,所以给V3标。
因为前面已给v 3标过号，这里又给标，它们分别表示两条不同的路
线，这里不存在修改标号的问题（与最短路不同）。因为我们的目标是尽快找出一条从v s到v t的增广链，即尽快使终点v t获得标号，所以不必在中途过多停留。也就是说在对已标号点v i进行检查时，每次只检查一个相邻点v j（不论前向弧或后向弧均可），再给标号即可，而不必检查所有与v i相邻的点。事实上，其余的相邻点也不会漏掉，因为以后还要通过检查
这些点来找出新的增广链。以下我们就按这种思路进行。
检查：
在弧上，因为，又有
.所以给标.
至此，终点已获得标号，于是找出一条从到的增广链。再由标号的第一部分用反向追踪法找出路线，即
（见图7-21）。
进行调查：
这时的调整量.再按公式（7.20）调整。由于上各弧均为前向弧，故得
，
，
.
（见图7-21）.其余的不变.
对这个新的可行流再进入标号过程，寻找新增广链。开始给标，检查，给标，检查：
在弧上，因为（见图7-21），故该弧已饱和，标号无法进行下去。
在弧上，因为，又有
所以给标，
检查：
在弧上，因为，又有
所以给标，
检查：
在弧上，因为，又有
，所以给标.
于是又得到一条增广链(见图7-22)
进行调整：这时。调整结果如图9.28所示。再重新标号求新的增广链.
开始给标，检查，给标。检查，给标，检查，给标，检查，因已是饱和弧（见图7-22）。标号无法进行。
但在弧上，.又有
，所以给标.
于是又得到一条增广链：
.
再进行调整（见图7-23）.
再重新进行标号求新的增广链：
开始给标（0，+），检查，给标.
检查：
这时弧均已饱和。而在弧上，因，又有
所以给标，表明弧为后向
弧.
检查，给标。检查，给标。于是又得到一条增广链：
.
再进行调整（见图7-24）。
再重新进行标号求新的增广链：
开始给标(0,+∞)，检查，给标。检查，这时和
均为前向弧，都已饱和，弧为后向弧，且为零流弧。故标号无法进行。
但在弧
上因为。又有
.所以给标.
检查,给标。检查，因为已饱和（见图7-24）。而在弧上，因为，又有
.所以给标，再检查，给标。于是又得到一条增广链：
.
再进行调整（见图7-25）。
再重新进行标号求新的增广链。
开始给标(0,+∞)，检查，给标。检查，因为已饱和，而为弧上标号还可以继续进行，给标。检查。给标。于是又得到一条增广链
再进行调整（见图7-26）。
网络流算法 在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。 ［问题描述］如图4-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。 一、基本概念及相关定理 1)网络与网络流 定义1 给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点， 对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图4-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图4-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。 2)可行流与最大流 在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有： 定义2 满足下列条件 (1)容量约束：0≤fij≤cij，(vi,vj)∈E， (2)守恒条件 对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。 网络N中流值最大的流f*称为N的最大流。 3)可增广路径 所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。 定义3 设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：
给定一个有向图D=(V,A),在V中指定一点称为发点(记为),该点只有出发去的弧,指定另一点称为收点(记为),该点只有指向它的弧,其余的点叫做中间点。对于A中的每一条弧,对应一个数(简记),称之为弧的容量。通常我们把这样的D叫做网络,记为D=(V,A,C)。 (2)网络流:在弧集A上定义一个非负函数。就是通过弧 的实际流量,简记,称就是网络上的流函数,简称网络流或流,称为网络流的流量。 §4 网络最大流问题 网络最大流问题就是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量,金融系统有现金流,控制系统有信息流等。许多流问题主要就是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4、1 基本概念与定理 1．1.网络与流 定义14 (1)网络: 例1如图7-20就是连结某产品产地与销地的交通图。弧表示从 到的运输线,弧旁的数字表示这条运输线的最大通过能力,括号内的数字表示该弧上的实际流。现要求制定一个运输方案,使从运到的产品数量最多。 可行流与最大流 在运输网络的实际问题中,我们可以瞧出,对于流有两个基本要求:
一就是每条弧上的流量必须就是非负的且不能超过该弧的最大通过能力(即该弧的容量); 二就是起点发出的流的总与(称为流量),必须等于终点接收的流的总与,且各中间点流入的流量之与必须等于从该点流出的流量之与,即流入的流量之与与流出的流量之与的差为零,也就就是说各中间点只起转运作用,它既不产出新的物资,也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=(V,A,C)与给定的流,若满足下列条件: （1）容量限制条件:对每一条弧,有 (7、9) (2)平衡条件: 对于中间点: 流出量=流入量,即对于每一个i (i≠s,t),有 (7、10) 对于出发带点,有 (7、11) 对于收点,有 (7、12) 则称为一个可行流,称为这个可行流的流量。 注意,我们这里所说的出发点就是指只有从发出去的弧,而没有指向的弧;收点就是指只有弧指向,而没有从它的发出去的弧。 可行流总就是存在的。例如令所有弧上的流,就得到一个可行流,(称为零流),其流量。 如图7-20中,每条弧上括号内的数字给出的就就是一个可行流,它显然满足定义中的条件(1)与(2)。其流量。 所谓网络最大流问题就就是求一个流,使得总流量达到最大,并且满足定义15中的条件(1)与(2),即 max
给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。 （2）网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。 §4 网络最大流问题 网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4.1 基本概念与定理 1．1．网络与流 定义14 （1）网络： 例1如图7-20是连结某产品产地和销地的交通图。弧表示从 到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的产品数量最多。 可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个基本要求： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件： （1）容量限制条件：对每一条弧，有 (7.9) （2）平衡条件： 对于中间点： 流出量=流入量，即对于每一个i (i≠s,t)，有 (7.10) 对于出发带点，有 (7.11) 对于收点，有 (7.12) 则称为一个可行流，称为这个可行流的流量。 注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧； 收点是指只有弧指向，而没有从它的发出去的弧。
最大流问题 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。 网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。 基本概念 设一个赋权有向图D=(V , A)，在V 中指定一个发点（源）vs 和一个收点（汇）vt ，且只能有一个发点vs 和一个收点vt 。（即D 中与vs 相关联的弧只能以 vs 为起点，与vt 相关联的弧只能以 vt 为终点），其他的点叫做中间点。 对于D 中的每一个弧(vi, vj)A ∈，都有一个权cij 叫做弧的容量。我们把这样的图 D 叫做一个网络系统，简称网络，记做D =(V , A, C) 。 Vs Vt 图1 图1是一个网络。每一个弧旁边的权就是对应的容量。 网络D 上的流，是指定义在弧集合A 上的一个函数f={f(vi, vj)}={fij}，f(vi,vj)=fij 叫做弧在(vi,vj)上的流量 。 Vs Vt 图2 图2中，每条弧上都有流量fij ，例如fs1=5，fs2=3，f13=2等。 容量是最大通过能力，流量是单位时间的实际通过量。显然，0≤fij≤cij 。网络系统上流的特点： (1)发点的总流出量和收点的总流入量必相等； (2)每一个中间点的流入量与流出量的代数和等于零； (3)每一个弧上的流量不能超过它的最大通过能力（即容量）。网络上的一个流f={fij}叫做可行流，如果f 满足以下条件： （1）容量条件：对于每一个弧(vi,vj)A ∈，有0≤fij≤cij 。
（2）平衡条件： 对于发点vs ，有∑f sj ?∑f js =v (f ) 对于收点vt ，有∑f tj ?∑f jt =?v (f ) 对于中间点，有∑f ij ?∑f ji =0 其中发点的总流量（或收点的总流量）v(f)叫做这个可行流的流量。 网络系统中最大流问题就是，在给定的网络上寻求一个可行流f={fij}，其流量v(f)达到最大值，即从vs 到vt 的通过量最大。 最大流问题可以通过线性规划数学模型来求解。图1的最大流问题的线性规划数学模型为 max v =f s 1+f s 2 s.t. { ∑j f ij ?∑i f ij =0 i ≠s,t 0≤f ij ≤c ij 所有弧(v i ,v j ) fs1和fs2是与起点相连的两条弧上的流量。 满足上式的约束条件的解{fij}称为可行解，在最大流问题中称为可行流。 对有多个发点和多个收点的网络，可以另外虚设一个总发点和一个总收点，并将其分别 与各发点、收点连起来，就可以转换为只含一个发点和一个收点的网络。 S T 所以一般只研究具有一个发点和一个收点的网络。 我们把fij=cij 的弧叫做饱和弧，fij
从一道题目的解法试谈网络流的构造与算法 福建师大附中江鹏 1. 引论 A. 对网络流算法的认识 网络流算法是一种高效实用的算法，相对于其它图论算法来说，模型更加复杂，编程复杂度也更高，但是它综合了图论中的其它一些算法（如最短路径），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的，看似NP的问题。 B. 具体问题的应用 网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。
2. 例题分析 【问题1】项目发展规划（Develop） Macrosoft?公司准备制定一份未来的发展规划。公司各部门提出的发展项目汇总成了一张规划表，该表包含了许多项目。对于每个项目，规划表中都给出了它所需的投资或预计的盈利。由于某些项目的实施必须依赖于其它项目的开发成果，所以如果要实施这个项目的话，它所依赖的项目也是必不可少的。现在请你担任Macrosoft?公司的总裁，从这些项目中挑选出一部分，使你的公司获得最大的净利润。 ●输入 输入文件包括项目的数量N，每个项目的预算Ci和它所依赖的项目集合Pi。格式如下：第1行是N； 接下来的第i行每行表示第i个项目的信息。每行的第一个数是Ci，正数表示盈利，负数表示投资。剩下的数是项目i所依赖的项目的编号。 每行相邻的两个数之间用一个或多个空格隔开。 ●输出 第1行是公司的最大净利润。接着是获得最大净利润的项目选择方案。若有多个方案，则输出挑选项目最少的一个方案。每行一个数，表示选择的项目的编号，所有项目按从小到大的顺序输出。 ●数据限制 0≤Ｎ≤1000 -1000000≤Ci≤1000000 ●输入输出范例
开题报告 数学与应用数学 网络最大流问题算法研究 一、综述本课题国内外研究动态, 说明选题的依据和意义 最大流问题是指在一定的条件下, 要求流过网络的物流、能量流、信息流等流量为最大的问题[2]. 最大流问题已有50多年的研究历史, 这段时期内, 人们建立了最大流问题较 为完善的理论, 同时开发了大量优秀的算法. 如Ford 和Fulkerson 增截轨算法 [3]、Dinic 阻塞流算法、Goldberg 推进和重标号算法[6]以及Goldberg 和Rao 的二分长度阻塞流算法等等, 这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用. 近年来, 随着计算机科学技术和网络的快速发展, 网络最大流问题得到了更深入的研究, 并极大地推动了最大流问题的研究进展. 然而, 研究工作仍未结束: 首先, 在理论算法研究方面, 人们还没有发现最大流问题算法时间复杂度的精确下界, 更没有任何一个通用算法达到或接近问题的下界; 其次, 在算法的实际性能方面, 目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决, 发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决. 因此, 关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig 提出的网络单纯刑法和Ford 和Fulkerson 的增载轨算法, 他们都是伪多项式时间算法, 分别由Dinic, Edmonds 和Karp 等提出. 1973年Dinic 首次获得了时间复杂度的核心因子为nm 算法. 以后的几十年中, 最大流算法获得了很大的进展. 在最大流问题中, ()nm O 时间界是一个自然的障碍. 如果我们把一个流沿从源到汇的各个路径进行分解, 根据流分解定理, 这些包含流的路径的总长度为()nm Θ.因此, 对每次利用一条曾接轨的算法, ()nm O 时间是这类算法的下界. 尽管这个下界对使用动态树数据结构或基于预流概念的算法是不适用的, 但在很长一段时间内, ()nm O 的
文献综述 数学与应用数学 网络最大流问题算法研究 最大流问题是指在一定的条件下,要求流过网络的物流、能量流、信息流等流量为最大的问题[2].最大流问题已有50多年的研究历史,这段时期内,人们建立了最大流问题较为完善的理论,同时开发了大量的算法.如Ford和Fulkerson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法[6]以及Goldberg和Rao的二分长度阻塞流算法等等,这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用.近年来,随着计算机科学技术和网络的快速发展,网络最大流问题得到了更深入的研究,并极大地推动了最大流问题的研究进展.然而,研究工作仍未结束:首先,在理论算法研究方面,人们还没有发现最大流问题算法时间复杂度的精确下界,更没有任何一个通用算法达到或接近问题的下界; 其次,在算法的实际性能方面,目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决,发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决.因此,关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig[6]提出的网络单纯刑法和Ford和Fulkerson的增载轨算法, 他们都是伪多项式时间算法,分别由Dinic、Edmonds和Karp等提出.1973年Dinic首 次获得了时间复杂度的核心因子为nm算法.以后的几十年中,最大流算法获得了很 大的进展. 本文主要介绍的是网络最大流的几种主要算法,其中重点介绍了标号算法的详细 过程,其后给出了其在实际中的应用实例,后面介绍了现有的几种主要算法,虽然没 有给出具体的程序,但本文目的主要是了解最大流问题的解决思想,读者对网络流算 法有更深刻的认识,读者要想了解更多关于最大流问题的研究,详细可以参照Goldberg等人的研究成果, 这些程序在网上都可以轻松得到. 在这里就不再详细讲述. 下面简要介绍一下增载轨算法. 增载轨算法[5]: 沿剩余网络中从源到汇的有向路径推进流. 增载轨算法包括Ford
网络最大流问题
给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。 （2）网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。 §4 网络最大流问题 网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4.1 基本概念与定理 1．1．网络与流 定义14 （1）网络： 例1如图7-20是连结某产品产地和销地的交通图。弧表示从到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的 产品数量最多。 可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个基本要求： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件： （1）容量限制条件：对每一条弧，有 (7.9) （2）平衡条件： 对于中间点： 流出量=流入量，即对于每一个i (i≠s,t)，有 (7.10) 对于出发带点，有 (7.11) 对于收点，有 (7.12) 则称为一个可行流，称为这个可行流的流量。
云南大学数学与统计学实验教学中心 实 验 报 告 一、实验目的 编制程序，在赋权图中找到从发点Vs 到收点Vt 的最大流，并输出最大流. 二、实验环境 VS2010（C++） 三、实验内容 P272 例14： 用标号法求图10-25所示网络的最大流，弧旁的数是()ij ij f c , 四、实验过程 A 、将上面算法编写实现运行结果如下图： 用标号法寻找网络中最大流的基本思想是寻找可增广链，使网络的流量得以增加， 直到最大为止（标号过程进行不下去，而收点vt 尚未标号，说明不存在增广路，得到最大流）。我采用的方法是从零流开始，再用标号法寻求最大流。 标号法主要分为两个步骤： (1) 标号过程 开始标号，初始化结点的结构体数组，然后标记vs 为标号点并进行检查，此时 其余都是未标号的点。然后找到与vs 有边相连的结点，标记那些点为标号而未检查的点。取一个标号而未检查(Tag=marking)的点vi ，对于一切未标号(Tag=n_mark) 的点vj ： A)．对于弧(vi ，vj)，若fij
到一条从vi到vt的增广路径p，转入调整过程。 若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。 (2) 调整过程 从vt点开始，通过每个点的第一个标号，反向追踪(根据结点的From信息)，可找出增广路P。直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算调整值：min{min(cij-fij)，min（fij）} a、初始化结果： 输入的结果为红色字体 b、初始化后的到结果： 红框中得到的图的关系与课本例题中的一样！所以创建图形正确！ c、最后得到的结果：