《网络最大流问题》.ppt

课程讲授：黄玉诚;第六章 图与网络分析;第四节 网络最大流问题;③;一、基本概念与基本定理;2、可行流与最大流;对于发点vs， ; 所谓最大流问题就是在网络中，寻找流量最大的可行流，即：求一个流{fij}使其流量v(f)达到最大，并且满足 0≤fij≤cij (vi，vj)∈A;3、增广链; 定义3 设f是一个可行流，μ是从vs到vt的一条链，若μ满足下列条件,称之为(关于可行流 f 的)一条增广链。 在弧(vi，vj)∈μ+上，0≤fijcij，即μ+中每一弧是非饱和弧。 在弧(vi，vj)∈μ-上，0fij≤cij，即μ-中每一弧是非零流弧。;4、截集与截量 ;定义5 给一截集(V1, )，把截集(V1, )中所有弧的容量之和称为这个截集的容量(简称为截量)，记为c(V1, )，即 ; 显然，若对于一个可行流f*，网络中有一个截集(V1*, )，使v(f*)= c(V1*, ), 则f*必是最大流，而(V1*, )必定是D的所有截集中容量最小的一个，即最小截集。 ;定理1 可行流f*是最大流的充分必要条件是不存在从vs到vt的(关于f*)增广链。;由增广链的定义，可知θ0, 令网络上的另一个流：; (二) 充分性：若不存在关于f*增广链，那么f*是最大流。 ;显然有; 最大流量最小截量定理：任一个网络D中，从vs到vt的最大流的流量等于分离vs，vt的最小截集的容量。 ;寻求最大流的思路：利用定理1中对V1*定义，根据vt是否属于V1*来判断D中有无关于f的增广链。;二、寻求最大流的标号法 ; 在标号过程中，网络中的点分为两类： (1)标号点(又分为已检查和未检查两种)。每个标号点的标号内容包含两部分：标号的第一部分表明它的标号是从哪一点得到的，以便找出增广链；标号的第二部分是为确定增广链的调整量θ用的。 (2)未标号点。;标号过程:; 若vt未获得标号，而标号过程无法进行时，则算法结束，这时的可行流 f 就是最大流。; 例如：设vt的第一个标号为vk，则弧(vk ,vt ) 是μ上的弧。接下来检查vk的第一个标号，若为vi，则找出(vi,vk) 。再检查vi的第一个标号，依此下去，直到vs为止。这时被找出的弧就构成了增广链μ。; (2) 在增广链上调整流量。;例 用标号法求图10-25所示网络的最大流???弧旁的数是 (cij ,fij) 。;(2) 检查vs。;(3) 检查v1。;(4) 检查v2。 ;(5) 在v3, v4中任选一个进行检查。;(二) 调整过程 ;(v4,1);(v4,1);vs;vs;vs;vs;这时的可行流即为所求最大流。最大流量为： v(f)=fs1+fs2=f4t+f3t＝5。 ;vs; 由此，也可以体会到最小截集的意义。网络从发点到收点的各通路中，向容量决定其通过能力，最小截集则是这些路中的咽喉部分，或者叫瓶颈，其容量最小，它决定了整个网络的最大通过能力。要提高整个网络的运输能力，必须首先改进这个咽喉部分的通过能力。;2022/4/13;8;③;③;③;8;③;8;8;由增广链的定义，可知θ0, 令网络上的另一个流：;8