图与网络分析 最大流问题
- 格式:ppt
- 大小:4.34 MB
- 文档页数:25
最大流问题在许多实际的网络系统中都存在着流量和最大流问题。
例如铁路运输系统中的车辆流,城市给排水系统的水流问题等等。
网络系统流最大流问题是图与网络流理论中十分重要的最优化问题,它对于解决生产实际问题起着十分重要的作用。
基本概念设一个赋权有向图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 的通过量最大。