下载文档原格式
最大流问题在许多实际的网络系统中都存在着流量和最大流问题。
例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。
网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。
基本概念设一个赋权有向图D=(V , A)，在V 中指定一个发点（源）vs 和一个收点（汇）vt ，且只能有一个发点vs 和一个收点vt 。
（即D 中与vs 相关联的弧只能以 vs 为起点，与vt 相关联的弧只能以 vt 为终点），其他的点叫做中间点。
对于D 中的每一个弧(vi, vj)A ∈，都有一个权cij 叫做弧的容量。
我们把这样的图 D 叫做一个网络系统，简称网络，记做D =(V , A, C)。
VsVt 图1图1是一个网络。
每一个弧旁边的权就是对应的容量。
网络D 上的流，是指定义在弧集合A 上的一个函数f={f(vi, vj)}={fij}，f(vi,vj)=fij 叫做弧在(vi,vj)上的流量。
VsVt 图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 的通过量最大。
