复旦大学：《离散数学——集合与图论》PPT课件（赵一鸣）27/30

82网络最大流 运输网络问题是很大一类网络问题,通 过介绍有些运输网络问题,可以使我们 建立起一些处理网络问题的基本概念和 方法。 这里涉及的运输网络问题只是考虑简单 情况

8.2 网络最大流 运输网络问题是很大一类网络问题，通 过介绍有些运输网络问题，可以使我们 建立起一些处理网络问题的基本概念和 方法。 这里涉及的运输网络问题只是考虑简单 情况

、运输网络 1运输网络的定义 定义87:一个带权有向图G=(,E)若满足如下条件 (1)G是连通无自环的; (2)每条弧(j)的权c为非负整数,称为弧的容量, c全体所构成的集合记为C; (3)存在2个不同的顶点和t 则称该有向图为运输网络,简称网络,记为N(V,E,O) 称s为发点,t为收点,除s和以外其它顶点称为中间点。 C称为容量函数

一、运输网络 1.运输网络的定义 定义 8.7：一个带权有向图G=(V,E)若满足如下条件： (1)G是连通无自环的； (2)每条弧(i,j)的权cij为非负整数，称为弧的容量， cij全体所构成的集合记为C； (3)存在2个不同的顶点s和t。 则称该有向图为运输网络, 简称网络，记为N(V,E,C)。 称s为发点, t为收点, 除s和t以外其它顶点称为中间点。 C称为容量函数

2运输网络N中的流 定义8.8:在网络N(V,E,C)的弧集E上定义了一个非 负整值函数},称为网络N上的流称为弧(i) 上的流量。若无弧(则定义为0。设流瞒满足下 列条件 (1)容量限制条件:对每一条弧(),有 (2)平衡条件:除和t外的每个中间点k有 ∑=∑fk 即流出和等于流入和。 对于s和t有22=2/21=V 则称f为网络N的一个可行流,V为流f值,或称f 流量 若N中无可行流∫,使vr>V则称为最大流

2.运输网络N中的流 定义 8.8：在网络N(V,E,C)的弧集E上定义了一个非 负整值函数f={fij}, 称f为网络N上的流, fij称为弧(i,j) 上的流量。若无弧(i,j), 则fij定义为0。设流f满足下 列条件: (1)容量限制条件：对每一条弧(i,j), 有fij≤cij。 (2)平衡条件：除s和t外的每个中间点k, 有 即流出和等于流入和。 对于s和t有 则称f为网络N的一个可行流, Vf为流f的值, 或称f的 流量。 若N中无可行流f', 使Vf'>Vf , 则称f为最大流。     = j V jk i V ki f f f i V ti j V jt j V js i V  f si −  f =  f −  f =V    

108 64 1010 66 4.4 t 4 74 103 定义89:若c,则称弧(动是饱和的;若 f则称弧()是未饱和的。若G则称弧 (i)是f0的;若島>0,则称弧()是/正的 现在的关键是如何求最大流的值

定义 8.9：若fij=cij, 则称弧(i,j)是饱和的; 若 fij0, 则称弧(i,j)是f-正的. 现在的关键是如何求最大流的值

3运输网络N中的割 定义8.10:设N(V,E,O是有一个发点s和一个收点t 的网络若V划分为P和,使S∈P,t∈P,则从P中 的点到P中的点的所有弧集称为分离s和t的割, 记为(P,P)。 如图8.6中虚线所示,P={s,a,c},P={b,t 若从网络N中删去任一个割,则从s到t之间不存 在有向路。 要说明的是,对同一s,割不唯一

3.运输网络 N 中的割 定义 8.10:设 N(V,E,C)是有一个发点 s 和一个收点 t 的网络。若 V 划分为 P 和P , 使 sP,t P ,则从 P 中 的点到P 中的点的所有弧集称为分离 s 和 t 的割, 记为(P, P )。 如图 8.6 中虚线所示, P={s,a,c}, P ={b,t}。 若从网络 N 中删去任一个割, 则从 s 到 t 之间不存 在有向路。 要说明的是,对同一 s,t,割不唯一

割(P,P)的容量是它的每条孤的容量之和记为C,) 即 C(P,P)=∑ t∈P,j∈P 对于不同的割它的容量显然是不同的。 对网络中N中的割(P,P),若不存在割(P,P)使 C(P,P)<C(P,P,则称(P,P)为最小割。 讨论网络中流与割的关系

割(P,P )的容量是它的每条弧的容量之和,记为 C(P,P ) 即:    = i P j P ij C P P c , ( , ) 对于不同的割, 它的容量显然是不同的。 对网络中 N 中的割(P, P ),若不存在割(P', P' )使 C(P', P')< C(P, P ),则称(P, P )为最小割。 讨论网络中流与割的关系

4运输网络中流和割的关系 定理84对于给定的网络N=(V,E,C,对任 一可行流∫和任一割(),成立v C(P P 证明:因为∫是可行流,根据流的平衡条件 可知: 对于发点s∈P有 多 ∑fs-∑fs= 多J∈ 对于P中不是发点s和收点t的中间点k有 ∑f=∑f ∑/-∑/k=0(2)

4.运输网络中流和割的关系 定 理 8.4:对于给定的网络 N=(V,E,C), 对 任 一可行流 f 和任一割 (P,P ), 成 立 Vf C(P,P )。 证明：因为 f 是可行流，根据流的平衡条件 可知： 对于发点 sP 有 f j V js i V  f s i −  f =V   （1） 对于 P 中不是发点 s 和收点 t 的中间点 k 有     = j V j k i V ki f f  −  = 0  jV jk i V k i f f （2）

此定理给出了流f的上界C(P,P)。 由于对任意的流和割都有Ⅴ ≤C(PP), 因此一定有 Vimaxscmin'(P,P)

此定理给出了流 f 的上界 C(P, P )。 由于对任意的流和割都有 Vf C(P, P )， 因此一定有 VfmaxCmin(P, P )

二、最大流最小割定理 引理:对于给定的网络N=(,E,C),若可 行流和割(PvP,成立=C(PVP),则 Vimax=V Cmin(P,V-P)=C(P, V-P) 因此求最大流的一个想法就是构造流和 割,使得流量和割容量相等

二、最大流最小割定理 引理：对于给定的网络N=(V,E,C), 若可 行流f和割(P,V-P), 成立Vf=C(P,V-P)，则 Vfmax=Vf，Cmin(P,V-P)=C(P,V-P)。 因此求最大流的一个想法就是构造流和 割，使得流量和割容量相等

福特,富克逊(Frod, Fulkerson)于1956年 给出的最大流最小割定理 基本思想: 1)对任意网络构造初始流。 零流,或其他可行流。 2)在初始流基础上寻找可增加流的路, 这样的路称为增广路。并在寻找增广路 的同时,计算在该路上可增加多少流。 2 3)若找到了从到t的可增加流的路,则 修改流,得到新的可行流。然后转回2)

福特,富克逊(Frod,Falkerson)于1956 年 给出的最大流最小割定理 基本思想： 1）对任意网络构造初始流。 零流,或其他可行流。 2）在初始流基础上寻找可增加流的路， 这样的路称为增广路。并在寻找增广路 的同时，计算在该路上可增加多少流。 3）若找到了从s到t的可增加流的路，则 修改流，得到新的可行流。然后转回2）