[2018年必威体育精装版整理]04最大流.pptVIP

引言 引言 可行流： 1.每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；2.中间点的流量为零。 因为对于每个点，运出这点的产品总量与运进这点的产品总量之差，是这点的净输出量，简称为是这一点的流量；由于中间点只起转运作用，所以中间点的流量必为零。易见发点的净流出量和收点的净流入量必相等，也是这个方案的总输送量。因此有： 可行流总是存在的。比如令所有弧的流量fij=0，就得到一个可行流(称为零流)。其流量v(f)=0。 最大流问题就是求一个流｛fij｝使其流量v(f)达到最大，并且满足： 0≤fij≤cij (vi，vj)∈A ① ② 最大流问题是一个特殊的线性规划问题。即求一组｛fij｝，在满足条件①和②下使v(f)达到极大。将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。 不难证明，任何一个可行流的流量v(f )都不会超过任一截集的容量。即 v(f )≤C 显然，若对于一个可行流f *，网络中有一个截集 ，使v(f *)=C ，则f*是最大流，而 必定是D的所有截集中，容量最小的一个，即最小截集。 由上述可见，用标号法找增广链以求最大流的结果，同时得到一个最小截集。最小截集容量的大小影响总的输送量的提高。因此，为提高总的输送量，必须首先考虑改善最小截集中各弧的输送状况，提高它们的通过能力。另一方面，一旦最小截集中弧的通过能力被降低，就会使总的输送量减少。 最大流问题的应用 运输网络的用途不限于解决运输问题。例如求一个二部图G=〈X,E,Y〉的最大匹配问题,可转化为运输网络求解。方法是把X的元素都看作源点,Y的元素都看作阱点,边的方向都是从源点指向阱点,再用上述方法,虚设一个源点a和一个阱点z,并设所有边的权均为1。对所得的图求得最大流的值就是最大匹配的边数,最大流通过的属于E的边集,就是最大匹配。 思考题 四个人：张三、李四、王五、赵六，四种乐器：小提琴、大提琴、钢琴、吉他。 已知四人的擅长如下： 张三擅长拉大提琴和弹钢琴； 李四擅长拉小提琴、大提琴和吉他； 王五擅长拉小提琴、大提琴； 赵六只会弹吉他。 今假设四人同同台演出，每人各奏一种乐器，问四人同时各演奏一种乐器时所有可能的方案，试把此问题化为最大流问题。 结点的容量约束 在由顶点容量约束的网络最大流问题中，除了需要满足边容量约束外，在网络的某些顶点处还要满足顶点容量约束，即流过该顶点的流量不能超过给定的约束值。 转换这类问题成标准的最大流问题需要拆点。把点v拆为两个点v’,v’’。那所有连接到v的边变为连接到v’的边，所有从v出去的边变成从v’’出去的边。边(v’,v’’)的流量就是点v的流量。 带下界约束的最大流问题 解决这种问题分两个阶段： 第一个阶段先找满足约束条件的可行流，第二个阶段把找到的可行流扩展成最大流。 带下界约束的最小流问题 与带上下界约束的最大流问题相似，分两个阶段。 第一个阶段求出满足约束条件的循环可行流，第二个阶段反向增流就求得最小流。 1 2 S T 2,6 3,7 3,4 1 2 S T 4 4 1 2 3 3 1 2 S T 4 4 1 2 3 3 1 2 S T 4 4 1 2 3 3 X Y 2 3 3 * 上图是联结某产品产地v1和销地v6的交通网，每一弧(vi，vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数字表示这条运输线的最大通过能力。产品经过交通网从v1输送到v6。现在要求制定一个运输方案使从v1运到v6的产品数量最多。 给出了一个运输方案，每条弧旁的数字表示在这个方案中，每条运输线上的运输数量。这个方案使8个单位的产品从v1运到v6，在这个交通网上输送量是否还可以增多，或者说这个运输网络中，从v1到v6的最大输送量是多少呢? 网络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)为