图论第四节

null图与网络分析图与网络分析第四节 最大流问题null 第四节 网络最大流问题例 连接某产品产地v1和销地v6的交通网如下：弧（vi，vj）：从vi到vj的运输线， 弧旁数字：这条运输线的最大通过能力,制定一个运输，使从v1到v6的产品数量最多。null弧旁数字： 运输数量。问题：这个运输网络中，从v1到v6的最大输送量是多少？null一、基本概念与定理1. 网络与流定义1 给定一个有向图D=（V，A），在V中指定 一点vs 称为发点，指定另一点vt 称为收点， 其余点称中间点。任意弧(vi ，vj )∈A，有 cij ≥0，称为弧的容量。称D为一个容量网 络。记为D=（V，A，C）。流: 定义在弧集A上的一个函数f={f(vi ,vj )}，并称 f(vi ,vj )为弧(vi ,vj )上的流量。简记 f = {fi ,j } null弧旁数字： 容量弧旁数字： 流量nullnull2. 可行流与最大流定义2 满足下述条件的流 f 称为可行流:1)容量限制条件: 对每一弧(vi , vj )∈A 0≤fij ≤cij2)平衡条件: 对中间点vi (i≠s,t ),有 V( f ) 称为可行流 f 的流量,即发点的净输出量。如所有fij=0， 零流。可行流总是存在的null3. 增广链对可行流 f ={ fij }：非饱和弧：fij < cij饱和弧：fij =cij非零流弧：fij >0零流弧：fij =0 链的方向：若µ是联结vs和vt的一条链，定义链的方向是从vs到vt 。 前向弧：弧的方向与链的方向一致，记为µ+。后向弧：弧的方向与链的方向相反，记为µ-。nullµ = (v1,v2,v3,v4,v5,v6 )µ+={(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6)}µ - ={(v5,v4)}null定义3 设 f 是一个可行流, µ 是从vs 到vt 的一条链,若µ满 足下列条件,称之为(关于可行流 f 的)一条增广 链。(vi , vj ) ∈ µ- 0 < fij ≤ cij 后向弧 是非零流弧，(vi , vj ) ∈ µ+ 0≤ fij 0,令这与 f *是最大流的假设矛盾。 null设D中不存在关于f *的增广链，证明f *是最大流。 定义V1 * ，令vs∈V1*, 若vi∈V1*,且弧(vi,,vj)上, fij*0，则令vj∈V1*。null定理2 最大流最小截定理。任一个网络D中，从vs 到 vt 的最大流的流量等于分离vs，vt 的最小截集 的容量。二、寻求最大流的标号法（Ford—Fulkerson） 从任一个可行流 f 出发（若网络中没有给定 f ，则从零流开始），经过标号过程与调整过程。（一）标号过程null标号：（前点标记，前点到该点的弧流量可调整量） 开始，vs 标上（0，∞），vs 是标号未检查的点，其余点都是未标号点，一般地，取一个标号未检查的点vi ，对一切未标号的点vj 。（1）若弧（vi，vj）上，fij0，则给vj 标号(-i， l (vj))，l (vj)=min[l (vi), fji], vj 成为标号而未检查的点。null 重复上述步骤，一旦vt被标号，则得到一条vs到vt的增广链。若所有标号都已检查过，而vt尚未标号，结束，这时可行流，即最大流。（二）调整过程 从vt 开始，反向追踪，找出增广链 µ，并在µ上进行流量调整。（1）找增广链 如vt 的第一个标号为k（或-k），则弧（vk，vt）∈µ（或弧（vt，vk) ∈µ)。检查vk 的第一个标号，若为i（或-i），则(vi,vk) ∈µ (或(vk,vi) ∈µ)。再检查vi 的第一个标号,依此下去,直到vs 。被找出的弧构成了增广链 µ。null（2）流量调整令调整量是 l(vt)，构造新的可行流 f ′， 去掉所有的标号,对新的可行流 f ′={ fij′},重新进入标号过程。null例 用标号法求下图网络的最大流。弧旁的数字是( cij , fij)。解：（一）标号过程。（1）给vs标上（0，∞）；（0，∞）在弧（vs，v2）上， fs2=cs2=3, 不满足标号条件。（s，4）null（3）检查v1，在弧（v2，v1）上，f21>0， 给v2标号 (-1, l(v2)), 在弧（v1，v3）上，f13=2， c13=2，不满足标号条件。（-1，1）（4）检查v2，在弧（v3，v2）上，f32=1>0， 给v3标号 (-2, l(v3)), 这里（-2，1）null在弧（v2，v4）上，f24=3，c24=4，f24