当前位置：文档之家 › 6.04-网络的最大流

6.04-网络的最大流

  • 格式：ppt
  • 大小：799.50 KB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

网络最大流

网络最大流

容量为20 容量为
• 最小截集： • 容量最小截集的称为网络G的最小截集。 • 最大流-最小截集定理： • 在任一个网络D中，从vs到vt的最大流的 流量等于分离的最小截集的容量。
（二）、 求最大流的标号法
标号过程： 1． 给发点vs 标号（0，+∞）。 2． 取一个已标号的点vi，对于vi一切未标号的邻 接点vj 按下列规则处理： （1）如果边 (v j , vi ) ∈ E ，且 f j i > 0 ，那么给vj 标 号 (−vi , δ j ) ，其中： δ j = min( f j i , δ i ) （2）如果边 (vi , v j ) ∈ E ，且 f ij < cij，那么给vj 标号 ( +vi , δ δ j = min(ci j − f i j , δ i ) ，其中：j ) 3．重复步骤2，直到vt被标号或标号过程无法进 行下去，则标号结束。若vt被标号，则存在一条增广 链，转调整过程；若vt未被标号，而标号过程无法进 行下去，这时的可行流就是最大流。
2．去掉所有标号，回到第一步，对可行流 重新标号。
求下图所示网络中的最大流，弧旁数为
v2 (3 , 3) vs (5 , 1) (1 , 1) v1 （-v1, 1） ） v2 (3 , 3) （0，+∞） ， ） vs (5 , 1) v1 （+ vs , 4） ） (2 , 2) (1 ,1) (1 , 1) (3 ,0) (2 ,1) v3 （-v2 ，1） ） (2 , 2) (4 ,3) (1 ,1) (3 ,0) (2 ,1) v3 （+v2，1） ） v4 (5 ,3) v4 (5 ,3) vt
f = f (v i , v j ) = { f i j }

图——网络最大流问题(1)

图——网络最大流问题(1)

运输方案与可行流
一个运输方案就是一个流，但一个可 行流才是一个运输方案，运输方案与可行流 之间存在一一对应关系。
因此，寻找最佳运输方案可以转换为 寻找流量最大的可行流问题。
最大流问题
最大流问题就是求一个流{fij}使其流量 v(f)达到最大，并且满足：
求解最大流的线性规划模型
示例
图
网络上的流
定义 网络上的流，是指定义在弧集合 A上的一个函数f={f(vi,vj)}，
f :AR
这里，称f(vi,vj)为弧(vi,vj)上的流量（简记 为fij）。
示例
图
① 每个弧上的流量不能超过该弧的最 大通过能力（即弧的容量）；
② 由于中间点只起转运作用，因此， 运出该点的产品总量与运进该点的产品总量 必须相等，也就是中间点的流量为零。
流出量等于流入量即一个运输方案就是一个流但一个可行流才是一个运输方案运输方案与可行流之间存在一一对应关系
网络最大流问题(1)
交通网示意图
图
运输方案示意图
网络最大流问题
面临的问题是： 在这个交通网上运送量是否还可以增 加，或者说这个运输网络中，从v1到v6的最 大运送量是多少呢? 这就是所谓的网络最大流问题。
示例
图
可行流
定义 满足下述条件的流f称为可行流： (1) 容量限制条件：对每一弧(vi,vj)∈A， 0≤fij≤cij ；
有缘学习更多＋谓ｙｇｄ３０７６或关注桃报：奉献教育（店铺）
可行流
(2) 平衡条件： 对于中间点：流出量等于流入量，即 对每个i(i≠s,t)有
可行流
对于发点vs，记
对于收点v在V中指定了 一点称为发点(记为vs)，而另一点称为收点 （记为vt），其余的点叫中间点。对于每一 个弧(vi,vj)∈A，对应有一个c(vi,vj)≥0(或简写 为cij)，称为弧的容量。通常就把这样的D叫 作一个网络。记作

网络流基础-最大流最小割定理

网络流基础-最大流最小割定理

⽹络流基础-最⼤流最⼩割定理
最⼤流最⼩割定理，指⽹络流的最⼤流等于其最⼩割。

最⼤流指符合三个性质的前提下，从S到T能流过的最⼤流量。

最⼩割指符合割的定义，最⼩的割容量。

求最⼤流：
不断寻找增⼴路，计算能增加的最⼩流量，然后增加。

找到⼀条增光路，最多能流过2，则：
找到第⼆条路径：
最后还剩a-c-e⼀条，则可计算出最⼤流量为4。

但遇到以下情况，且第⼀条路径为a-b-c-d时，就不⾏了：
此时需要增加反向路径，即当减去增⼴路时，反向加上减去的流量，提供后悔的选择：
这样，当考虑a-c-b-d时，可以对冲掉b-c的流量。

证明：
定理⼀：对于任⼀割和任⼀流，流量等于正向割边流量减去反向割边流量。

即f = f c+ - f c-，其中c+代表正向割边流量。

推论：任⼀割容量必定⼤于等于任⼀流量，由于：C+ > f c+ > f c+ - f c- > f。

则如果存在某流量和某割，则此流量必定为最⼤流，此割必定为最⼩割。

当我们计算出最⼤流时，不妨思考下此时的残留⽹络：
此时残留⽹络不存在增⼴路，即不存在⼀条能从S到T的路径。

此时残留⽹络中，我们把S能到达的节点记为s'集，能到达T的节点记为t’集，则s'和t'构成割集。

在残留⽹络中，流量指容量为0的边（满流），⽽这些边⼜是割边，所以流量和等于割的容量和。

⽐如对于：
其⼀个残留⽹络为：
其中两条虚线边为满流的边，也是割边。

网络流——求网络最大流

网络流——求网络最大流

4 1 4 8
4 2 2 6
7
9
(1,4) V2 (0,+∞) V1
(2,4) V4 (4,4) V6
(1,8)
V3
V5 (2,1)
4 1 4 8
4 2 2 6
7
9
(-4,2) V2 (0,+∞) V1 4 4
(3,2) V4 4
(4,2) V6
(1,8)
V3
V5 (3,2)
4 1 4 8
4 2 2 6
7
9
(5,2) V2 (0,+∞) V1 2 4 4 V4 6
(5,2) V6
2
(1,6)
V3
V5 (3,2)
4 1 4 8
4 2 2 6
7
9
V2 (0,+∞) V1 4 4
4
V4
6 V6 2
2 2
(1,4)
V3
V5
存储结构
const maxn=100; type nodetype=record{可改进路顶点类型 可改进路顶点类型} 可改进路顶点类型 l,p:integer;{标号、检查标志 标号、 标号 检查标志} end; arctype=record{网顶点类型 网顶点类型} 网顶点类型 c,f:integer;{容量、流量 容量、 容量 流量} end; gtype=array[0..maxn,0..maxn] of arctype; ltype=array[0..maxn] of nodetype; var lt:ltype; g:gtype; n,s,t:integer;{顶点数、源点、汇点 顶点数、 顶点数 源点、汇点} f:text;
增广后的F

运筹学课件：网络最大流的基本概念(1)

运筹学课件：网络最大流的基本概念(1)

第八讲
第十一章 网络计划
Operation Research
概述
第八讲
网络计划方法是一种项目管理技术，合理安排项目的时间 进度，以及人力、物力、财力等资源。
美国是网络计划技术的发源地，并广泛应用。
20世纪50年代末，钱学森将将网络计划技术引入我国，并 在航天领域应用。
华罗庚在我国的网络计划方法推广普及等方面做出杰出贡 献。
Operation Research
网络计划图（1）
第八讲
基本概念
工作（作业、工序）
在项目中，消耗时间和资源的行动。用有方向的箭头表示
工作名称或代号 持续时间或消耗资源
事件（时间节点、Milestone)
标志工作（作业、工序）的开始或结束的点，本身不消耗资源。用圈 或正方形表示，使工作两端的连接点。
网络计划图（4）
（5）网路计划图中不能有回路出现
第八讲
（6）网络计划图中，仅有一个起点（代表项目开始），仅有一个终点（代 表项目结束）
（7）网络计划图中尽量避免出现交叉线
Operation Research
实例1
第八讲
Operation Research
第八讲
实例2
新产品项目，需要完成的工作和先后关系，各项工作需要的时间汇总在 下表中，编制网络计划图。
对于工作（i，j）有
tESi, jtEi tLFi, jtLj
Operation Research
第八讲
网络计划图的时间参数计算（6）
时差（工作的机动时间）
工作的总时差
工作的单时差
Operation Research
第八讲
网络计划图的时间参数计算（7）
讨论

网络最大流问题

网络最大流问题

第七章Operational厂§ 4网络最大流问题网络最大流冋题是网络的另一个基本冋题。

许多系统包含了流量问题。

例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。

许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。

4.1基本概念与定理1. 1.网络与流定义14 （1）网络：例1如图7-20是连结某产品产地’和销地一的交通图。

弧:1 表示从二到匚的运输线，弧旁的数字表示这条运输线的最大通过能力，.，括号内的数字表示该弧上的实际流一［。

现要求制定一个运输方案，使从一运到尸，的产品数量最多。

可行流与最大流输网络的实际问题中，我们可以看出，对于流有两个基本要求：一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力(即该弧的容量)二是起点发出的流的总和(称为流量)，必须等于终点接收的流的总和，且各中间点流 入的流量之和必须等于从该点流出的流量之和， 即流入的流量之和与流出的流量之和的差为 零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。

因此有下面所谓的可行流的定义。

定义14对于给定的网络 D=(V,A,C )和给定的流 』」：.「，若「满足下 列条件:(1)容量限制条件：对每一条弧 .-，有- -(7.9)(2)平衡条件： 对于中间点：流出量=流入量，即对于每一个对于出发带点T ：，有SA -'K/)对于收点①，有 工二 'I(7.12)则称/ - ■为一个可行流，•-称为这个可行流的 流量。

注意，我们这里所说的出发点 r 是指只有从匚发出去的弧，而没有指向J 的弧;收点二是指只有弧指向--，而没有从它的发出去的弧。

在运i (i 丰 s,t)，有(7.10)(7.11)可行流总是存在的。

例如令所有弧上的流，就得到一个可行流，（称为零流）,其流量 ': 一。

如图7-20中，每条弧上括号内的数字给出的就是一个可行流 3 - f/yJ ，它显然满足定义中的条件（1 ）和（2）。

6-3网络最大流

6-3网络最大流
v2 4,1 1,0
流量
3,1
vs 5,2 1,0 v1
v4
5,2
3,1 2,1 v3 vt
2,2
• 可行流
– 可行流满足：
可行流的流量
1)容量限制条件 : 对（vi , v j ) A 0 f ij cij 2)平衡条件 :
流入量=流出量
对vi , i s, t有 : 对v s 有 : 对vt 有 :
பைடு நூலகம்vs
5
vt
给一个有向图G＝(V,A)指定两个点，一 个点称为发点，记为vs，另一个点称为收点， 记为vt，其余点称为中间点。
容量
对于G中的每一个弧(vi,vj)，相应地给 一个数cij（cij≥0），称为弧(vi,vj)的 容量（表示这条弧的最大通行能力） 通过弧的某种流的实际流量，简记 为fij
调整流量，f=1。继续求出网络的不饱 和边
2 u=8 x=1 x=0 x=0
u=6
x=0 u=2 u=4 4
5
u=9 x=0 x=0 7 u=7 x=0
f=1
1
u=3 x=1
f=1
u=7 3
x=0
u=4
x=1
u=3
u=1
x=0 6
x=1
u=8
求出一条从1到7的不饱和链
2 u=8 f=1 1 u=7 =7 3 x=1 u=3 x=0 u=2 x=0 x=1 =1 x=0 u=4 u=6 =6 x=0 u=4 x=0 5 u=9 =9 x=0 7 u=8 6 f=1
u=1
x=0 6
x=1
u=8
=min {7,5,8}=5, 调整流量 xij’=xij+5, f’=f+5=2+5=7

网络最大流问题

网络最大流问题

1、网络与流设一个赋权有向图D=（V, A ）,在V 中指定一个发点v s 和一个收点v t (本题中，1V 和7V 分别是发点和收点)其它的点叫做中间点。

对于D 中的每一个弧（v i , v j ）∈A ,（i ，j {1，2，3，4，5，6，7}） 都有一个非负数c ij ,叫做弧的容量。

我们把这样的图D 叫做一个容量网络， 简称网络，记做D =（V ，A ，C ）。

弧的容量：是对网络上的每条弧(v i ,v j )都给出一个最大的通过能力，记为c (v i ,v j )或简写为c ij 。

2．流：加在网络各条弧上的一组负载量f(v i ,v j )：加在弧(v i ,v j )上的负载量，简记为f ij ，为非负数网络上的流：是指定义在弧集合上的一个函数f={f(v i ,v j )},其中f(v i ,v j )称为弧（v i ,v j )上的流量，流也可看作一个双下标变量。

3.弧的流量f(v i ,v j )：表示弧(v i ,v j )上每单位时间内的实际通过能力 弧的容量c(v i ,v j )：表示弧（v i ,v j )上每单位时间内的最大通过能力 对于实际的网络系统上的流，有几个显著的特点：(1)发点的净流出量和收点的净流入量必相等。

(2)每一个中间点的流入量与流出量的代数和等于零。

(3)每一个弧上的流量不能超过它的最大通过能力（即容量）.4.可行流与最大流称满足下列条件的流为可行流：（1）容量限制条件：对于每一个弧（v i ,v j ）∈A ，有 0≤f(v i ,v j ) ≤c(v i ,v j ) （简记为0≤ f ij ≤ c ij ）（2）平衡条件1，对出发点1V 有，()11j j f f V f -=∑∑2.对于收点7V 有， ()77j j f f V f -=-∑∑式子中V(f)称为可行流f 的流量,即发点的净输出量（或收点的净输入量）。

3.对于中间点: 流入量=流出量。

网络最大流问题

网络最大流问题

给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。

对于A中的每一条弧，对应一个数（简记），称之为弧的容量。

通常我们把这样的D叫做网络，记为D=(V,A,C)。

（2）网络流：在弧集A上定义一个非负函数。

是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。

§4 网络最大流问题网络最大流问题是网络的另一个基本问题。

许多系统包含了流量问题。

例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。

许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。

4.1 基本概念与定理1．1．网络与流定义14 （1）网络：例1如图7-20是连结某产品产地和销地的交通图。

弧表示从到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。

现要求制定一个运输方案，使从运到的产品数量最多。

可行流与最大流在运输网络的实际问题中，我们可以看出，对于流有两个基本要求：一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）；二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。

因此有下面所谓的可行流的定义。

定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件：（1）容量限制条件：对每一条弧，有(7.9)（2）平衡条件：对于中间点：流出量=流入量，即对于每一个i (i≠s,t)，有(7.10)对于出发带点，有(7.11)对于收点，有(7.12)则称为一个可行流，称为这个可行流的流量。

注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧；收点是指只有弧指向，而没有从它的发出去的弧。

网路的最大流和最小截

网路的最大流和最小截
5
最大流最小截集的标号法举例
(1 4 1 , 4 )
1
(16,15)
(6, 6)
(5, 5
(7,5)
(s+,)
s
(9
(1
(15,9)
(s+,6)
(3,1 )
2 (12,10)
)
,1 3 (1
6 2)
(22
,22
)
5
3) (6,
t (4+,1)
(1 0 1 , 9 )
,9)
4 1 , 4 )
3
(2,6)
• 若在当前可行流下找不到增广链，则已得到最大流
• 增广链中与 s 到 t 方向一致的弧称为前向弧，反之后向弧
s (5,1) (1,1) (1,1) (3,0) (5,3)
c ij f ij 前向弧 增广量 q = min qij q ij f ij 后向弧 = min (4,1,1,3,2)= 1 (5,2) (1,0) (1,0) (3,1) (5,4) s 2 3 4 5 t
(1) (i, j)是前向弧且饱和，则节点 j 不标号； (2) (i, j)是前向弧且未饱和，则节点 j 标号为[i+,q(j)]，表示从节点 i 正 向流出，可增广 q(j)=min[q(i), cijfij] ；
(3) (j, i)是后向弧，若 fji=0，则节点 j 不标号；
(4) (j, i)是后向弧，若 fji>0，则节点 j 标号为[i,q(j)]，表示从节点 j 流 向 i，可增广 q(j)=min[q(i), fji] ；
(3,0) s (5,0)
2
(4,0) (1,0) (2,0)
4

网络系统的最小费用最大流问题

网络系统的最小费用最大流问题
净输入量）
网络系统的最大流问题
• 任意一个网络上的可行流总是存在的。例如零流v(f )=0,
就是满足以上条件的可行流。 • 网络系统中最大流问题就是在给定的网络上寻求一个可行
流f ,使其流量v(f )达到最大值。 • 设流f={fij}是网络D上的一个可行流，我们把D中fij=cij的
弧叫做饱和弧，fij<cij的弧叫做非饱和弧，fij>0的弧为非 零流弧，fij=0的弧叫做零流弧。
查点。(考虑后向弧)
于是vi成为标号已检查的点。重复以上步骤，如果所有的标
号都已经检查过，而标号过程无法进行下去，则标号法结束。这时
的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广 链μ，转入下一步调整过程。
网络系统的最大流问题
2. 调整过程
首先按照vt和其他点的第一个标号，利用“反向追踪” 的办法，找出增广链 。例如，令vt的第一个标号是vk，则 弧（vk,vt）在μ上。再看vk的第一个标号，若是vi，则弧 (vi,vk)都在μ上。依次类推，直到vs为止。这时，所找出 的弧就成为网络D的一条增广链μ。取调整量θ= l(vt),即 vt的第二个标号，
未检查点vi，对一切未标号点vj：
网络系统的最大流问题
1) 如 果 在 弧 （ vi ,vj ） 上 ， fij<cij , 那 么 给 vj 标 号 （vi ,l(vj)），其中l(vj)=min[l(vi),cij -fij].这时，vj 成
为标号未检查的点。(考虑前向弧)
2) 如 果 在 弧 （ vj ,vi ） 上 ， fji>0, 那 么 给 vj 标 号 （ -vi , l(vj)）,其中l(vj)=min[l(vi),fji].这时，vj成为标号未检

Chap.6-网络最大流解析

Chap.6-网络最大流解析
16
11

饱和弧:(s,v1),(v2,v4),(v3,t); 其他的弧都是非饱和弧; (v3,v2)是零流弧.
v1
8(8)
9(4)
v3
cij ( fij )
5(5) 2(0) 5(4) 6(1)
s
7(5)
t
10(8)
v2
9(9)
v4
如图，在链（s,v1,v2,v3,v4,t)中， μ+={(s,v1),(v1,v2),(v4,t)}, μ-={(v3, v2),(v4,v3)}.
s
7(5)
2(0) 5(4)
6(1)
t
10(8)
v2
9(9)
v4
如图，链μ=（s,v2,v1,v3,v4,t）就是一条增广链。
14
当有增广链存在时,令
ci fi , min , fi
再令
for for

fi , for f f i , for f , other i
Cij
5 6 10
t
每条弧旁边的权就是对应的容量(最大通过能力)。 要求指定一个产品运输方案，使得从s→t的货运量最大， 这是寻求网络系统的最大流问题,即从发点s到收点t允 2 许通过的最大流量。
§5 网络的最大流
二 基本概念 定义 设一个加权有向图D(V,A),在V中指定一 个发点 s 和一个收点 t, 其他的点叫做中间点。 对于 D 中的弧 (vi,vj)∈A, 都有一个权 cij 叫做 弧的容量。这样的图 D 称做一个网络系统，简 称网络，记做 D(V，A，C)。
§5 网络的最大流

一 引言 在许多实际的网络系统中都存在着流量和最大 流问题。例如铁路运输系统中的车辆流，城市 给排水系统的水流问题等等。而网络系统的最 大流问题是图与网络流理论中的最优化问题， 它对于解决生产实际问题起着十分重要的作用。

《网络最大流问题》PPT课件

《网络最大流问题》PPT课件
《网络最大流问题》PPT课件
本课件仅供大家学习学习 学习完毕请自觉删除
谢谢 本课件仅供大家学习学习
学习完毕请自觉删除 谢谢
第六章 图与网络分析
第一节 图的基本知识 第二节 树 第三节 最短路问题 第四节 网络最大流问题 第五节 最小费用最大流问题
第四节 网络最大流问题
图10-23是联结某产品产地v1和销地v6的交通网，每一
给vt标号为(v4, l(vt))，这里 l(vt)＝min[l(v4), (c4t- f4t)]=min[1, 2]=1
因vt有了标号，故转入调整过程。
(3,3) (0,+∞) vs
(5,1)
v2 (-v1,1) (4,3) v4 (v2,1) (5,3)
(1,1) (1,1) (3,0)
vt (v4,1)
(3,3)
(5,3)
(0,+∞) vs (5,1)
(1,1) (1,1)
(3,0) vt (2,1)
v1 (vs,4) (2,2) v3
(4) 检查v2。
在弧(v2，v4)上，f21=3， c24=4，f24< c24，则给
v4标号(v2, l(v4)) 。
l(v4) = min[l(v2), (c24- f24)]=min[1, 1]=1 在 弧 (v3 ， v2) 上 ， f32=1>0 ， 给 v3 标 号 ： (-v2,
便不存在路。所以，截集是从vs到的vt必经之路。
定义5 给一截集(V1, V)__，1 把截集(V1, )中V__1 所有弧的 容量之和称为这个截集的容量(简称为截量)，记为
c(V1, )，即V__1
cV1,V1
cij
(vi,vj)(V 1,V1)

6-maximum flow网络最大流

6-maximum flow网络最大流

10
Ford-Fulkerson ( G, s, t )
for each edge (u, v) ∈ E (G ) do f (u , v) ← 0 f (v, u ) ← 0 while there exists an augmenting path p in residual network G f do c f ( p ) = min {c f (u , v) : (u , v) is on p} for each edge (u, v) is in p do f (u , v) ← f (u, v) + c f ( p ) f (v, u ) ← − f (u , v)
13
• Capacity constraint:
(f
• Flow conservation: for all u ∈V − {s, t},
∑ ( f + f ′ ) (u, v )
v∈V
= =
∑ f (u, v ) + ∑ f ′(u, v )
v∈V v∈V
0 + 0= 0
• Finally, f + f′ = = =
v∈V v∈V
f ( u, V ) )
• The value of a flow is f = f ( s, V ) − f (V , s ) . • Note: when (u, v ) ∉ E , f (u, v ) = 0.
7
Some of these properties do not hold any more (when using the second definition of flows)
15
Cuts
• A cut ( S , T ) of a flow network G = (V , E ) is a partition of of V into S and T = V − S such that s ∈ S and t ∈ T . • If f is a flow, f ( S , T ) denotes the net flow across the cut ( S , T ). • The capacity of ( S , T ) is c( S , T ) = ∑∑ c(u, v ).

6.4 网络的最大流

6.4 网络的最大流

运 筹 帷 幄 之中
决胜千里之外
链：从发点到收点的一条路线（弧的方向不一定都同向） 称为链。从发点到收点的方向规定为链的方向。
前向弧：与链的方向相同的弧称为前向弧。
后向弧：与链的方向相反的弧称为后向弧。
增广链: 设 f 是一个可行流，如果存在一条从vs到vt的链，满足：
1.所有前向弧上fij<Cij 2.所有后向弧上fij>0
截集中，称截量最小的为最小截集。 从直观上说，截集的所有弧是 vs 到 vt 的必经之路，若把去掉截
集中的从网络中去掉，则从 vs 到 vt 就不存在路了。
12
截集和截量
运 筹 帷 幄 之中
决胜千里之外
v1 (3,3)
(4,3)
v3 (5,3)
vs
(2,1)
(1,1)
(1,0)
vt
、
(5,1)
v2
vm
vm
(3) v fsj fit
vs
vt
所有中间点vm
发点vs流出的总流量等于流入收点vt的总流量
9
增广链的概念
运 筹 帷 容量的弧。 非饱和弧：fij<cij，流量小于容量的弧。 零流弧：fij=0，流量等于零的弧。 非零流弧：fij＞0，流量大于零的弧。
V3 (V1, 1)
2
5(5)
4(2)
V4
6(6)
4(2)
V5
(V2, 1) Vt
旅游车数量配置问题
运 筹 帷 幄 之中
决胜千里之外
V1
3(3)
V2 (V3, 1)
Vs (△, +∞)
5(4)
1(1) 4(34)
9(78) 1(1)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
③如果某未标号点 k有两个以上相邻的标号 点, 为了减少迭代次数 , 可按①和②中所述规则 分 别计算出 ( k )的值, 并取其中最大的一个标 记.
运筹学

3) 重复第二步 , 可能出现两种结局:
①标号过程中断 , t得不到标号 , 说明该网络中 不存在增广链 , 给定流量即为最大流 .记已标号 点的集合为V , 未标号点集为 V , (V ,V )为网络的 最小割; ②t得到标号, 这时可用反向追踪法在 网络中找 出一条从s t的由标号点及相应的弧 连接而成 的增广链.
4 5 6
1(0) (4,1) 1(1)
s
2 3
t
运筹学
1(0) (s,1)
(2,1) 1(0)
增广链
任意给一个可行流，用标号算法求出网络的最大流
1
1(1) (s,1) (0,∞) 1(0) 1(0) 1(1) 1(0) 1(0) 1(1) 1(0) (2,1)
4 5 6
1(1) (6,1) 1(1)
j j
运筹学
网络的最大流：满足容量限制条件和中间 点平衡的条件下，使v(f)值达到最大。
max v ( f ) ）对所有弧有： 1 0 f ( v , v ) c( v , v ) i j i j s.t. 2）对中间点vi , i s, t有 : f (v , v ) f (v , v ) 0 i j j i
运筹学

增广链 当有增广链存在时，找出
可增加流量的链
( ci f i ), 对 min 0 对 fi , f i , 对所有 再令 f f i - , 对所有 f , 对非增广链上的弧 i
s
f2>0 f1<c1 f3>0
( v j ) min{ ( vi ), cij f ij }
②对( v j , vi ) 后向弧, 若f ji 0, 不给点v j标号; 若f ji 0, 给v j标号( vi , ( v j )),其中 :
( v j ) min{ ( vi ), f ji }
t
运筹学
v2
K
9(9)
图中弧旁数字cij(fij) 图6-13
v4
找出全部不同的割：
v1
8(8)
K
9(4)
v3
5(5) 6(1) 10(8)
s
7(5)
5(4)
2(0)
t
V
s s,1 s,2 s,1,2 s,1,3 s,2,4 s,1,2,3 s,1,2,4
V
1,2,3,4,t 2,3,4,t 1,3,4,t 3,4,t 2,4,t 1,3,t 4,t 3,t
v4
图6-13
运筹学
s,1,2,3,4
t
(3,t)(4,t)
15
几点结论
1）从s→t的流量实际上等于通过割的从V 到V 的流量减去V →V的流量，即
v( f ) f (V ,V ) f (V ,V )
2）若用v*(f)表示网络中从s→t的最大流， 用c*(V， V )表示网络中最小割的容量，则有
1)容量限制条件 : 对( vi , v j ) A 0 f ( vi , v j ) c( vi , v j ) 2)中间点平衡条件 :
流入量=流出量
对vi , i s, t有 : f ( vi , v j ) f ( v j , vi ) 0 以v ( f )表示网络中从s t的流量，则有 v ( f ) f ( vs , v j ) f ( v j , vt )
运筹学
4.2-4.3 割和流量
割的定义: 将容量网络中的发点和收点分割成两 个集合V和V ,并使s到t的流中断的一组弧的集合 ,记为割（V，） V . 割的容量是组成它的集合中的各弧的容量之和, 用c(V,V )表示。
v1
K
9(4)
v3
8(8)
s
7(5)
5(4)
5(5) 2(0) 6(1) 10(8)
*
s
t
图6-13
运筹学
7(6)
v (s,1) 2
*
v4
v ( f ) c (V ,V ) 14
4-5 应用举例
例7 某河流中有4个岛屿,从两岸至各岛屿及各岛屿之间的桥梁 编号如图所示.在一次敌对的军事行动中,问至少应炸断哪几 座桥梁,才能完全切断两岸的交通联系？ A 1 B 2 4 D 10 11 5 C 8 6
s
2 3
t
1(1)
(2,1) 1(0)
增广链
1
1(1) (s,1) (0,∞) 1(1)
1(0) 1(1) 1(0) 1(1) 1(1) 1(0)
4
(2,1)
1(1) (6,1) 1(1)
s
2 3
5 6
t
运筹学
1(1)
(2,1) 1(1)
运筹学

4) 修改流量 : 设图中原有可行流为 f ,令
f (t ), 对增广链上所有前向弧 f f - (t ), 对增广链上所有后向弧 f, 所有非增广链上的弧 这样又得到网络上的一 个新的可行流 f ;


, 重复第一到第四步 , 直到图中 5) 抹掉图上所有标号 找不到任何增广链 ,即出现第三步的结局 (1)为止, 这时网络中的流量即为 最大流.
f4<c4 f5<c5
t
运筹学
s→t的流量v(f)增大了一个θ值
几点结论
1) v ( f ) c(V ,V ) 2) 可行流f *是最大流 不存在关于f *的增广链 3) 最大流最小割定理 : 最大流量 最小割容量 v ( f ) c (V ,V )
* *
运筹学
4.4 求网络最大流的标号法
割 (s,1)(s,2) (s,2)(1,2)(1,3) (s,1)(2,4) (1,3)(2,4) (s,2)(1,2)(3,2)(3,t) (s,1)(4,3)(4,t) (2,4)(3,t) (1,3)(4,3)(4,t)
v 2 割的容量
15 21 17 18 19 24 14 25
K
9(9)
运筹学
例6 用标号算法求下图中s→t的最大流量,并找出
该网络的最小割。
v1
8(8)
9(4) 5(4)
v3
5(5) 6(1) 10(8)
s
7(5)
2(0)
t
图6-13
运筹学
v2
9(9)
v4
例 6 (续 ) 。
(v2,1)
v1
(v1,1)
9(5) 5(3)
v3
8(8)
(0,+∞)
5(5) 2(0) 6(0) 10(9) 9(9)
v ( f ) c (V ,V )
* *
运筹学
增广链:
对可行流
f { fi } f i ci 饱和弧；f i ci 非饱和弧
f i 0 零流弧；f i 0 非零流弧 网络中的一条链
(vs ,..., vt )
弧的方向与链的方向一致 - -前向弧 - -其全体记为 对f i , 存在f i ci ; 弧的方向与链的方向相反 - -后向弧 - -其全体记为 对f i , 存在f i 0;
§4 网络的最大流
4.1网络最大流的有关概念 定义: 对有向图D=(V,A): vs --发点 vt -- 收点 其余 -- 中间点 c(vi,vj) -- 弧(vi,vj)的容量, 最大通过能 力，简写为cij D=(V,A,C) -- 网络 fij -- 弧(vi,vj)上的流量
运筹学
流与可行流 可行流满足:
3(1) 增广链
B
(A,1) 1(1)
2(1)
(B,1)
D
1(1)
A
2(1)
1(1) K
C
1(0)
F
1(1) K
最小割为{(D,F), (A,E), (D,E)}, 应至少炸断编号 为7、9、10的三座桥。
运筹学
E
3(2)
4-5 应用举例
例8 匹配问题. 有三根相同的轴(编号为1、2、3),又有三个相同 的齿轮(编号为4、5、6),由于精度不高,不能做到任意互配.根 据图纸工艺要求,已知轴1能和齿轮4、5配合,轴2能和齿轮5 、6配合,轴3能和齿轮4、5配合.要求合理选择装配方案,以得 到轴与齿轮的最大匹配数.
1 2 3
4 5 6
运筹学
增加一个假想发点与假想收点,问题转化为求该网络上的最大流.
1
1 1 1
4 5 6
1 1 1
s
1 1
2
1
1 1
t
3
1
任意给一个可行流，用标号算法求出网络的最大流
1
1(1) (s,1) (0,∞) 1(0) 1(0) 1(1) 1(0) 1(0) 1(0) 1(0) (2,1) (3,1)
7
3
9
E 12
13
运筹学
F
例7等价于求网络中的最小割,弧旁数字相当于容量
B
2
2
D
2
A
1
1
C
1
1
F
3
E
运筹学
任意给一个可行流，用标号算法求出网络的最大流
(A,1) 2(1) (0,∞)
B
(A,1) 1(1)
2(1)
(B,1)
D
1(1)
A
2(1)
1(1)
C
(A,1)
1(0)
F
(E,1)