ch6.4 最大流.ppt

网络的最大流 (5) 修改增广链上的流量，非增广链上的流量不变，得到新的可行流。 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(6) 3(2) 1(1) 4(3) 3(2) 5(3) 4(4) 2(2) 7(6) 8(5) ● (∞) (4) (1) (1) (1) 网络的最大流 (6) 擦除原标号 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(7) 3(2) 1(1) 4(3) 3(3) 5(4) 4(4) 2(2) 7(6) 8(6) ● (∞) (4) (1) (1) (1) 网络的最大流 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(7) 3(2) 1(1) 4(3) 3(3) 5(4) 4(4) 2(2) 7(6) 8(6) ● (∞) (1) (1) (2) (7) 重新搜寻增广链。 存在增广链：s→v5→v3→ t 网络的最大流 (8) 调整增广链上的流量，非增广链流量不变，得到新的可行流 s t v1 v2 v3 v4 v5 4(3) 3(2) 10(7) 3(2) 1(1) 4(3) 3(3) 5(4) 4(4) 2(2) 7(6) 8(6) ● (∞) (1) (1) (1) 网络的最大流 s t v1 v2 v3 v4 v5 4(3) 3(3) 10(7) 3(2) 1(1) 4(3) 3(3) 5(5) 4(4) 2(2) 7(6) 8(7) ● (∞) (1) (1) (1) (9) 擦除原标号 网络的最大流 s t v1 v2 v3 v4 v5 4(3) 3(3) 10(7) 3(2) 1(1) 4(3) 3(3) 5(5) 4(4) 2(2) 7(6) 8(7) ● (10) 重新标号，有哪些信誉好的足球投注网站增广链 (∞) (1) (1) (1) (1) 存在增广链：s→v1→v5→v4→t 网络的最大流 s t v1 v2 v3 v4 v5 4(3) 3(3) 10(7) 3(2) 1(1) 4(3) 3(3) 5(5) 4(4) 2(2) 7(6) 8(7) ● (∞) (1) (1) (1) (1) (11) 调整增广链上的流量，非增广链流量不变，得到新的可行流 网络的最大流 s t v1 v2 v3 v4 v5 4(4) 3(3) 10(7) 3(3) 1(1) 4(4) 3(3) 5(5) 4(4) 2(2) 7(7) 8(7) ● (∞) (1) (1) (1) (1) (11) 擦除标号，在新的可行流上重新标号。 网络的最大流 s t v1 v2 v3 v4 v5 4(4) 3(3) 10(7) 3(3) 1(1) 4(4) 3(3) 5(5) 4(4) 2(2) 7(7) 8(7) ● (∞) (11) 擦除标号，在新的可行流上重新标号。 (3) 无法标号，不存在增广链，此可行流已为最大流。最大流量为14。 第四节 网络的最大流 网络的最大流 如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。 网络的最大流 基本概念： 1. 容量网络：网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。 s ① ② ③ ④ t 4 8 4 4 1 2 2 6 7 9 网络的最大流 2. 流与可行流 流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量（实际流量）记为fij。 若fij=0，称为零流弧； 若fij=cij，称为饱和弧。 满足以下条件的一组流称为可行流： 容量限制条件： 所有的弧满足 0≤fij≤cij 平衡条件： 中间点的流量为0（ 流入量 = 流出量） 发点的净流出量 = 收点的净流入量 网络的最大流 结论：任何网络上一定存在可行流。（零流即是可行流） 网络最大流问题： 指满足容量限制条件和平衡条件下，使v(f)值达到最大。 3. 网络的最大流 是指网络中从发点到收点之间允许通过的最大流量。 网络的最大流 4. 增广链 在网络的发点和收点之间能找到一条链，在该链上所有指向为s→t的弧，称为前向弧，记作 μ+,存在 fc ；所有指向为t→s的弧，称为后向弧，记做 μ－，若 f0，则称这样的链为增广链。例如下图中，s→v2→v1→v3→v4→t。 定理3 网络N中的流 f 是最大流当且仅当N中不包含任何增广链 网络的最大流 ● s t v1 v3 v2 v4 8(8) 9(4) 5(5) 10(8) 6(1) 2(0) 9(9) 5(3) 7(5) 网络的最