资源描述：
《网络最大流问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、第四节网络最大流问题本节内容的安排基本概念与基本定理寻求最大流的标号法1.应用背景在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题,控制系统中的信息流问题，常见的人流，物流，水流，气流，电流，现金流等。在一定条件下,求解给定系统的最大流量,就是网络最大流问题.网络系统最大流问题是图与网络理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。一 引言2.问题描述连通网络G(V,A)中有m个节点,n条弧,弧eij上的流量上界为cij,求从起始节点vs到终点
2、vt的最大流量的问题就是最大流问题。3.引例连接某产品产地v1和销地v6的交通网如下：v2v5348v3v1v4v65106111735（a）弧（vi，vj）：从vi到vj的运输线，弧旁数字：这条运输线的最大通过能力—容量。v2v5313v3v1v4v61563222（b）制定一个运输方案，使从v1运到v6的产品数量最多。弧旁数字：运输数量—流量。问题：这个运输网络中，从v1到v6的最大输送量是多少？1、网络与流设一个赋权有向图D=（V,A）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一个弧（v
3、i,vj）∈A,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，A，C）。弧的容量：是对网络上的每条弧(vi,vj)都给出一个最大的通过能力，记为c(vi,vj)或简写为cij。二、基本概念sts’t’对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收点,并将其分别与各发点、收点连起来（见图），就可以转换为只含一个发点和一个收点的网络。所以一般只研究具有一个发点和一个收点的网络流：加在网络各条弧上的一组负载量f(vi,vj)：加在弧(vi,vj)上的负载量简记为fi
4、j，为非负数网络上的流：是指定义在弧集合上的一个函数f={f(vi,vj)},其中f(vi,vj)称为弧（vi,vj)上的流量，流也可看作一个双下标变量弧的流量f(vi,vj)：表示弧(vi,vj)上每单位时间内的实际通过能力弧的容量c(vi,vj)：表示弧（vi,vj)上每单位时间内的最大通过能力零流：网络上所有的fij=0图10-24表示的就是这个网络上的一个流（运输方案），每一个弧上的流量fij就是运输量。例如：f12=1,f13=2,f24=3等等。v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1
5、）（1）（2）fijvt图10-24v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fijvt对于实际的网络系统上的流，有几个显著的特点：(1)发点的净流出量和收点的净流入量必相等。(2)每一个中间点的流入量与流出量的代数和等于零。(3)每一个弧上的流量不能超过它的最大通过能力（即容量）称满足下列条件的流为可行流：（1）容量限制条件：对于每一个弧（vi,vj）∈A有0f(vi,vj)c(vi,vj)（简记为0fijcij）2、可行流与最大流（2）平衡条件：①对于发点vs，有②对于收点
6、vt，有式子中V(f)称为可行流f的流量,即发点的净输出量（或收点的净输入量）。③对于中间点:流入量=流出量。即对每个i(i≠s,t)有f(vi,vj)-f(vj,vi)=0(is，t)(简记为fij-fji=0(is，t))即总流量=发点的净输出量=收点的净输入量容量网络的可行流总是存在的，如当所有弧的流均取零，即对所有的i,j,有f(vi,vj)=0就是一个可行流可行流中fij＝cij的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧。fij＞0的弧为非零流弧，fij＝0的弧叫做零流弧。13(5)9(3)4(1
7、)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)图中为零流弧，都是非饱和弧。就是要求一个流{fij},使其流量v(f)达到最大,并且满足0fijcij网络的最大流:求网络的最大流，即是指满足容量限制条件和平衡条件的条件下，使v(f)值达到最大.容量网络D，若μ为网络中从vs到vt的一条链，给μ定向为从vs到vt，μ上的弧分为两类：凡与μ方向相同的称为前向弧，凡与μ方向相反的称为后向弧，其集合分别用μ+和μ-表示。链的方向：若µ是联结vs和vt的一条链，定义链的方向是从vs到vt。3、增广链s
8、tf10f3>0增广链：f是一个可行流，如果满足：即中的每一条弧都是非饱和弧即中的每一条弧都是非零流弧则称μ为从vs到vt的关于f的一条增广链。stf10f3>0v2v53-34-18-3v3v1v4v65-110-511-66-317-2
