§4网络最大流问题 廿许多系统都包含了流量问题。例如公路系统中有车辆流，控制 系统有信息流，供水系统有水流等等。 现在考虑这样一个问题：某物资有m个生产基地A1,A2,.,Am 要通过铁路运到n个销地B1,B2,.,B,去。把铁路网上的车站看 作是顶点，两个车站间的铁路线看作是弧。可以认为在某条铁路线 上可运送的物资数量是有限的，我们把某条线路上的允许最大运送 量称为容量。这时要考虑如何安排运输方案，使得由产地运到销地 的物资总量达到最大。这就是在这个运输网中，求最大流问题。 4.1网络最大流概念 容量网络：在有向图D=(V,A),指定一个点为发点，记作 巴，指定另一个点为收点，记作，其余点叫作中间点。对于A的每 条弧(，y,),都对应一个权数C≥0，称为弧(，v)的容量，将这 样的赋权有向图叫作一个容量网经，记作D=(V,AC)
§4 网络最大流问题 许多系统都包含了流量问题。例如公路系统中有车辆流，控制 系统有信息流，供水系统有水流等等。 现在考虑这样一个问题：某物资有m个生产基地A1，A2，…，Am 要通过铁路运到n个销地B1，B2，…，Bn去。把铁路网上的车站看 作是顶点，两个车站间的铁路线看作是弧。可以认为在某条铁路线 上可运送的物资数量是有限的，我们把某条线路上的允许最大运送 量称为容量。这时要考虑如何安排运输方案，使得由产地运到销地 的物资总量达到最大。这就是在这个运输网中，求最大流问题。 4.1 网络最大流概念 容量网络：在有向图D=（V，A），指定一个点为发点，记作 vs ，指定另一个点为收点，记作vt ，其余点叫作中间点。对于A的每 条弧（vi ,vj），都对应一个权数cij ≥0，称为弧（vi ,vj）的容量，将这 样的赋权有向图叫作一个容量网络，记作D=（V,A,C）
如果在一个网络中，有多个发点或收点，则我们可以将其 变为只有一个发点和收点的网络。这只需增加一个新的总 发点和一个新的总收点。从总发点到各个发点分别连接 条容量为+∞的弧，从各个收点到总收点分别连接一条容量 为+∞的弧。这样就可将问题变为单发点和单收点的网络流 问题。所以，以后我们只讨论一个发点和一个收点的网络流问题。 在网络中，将通过弧(，？)的运量记作f,并称之为弧(，马) 上的流量。 可行流：对于容量网络D=(V,A,C),每条弧(，v)都给 定一个流量f,当f}满足下列条件时，称为可行流 1°容量限制：对每条弧(，y)∈A,有0≤fc 2°平衡条件：对于中间点v,∈V,流入量等于流出量，即 对于发点，和收点，则有，发出总量等于，收到总量，即 g∑f-∑=f) 称vf)为可行流f}的流量
如果在一个网络中，有多个发点或收点，则我们可以将其 变为只有一个发点和收点的网络。这只需增加一个新的总 发点和一个新的总收点。从总发点到各个发点分别连接一 条容量为+∞的弧，从各个收点到总收点分别连接一条容量 为+∞的弧。这样就可将问题变为单发点和单收点的网络流 问题。所以，以后我们只讨论一个发点和一个收点的网络流问题。 在网络中，将通过弧（vi ,vj）的运量记作f ij，并称之为弧（vi ,vj） 上的流量。 可行流：对于容量网络D=（V，A，C），每条弧（vi ,vj）都给 定一个流量 f ij ，当｛f ij｝满足下列条件时，称为可行流。 1°容量限制：对每条弧（vi ,vj）∈A，有0≤ f ij≤cij 2°平衡条件：对于中间点vi ∈V，流入量等于流出量，即 ∑f ji=∑f ij 对于发点vs 和收点vt ，则有vs 发出总量等于vt 收到总量，即 ∑f sj -∑f js= ∑f jt - ∑f tj =v(f ) 称v(f )为可行流｛f ij｝的流量。 j j j j j j
如图7-15中，弧旁的数字分别为(c,)，可以验证 给出的流是可行流。 对于任何网络总是存在可行流的，比如令所有弧上的 流都等于0，就可以得到一个可行流，其流量y(f)=O。 最大流：使v()达到最大的可行流称为最大流。 (4,3) (3,3 1,1) 5,3) 1,1 (3,0)PV 2,1) (2,2) 图7-15
如图7-15中，弧旁的数字分别为（cij ，f ij），可以验证 给出的流是可行流。 对于任何网络总是存在可行流的，比如令所有弧上的 流都等于0，就可以得到一个可行流，其流量v(f ) =0。 最大流：使v(f )达到最大的可行流称为最大流。 ° ° ° ° ° ° vs vt v1 v2 v3 v4 （3，3） （4，3） （5，1） （1，1） （1，1） （5，3） （3，0） （2，1） （2，2） 图7-15
4.2计算最大流的标号法 这里介绍计算网络最大流的简便方法一标号法，此方法 是Ford一Fulkerson于1956年提出来的，它的原理是利用寻 找增广链来不断改善可行流。 设u是网络中v,到v,的一条链，规定，到v,的方向为u的方向。u 上与的方向一致的弧称为前向弧，前向弧的集合记为+，u上与4 的方向相反的弧称为后向弧，后向弧的集合记为。 (4,3) (3,3 (1,1) 5,3) 2。 (1,1) (3,0)V (5,1） 2,1) V2 (2,2) 04 图7-15 上图，链{2}上u+={(V,2),（v,V）,（3 )} ={V1,V2
4.2 计算最大流的标号法 这里介绍计算网络最大流的简便方法—标号法，此方法 是Ford—Fulkerson 于1956年提出来的，它的原理是利用寻 找增广链来不断改善可行流。 设μ是网络中vs 到vt 的一条链，规定vs 到vt 的方向为μ的方向。 μ 上与μ的方向一致的弧称为前向弧，前向弧的集合记为μ＋ ，μ上与μ 的方向相反的弧称为后向弧，后向弧的集合记为μ-。 ° ° ° ° ° ° vs vt v2 v4 （3，3） （4，3） （5，1） （1，1） （1，1） （5，3） （3，0） （2，1） （2，2） 图7-15 上图，链｛vsv2v1v3vt｝上 μ＋=｛（vs，v2），（v1，v3）， （v3， vt ）｝ μ- =｛v1，v2｝。 v1 v3
若给一个可行流f},称网络中f=c的弧为饱和弧， 称f≤c,的弧为非饱和弧，称f=0的弧为零流弧，称f>0 的弧为非零流弧。 增广链：设(f)是可行流，u是v,到v,的一条链，若满足下 列条件，则称为关于f的增广链。（注意：f=f)}) 1°对于任何(，)∈+，0≤0，令 f0, （,y)∈u+ f*- f*-0, (v,∈0 ,y)∈u
若给一个可行流｛f ij｝，称网络中 f ij =cij 的弧为饱和弧， 称 f ij＜ cij 的弧为非饱和弧，称f ij =0的弧为零流弧，称f ij＞0 的弧为非零流弧。 增广链：设｛f ij｝是可行流，μ是vs 到vt 的一条链，若μ满足下 列条件，则称μ为关于 f 的增广链。（注意： f =｛f ij｝） 1°对于任何（vi ,vj）∈μ＋ ，0≤ f ij ＜ cij （前向弧为非饱和弧） 2°对于任何（vi ,vj）∈μ -，0 ＜ f ij ≤ cij （后向弧为非零流弧） 如图7-15中，μ=｛vsv2v1v3vt｝就是一条增广链。 定理：可行流 f﹡是最大流，当且仅当不存在关于 f﹡的增广链。 证明：必要性：设f﹡是最大流，若存在关于 f﹡的增广链μ，令 则θ ＞0，令 +θ， （vi ,vj）∈μ＋ = -θ， （vi ,vj）∈μ - ， （vi ,vj）∈μ = − + − ij vi v j μ ij ij vi v j μ θ min min c f , min f fij fij fij fij
不难验证f*)仍是可行流，且v(f*)=(f)+0>v() 这与是最大流矛盾。所以当∫是最大流时，不会存在关 于的增广链。 充分性：证明略。 这个定理为我们提供了确定最大流的方法。对于一个可行流 如果不存在关于∫的增广链，则f就是最大流。反之，如果存在增 广链，则按照定理必要性证明的方法，可以改进可行流f,得到另 个流量增大的可行流。 我们下面介绍的标号法，就是一种通过搜索增广链，不断改进可 行流，直至求得最大流的方法。 标号法： 在标号法中，网络中的点可分为三类： ①标了号且检查过的点；②标了号但未检查的点：③未标号点。 前两种都称为标号点，对于标号点，它的标号包含两部分内容， 第一部分指出v的紧前点，第二部分表示从v,到y的可能调整量，记 为L()
不难验证｛ ｝仍是可行流，且v( f﹡﹡)=v( f﹡)+θ＞ v( f﹡)。 这与 f﹡是最大流矛盾。所以当 f﹡是最大流时，不会存在关 于 f﹡的增广链。 充分性：证明略。 fij 这个定理为我们提供了确定最大流的方法。对于一个可行流 f 如果不存在关于 f 的增广链，则 f 就是最大流。反之，如果存在增 广链，则按照定理必要性证明的方法，可以改进可行流 f ，得到另 一个流量增大的可行流。 我们下面介绍的标号法，就是一种通过搜索增广链,不断改进可 行流，直至求得最大流的方法。 标号法： 在标号法中，网络中的点可分为三类： ①标了号且检查过的点；②标了号但未检查的点； ③未标号点。 前两种都称为标号点，对于标号点vj ，它的标号包含两部分内容， 第一部分指出vj 的紧前点，第二部分表示从vs 到vj 的可能调整量，记 为L（vj）
标号法从一个可行流∫出发（若网络中没有给定∫，则 可以设f是零流)，反复经过标号过程与调整过程来寻找最 大流。 一标号过程 1°标U,(0,+),这时v,成为标了号但未检查的点，其余点都 是未标号点。 2°从标了号但未检查的点四出发，给它相邻的未标号点v标号： 若（，g)上f0,则标V(-,L()) 这里从o,到v,的可能调整量L(v)=min{L(v,),f) 上述标号过程结束后，，便成为标了号且检查过的点，而获得标号 的v成为标了号但未检查的点。 3°重复2。，直至标号进行不下去，或获得标号为止。 若标号进行不下去，则现在的可行流已是最大流，计算停止。 若v,获得标号，则意味着已找到一条从v,到v的增广链，转（白
标号法从一个可行流 f 出发（若网络中没有给定 f ，则 可以设 f 是零流），反复经过标号过程与调整过程来寻找最 大流。 ㈠标号过程 1°标vs （0，+∞），这时vs 成为标了号但未检查的点，其余点都 是未标号点。 2 °从标了号但未检查的点vi 出发，给它相邻的未标号点vj 标号： 若（vi ,vj）上 f ij ＜ cij ，则标vj（vi ， L（vj））。 这里L（vj）=min｛L（vi）, cij-f ij｝表示从vs 到vj 的可能调整量。 若（vj ,vi）上 f ji＞0 ，则标vj（-vi ， L（vj））。 这里从vs 到vj 的可能调整量L（vj）=min｛L（vi）, f ji｝。 上述标号过程结束后，vi 便成为标了号且检查过的点，而获得标号 的vj 成为标了号但未检查的点。 3 °重复2 °，直至标号进行不下去，或vt获得标号为止。 若标号进行不下去，则现在的可行流已是最大流，计算停止。 若vt 获得标号，则意味着已找到一条从vs 到vt 的增广链，转㈡
(白)调整过程 首先，按v,的标号的第一部分，反向追踪，找出增广链， 确定调整量0=L(v,)。 然后令 +0, （V,Y）∈u 下=f, ∈ （g,y)∈4 去掉所有标号，对新的可行流于)再进行标号过程()
㈡调整过程 首先，按vt 的标号的第一部分，反向追踪，找出增广链μ， 确定调整量θ= L（vt ）。 然后令 f ij+θ， （vi ,vj）∈μ＋ = f ij-θ， （vi ,vj）∈μ - f ij ， （vi ,vj）∈μ 去掉所有标号，对新的可行流｛ ｝再进行标号过程 ㈠。 f ij _ ij f _
例5用标号法求图7-15所示网络的最大流。 解：标V(0,+o) 标2（v,L(2))=(,min{+oo,c2f2})=(v4) 标v,(-v2,L（v,))=(-v2,min{L(v2),f2})=(-v21） V, (4,3) 标U（v,L(,)) (3,3) (1,1) 5,3) =3（1,1) V.o 标v,(-,L(v4)） 1,1) (3,0)PV: =V4（-Y,1） (5,1) 2,1) 标v(,L(,)) 图7-15 (2,2) =V(V3,1) V (4,4) V, 得增广链：0，→V-V,→V→： (3,3) 调整量0L(4,)=1 1,1) 5,4)调整可行流结果如图7-16。 ,% 1,0) (3,0)PV 再标V(0,+o) (2,1) 标v2(v,3) (5,2 至此标号进行不下去，最大流即 V2 2,2） 图7-16 如图7-16所示，最大流量v(f)=5
例5 用标号法求图7-15所示网络的最大流。 ° ° ° ° ° ° vs vt v1 v2 v3 v4 （3，3） （4，3） （1，1） （1，1） （5，3） （3，0） （2，1） 图7-15 （2，2） （5，1） 解：标vs （0，+∞） 标v2（vs ,L（v2））=（vs ,min｛+∞,cs2-f s2｝)=（vs ,4） 标v1（-v2 ,L（v1））=（-v2 ,min｛L（v2）, f 12｝）=（-v2 ,1） 标v3（v1 ，L（v3）） =v3（v1 ，1） 标v4（-v1 ，L（v4）） =v4（-v1 ，1） 标vt（v3 ，L（vt）） =vt（v3 ，1） 得增广链：vs →v2←v1→v3→vt ° ° ° ° ° ° vt v2 v4 （4，4） （1，0） （1，1） （5，4） （3，0） （2，1） （2，2） 图7-16 调整量θ= L（vt）=1 v1 （3，3） vs （5，2） v3 调整可行流结果如图7-16。 再标vs （0，+∞） 标v2（vs ，3） 至此标号进行不下去，最大流即 如图7-16所示，最大流量v(f ) =5