《大流标号法》PPT课件.ppt
《《大流标号法》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《大流标号法》PPT课件.ppt(29页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、最大流问题 给定一个有向图G(V,E),其中仅有一个点的入次为零称为发点(源),记为vs,仅有一个点的出次为零称为收点(汇),记为vt,其余点称为中间点。基本概念基本概念3511 42352vsv2v1v3v4vt 对于G中的每一个弧(vi,vj),相应地给一个数cij(cij0),称为弧(vi,vj)的容量。我们把这样的D称为网络(或容量网络),记为G(V,E,C)。所谓网络上的流,是指定义在弧集E上的函数ff(vi,vj),并称f(vi,vj)为弧(vi,vj)上的流量,简记为fij。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt标示方式:每条边上标示两个
2、数字,第一个是容量,第二是流量可行流、可行流的流量、最大流。可行流是指满足如下条件的流:(1)容量限制条件:对G中每条边(vi,vj),有(2)平衡条件:对中间点,有:(即中间点vi的物资输入量等于输出量)对收点vt与发点vs,有:(即vs发出的物资总量等于vt接收的物资总量),W是网络的总流量。可行流总是存在的,例如f=0就是一个流量为0的可行流。所谓最大流问题就是在容量网络中寻找流量最大的可行流。一个流f=fij,当fij=cij,则称f对边(vi,vj)是饱和的,否则称f对边(vi,vj)不饱和。最大流问题实际上是一个线性规划问题。但利用它与图的密切关系,可以利用图直观简便地求解。给定容
3、量网络G(V,A,E),若点集V被剖分为两个非空集合V1和V2,使 vsV1,vtV2,则把弧集(V1,V2)称为(分离vs和vt的)割割集集。显然,若把某一割集的弧从网络中去掉,则从vs到vt便不存在路。所以,直观上说,割集是从vs到vt的必经之路。3511 42352vsv2v1v3v4vt注:有向边也称为弧。对教材P259定义21的解释vsv1v4v3vtv2边集(vs,v1),(v1,v3),(v2,v3),(v3,vt),(v4,vt)是G的割集。其顶点分别属于两个互补不相交的点集。去掉这五条边,则图不连通,去掉这五条边中的任意1-4条,图仍然连通。割集的容量(简称割量)最小割集割集
4、(V1,V2)中所有起点在V1,终点在V2的边的容量的和称为割集容量。例如下图中所示割集的容量为53511 42352vsv2v1v3v4vt在容量网络的所有割集中,割集容量最小的割集称为最小割集(最小割)。对于可行流ffij,我们把网络中使fijcij的弧称为饱和弧,使fij0的弧称为非零流弧。设f是一个可行流,是从vs到vt的一条链,若满足前向弧都是非饱和弧,后向弧都是都是非零流弧,则称是(可行流f的)一条增广链。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt 若是联结发点vs和收点vt的一条链,我们规定链的方向是从vs到vt,则链上的弧被分成两类:前向弧
5、、后向弧。对最大流问题有下列定理:定理定理1 1 容量网络中任一可行流的流量容量网络中任一可行流的流量不超过其任一割集的容量。不超过其任一割集的容量。定理定理2 2(最大流(最大流-最小割定理最小割定理)任一容任一容量网络中量网络中,最大流的流量等于最小,最大流的流量等于最小割割集集的割量。的割量。推论推论1 可行流可行流f*fij*是最大流,是最大流,当且当且仅当仅当G中不存在关于中不存在关于f*的增广链。的增广链。求最大流的标号法求最大流的标号法 标号法思想是:标号法思想是:先找一个可行流。先找一个可行流。对于一个可行流,经过对于一个可行流,经过标号过程标号过程得到得到从发点从发点vs到收
6、点到收点vt的增广链;经过的增广链;经过调整调整过程过程沿增广链增加可行流的流量,得沿增广链增加可行流的流量,得新的可行流。重复这一过程,直到可新的可行流。重复这一过程,直到可行流无增广链,得到最大流。行流无增广链,得到最大流。标号过程:(1)给vs标号(-,+),vs成为已标号未检查的点,其余都是未标号点。(2)取一个已标号未检查的点vi,对一切未标号点vj:若有非饱和弧(vi,vj),则vj标号(vi,l(vj),其中l(vj)minl(vi),cij fij,vj成为已标号未检查的点;若有非零弧(vj,vi),则vj标号(-vi,l(vj),其中l(vj)minl(vi),fji,vj成
7、为已标号未检查的点。vi成为已标号已检查的点。(3)重复步骤(2),直到vt成为标号点或所有标号点都检查过。若vt成为标号点,表明得到一条vs到vt的增广链,转入调整过程;若所有标号点都检查过,表明这时的可行流就是最大流,算法结束。调整过程:在增广链上,前向弧流量增加l(vt),后向弧流量减少l(vt)。下面用实例说明具体的操作方法:例(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt在图中给出的可行在图中给出的可行流
8、的基础上,求流的基础上,求vs到到vt的最大流。的最大流。(-,+)(vs,4)(-v1,1)(-v2,1)(v2,1)(v3,1)(3,3)(5,2)(1,0)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)vsv2v1v3v4vt(vs,3)(-,+)得增广链,标号结束,得增广链,标号结束,进入调整过程进入调整过程 无增广链,标号结束,得无增广链,标号结束,得最大流。同时得最小截。最大流。同时得最小截。下图中已经标示出了一个可行流,求最大流-,vs,3vs,4v2,4-v4,2vsv1v2v3v4v5vs(4,0)(5,2)(1,0)(4,0)(1,0)(2,2)(3,2)(4
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大流标号法 标号 PPT 课件
限制150内