1/22
文档分类:高等教育

运筹学-最大流问题.ppt


下载后只包含 1 个 PPT 格式的文档,里面的视频和音频不保证可以播放,查看文件列表

特别说明:文档预览什么样,下载就是什么样。

下载所得到的文件列表
运筹学-最大流问题.ppt
文档介绍:
最大流问题
运筹学-最大流问题
给定一个有向图G=(V,E),其中仅有一个点的入次为零称为发点(源),记为vs,仅有一个点的出次为零称为收点(汇),记为vt,其余点称为中间点。
基本概念
3
5
1
1
4
2
3
5
2
vs
v2
v1
v3
v4
vt
对于G中的每一条边(vi,vj),相应地给一个数cij(cij≥0),称为边(vi,vj)的容量。我们把这样的网络 G称为容量网络 ,记为G=(V,E,C)。
运筹学-最大流问题
网络上的流,是指定义在边集E上的函数f={f(vi,vj)},并称f(vi,vj)为边(vi,vj)上的流量,简记为fij。
3,1
5,2
1,0
1,0
4,1
2,2
3,1
5,2
2,1
vs
v2
v1
v3
v4
vt
标示方式:每条边上标示两个数字,第一个是容量,第二是流量
运筹学-最大流问题
可行流、可行流的流量、最大流。
可行流是指满足如下条件的流:
(1)容量限制条件:对G中每条边(vi,vj), 有
(2)平衡条件:
对中间点,有:
(即中间点vi的物资输入量等于输出量)
对收点vt与发点vs,有:
(即vs发出的物资总量等于vt接收的物资总量),W是网络的总流量。
运筹学-最大流问题
可行流总是存在的,例如f={0}就是一个流量为0的可行流。
所谓最大流问题就是在容量网络中寻找流量最大的可行流。
一个流f={fij},当fij=cij,则称f对边(vi, vj)是饱和的,否则称f对边(vi, vj)不饱和。对于不饱和的,其间隙为δij=cij-fij
最大流问题实际上是一个线性规划问题。
但利用它与图的密切关系,可以利用图直观简便地求解。
运筹学-最大流问题
给定容量网络G=(V,E,C),若点集V被剖分为两个非空集合V1和V2,使 vs∈V1 ,vt∈V2,则把边集(V1,V2)称为(分离vs和vt的)割集。
显然,若把某一割集的边从网络中去掉,则从vs到vt便不存在路。所以,直观上说,割集是从vs到vt的必经之路。
3
5
1
1
4
2
3
5
2
vs
v2
v1
v3
v4
vt
运筹学-最大流问题
vs
v1
v4
v3
vt
v2
边集(vs,v1),(v1,v3),(v2,v3),(v3,vt),(v4,vt)是G的割集。其顶点分别属于两个互补不相交的点集。去掉这五条边,则图不连通,去掉这五条边中的任意1-4条,图仍然连通。
运筹学-最大流问题
割集的容量(简称割量) 最小割集
割集(V1, V2)中所有起点在V1,终点在V2的边的容量的和称为割集容量。例如下图中所示割集的容量为5
3
5
1
1
4
2
3
5
2
vs
v2
v1
v3
v4
vt
在容量网络的所有割集中,割集容量最小的割集称为最小割集(最小割)。
运筹学-最大流问题
对于可行流f={fij},我们把网络中使fij=cij的边称为饱和边,使fij<cij的边称为非饱和边;把使fij=0的边称为零流边,使fij>0的边称为非零流边。
设f是一个可行流,μ是从vs到vt的一条链,若μ满足前向边都是非饱和边,后向边都是都是非零流边,则称μ是(可行流f的)一条可增广链。
3,1
5,2
1,0
1,0
4,1
2,2
3,1
5,2
2,1
vs
v2
v1
v3
v4
vt
若μ是联结发点vs和收点vt的一条链,我们规定链的方向是从vs到vt,则链上的边被分成两类:前向边、后向边。
运筹学-最大流问题
对最大流问题有下列定理:
定理1 容量网络中任一可行流的流量不超过其任一割集的容量。

定理2(最大流-最小割定理)任一容量网络中,最大流的流量等于最小割集的割量。
推论1 可行流f*={fij*}是最大流,当且仅当G中不存在关于f*的增广链。
运筹学-最大流问题
内容来自淘豆网www.taodocs.com转载请标明出处.