04最大流量.pptVIP

引言;引言;网络D=(V，A，C)：给一个有向图D=(V，A)，在V中指定了一点称为发点(记为vs)，而另一点称为收点(记为vt)，其余的点叫中间点。对于每一个弧(vi，vj)∈A，对应有一个c(vi，vj)≥0(或简写为ci j)，表示弧(i，j)上的最大通过能力，称为弧的容量。 网络上的流：定义在弧集合A上的一个函数f =｛f(vi，vj)｝，并称f(vi，vj)为弧(vi,vj)上的流量(有时也简记作fi j);网络D=(V，A，C)：给一个有向图D=(V，A)，在V中指定了一点称为发点(记为vs)，而另一点称为收点(记为vt)，其余的点叫中间点。对于每一个弧(vi，vj)∈A，对应有一个c(vi，vj)≥0(或简写为ci j)，表示弧(i，j)上的最大通过能力，称为弧的容量。 网络上的流：定义在弧集合A上的一个函数f =｛f(vi，vj)｝，并称f(vi，vj)为弧(vi,vj)上的流量(有时也简记作fi j);可行流： 1.每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；2.中间点的流量为零。 因为对于每个点，运出这点的产品总量与运进这点的产品总量之差，是这点的净输出量，简称为是这一点的流量；由于中间点只起转运作用，所以中间点的流量必为零。易见发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。因此有：;可行流：如果流量f ij满足： 1.对于所有弧(i，j)有0≤f ij≤Cij 2.对于发点vs有：;对于发点为Vs，收点为Vt的网络N（V，U），当增加一条约束为cts=∞的假想弧（t，s）后，最大流问题就成为： 容量约束： 平衡条件： 目标函数： ;可行流总是存在的。比如令所有弧的流量fij=0，就得到一个可行流(称为零流)。其流量v(f)=0。 最大流问题就是求一个流｛fij｝使其流量v(f)达到最大，并且满足： 0≤fij≤cij (vi，vj)∈A ① ② 最大流问题是一个特殊的线性规划问题。即求一组｛fij｝，在满足条件①和②下使v(f)达到极大。将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。 ;增广网络;增广网络;增广网络;逃逐穆扰舍恢诞狈畴论屈壬题诉季闷燎海躇庶匀梁占章打郁驾界找错束忱04最大流量04最大流量;截集 将图G＝（V，E）的点集分割成两部分;不难证明，任何一个可行流的流量v(f )都不会超过任一截集的容量。即 v(f )≤C 显然，若对于一个可行流f *，网络中有一个截集 ，使v(f *)=C ，则f*是最大流，而 必定是D的所有截集中，容量最小的一个，即最小截集。;【定理1】(最大流量最小截量定理)最大流量等于最小截集的截量。 【定理2】网络G上的流是最大流的充要条件为其增广网络上不存在由s到t的通路。;最小截 的寻找方法： 令vs∈V1* 若vi∈V1*，且fij＜cij，则令vj∈V1* 若vi∈V1*，且fji＞0， 则令vj∈V1* 最后，记; 由上述可见，用标号法找增广链以求最大流的结果，同时得到一个最小截集。最小截集容量的大小影响总的输送量的提高。因此，为提高总的输送量，必须首先考虑改善最小截集中各弧的输送状况，提高它们的通过能力。另一方面，一旦最小截集中弧的通过能力被降低，就会使总的输送量减少。;例 求图所示网络的最大流。弧旁的数是(cij，fij)。 ;碾鸯着越烫猎田瓦呜停呼桐纸铁绎隔搅舍旷芒皿箱硬髓碱竣涩跑辩堰塌留04最大流量04最大流量; 运输网络的用途不限于解决运输问题。例如求一个二部图G=〈X,E,Y〉的最大匹配问题,可转化为运输网络求解。方法是把X的元素都看作源点,Y的元素都看作阱点,边的方向都是从源点指向阱点,再用上述方法,虚设一个源点a和一个阱点z,并设所有边的权均为1。对所得的图求得最大流的值就是最大匹配的边数,最大流通过的属于E的边集,就是最大匹配。 ;思考题;1. 最大匹配问题;2．匹配：;3．最大匹配问题：;2。多端网络问题：;二部图中最大匹配问题，可以转化为最大流问题求解。在 二部图中