- 1、本文档共35页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
最大流在信息学竞赛中应用的一个模型江涛.
最大流在信息学竞赛中应用的一个模型
江 涛
关键字:
网络 可行流 最大流 附加网络
无源汇 必要弧 流的分离 有上下界的最大流 建模
引言:
最大流类的模型在当今信息学比赛中有相当广泛的应用。但在教学中,发现很多同学对流模型的原理和变形并不掌握,只是记下经典的算法和题目,以便比赛中套用。
这当然有很大的局限性,也不是学习之正道。本讲想通过对最大流模型,特别是附加网络的一些分析、讨论,达到抛砖引玉目的。
一、网络与流的概念
一个实例:运输网络
图1.1
网络定义:
一个有向图 G=(V,E);
有两个特别的点:源点s、汇点t;
图中每条边(u,v)∈E,有一个非负值的容量C(u,v)
记为 G=(V,E,C)
网络三要素:点、边、容量
可行流定义:
是网络G上的一个“流”,即每条边上有个“流量”P(u,v),要满足下面两个条件:
流的容量限制---弧: 对任意弧(u,v)---有向边
流的平衡---点:
除源点和汇点,对任意中间点有:流入u的“流量”与流出u的“流量”相等。即:
有
网络的流量:源点的净流出“流量” 或 汇点的净流入“流量”。即:
注意,我们这里说的流量是一种速率,而不是指总量。联系上面所说的实例,下面是一个流量为1的可行流:
图1.2
标准图示法:
图1.3
例1.1 有一个n*m的国际棋盘,上面有一些格子被挖掉,即不能放棋子,现求最多能放多少个棋子“车”,并保证它们不互相攻击(即:不在同一行,也不在同一列)?
分析:
行、列限制---最多只能一个车控制;
车对行、列的影响---一个车控制一个行和边;
例子:
图1.4
图1.5
显然,我们要求车最多,也就是求流量最大---最大流问题。下面是一个解:
图1.6
即(1,3)、(2,1)、(3,2)格上各放一个车,可得到一个最优方案。
二、最大流问题
寻找网络G上可能的最大流量(和一个有最大流量的可行流方案),即为网络G上的最大流问题。
我们再来看看图1.1的运输网络例子,我们可能通过改进图1.3得到下面这样的可行流:
图2.1
求解过程中的困惑:
[问题2.1]流量还可能增加吗?
[问题2.2]如果能增加,怎样改进?
三、最大流算法的核心---增广路径
退流的概念---后向弧
仔细分析图2.1,我们发现,流量是可以增加的:
图3.1
把一个流量弧(B,C)和(C,T)上的流退回到B点,改道从B-D-E-T走,就可以增加流量了,如下图:
图3.2
图3.1不能“直接寻找增大流的路径”,是因为当初有些弧上的流选择不“恰当”,要“退流”。
一种直观的想法就是:调整或重新有哪些信誉好的足球投注网站“当初的选择”---难!
能不能保留以前的工作,而在这之上改进呢?经过专家们研究发现,加入退流思想---后向弧,就能再次“直接寻找增大流的路径”。
增广路径(可改进路径)的定义
若P是网络中连结源点s和汇点t的一条路,我们定义路的方向是从s到t,则路上的弧有两种:
前向弧---弧的方向与路的方向一致。前向弧的全体记为P+;
后向弧---弧的方向与路的方向相反。后向弧的全体记为P-;
设F是一个可行流,P 是从s到t的一条路,若P满足下列条件:
在P+的所有前向弧(u,v)上,0≦f(u,v) C(u,v);
在P-的所有后向弧(u,v)上,0f(u,v) ≦C(u,v);
则称P是关于可行流F的一条可增广路径。
图3.3
本图中:S-A-C-B-D-E-T 为一增广路径。其中(C,B)为后向弧,其它为前向弧。
在增广路径上的改进算法:
求路径可改进量;
修改增广路径上的流量;
四、附加网络1---残留网络
由于要考虑前向弧、后向弧,分析、描述时不简洁,在图2.1上直观看也不容易看出增广路径。
因此我们把已经有的流量从容量中分离出来表示,引入一个与原问题等价的附加网络1:残留网络。
图4.1
其中,前向弧(黑色)上的容量为“剩余容量”=C(u,v)-f(u,v);后向弧(红色)上的容量为“可退流量”=f(v,u)。
改造后的网如下:
图4.2
在这张图上,我们找增广路径显的非常直观了!
结合增广路径,我们有如下定理:
最大流定理
如果残留网络上找不到增广路径,则当前流为最大流;反之,如果当前流不为最大流,则一定有增广路径。
证明涉及最小割概念,不是本文重点,由于时间关系,从略。
您可能关注的文档
- 最优二叉树哈夫曼树..doc
- 最优套期保值比率确定模型研究..doc
- 曾良《略论古籍整理中的文字处理问题》..doc
- 曼昆经济学原理微观经济学英文版习题答案..docx
- 曼昆宏观经济学习题答案..doc
- 最低工资制度对劳动力市场的影响..doc
- 曼昆《经济学原理》第五版微观经济学习题答案(英文)..doc
- 最低工资标准下的福建鞋业-现场调查与案例跟踪..doc
- 最低工资制度对浙江中小企业的影响..doc
- 最佳商业模式设计创新与转型(金超)..doc
- 2024至2030年中国推土机行业市场需求与投资规划分析报告.docx
- 2024至2030年中国过氧化镁行业发展预测及投资策略报告.docx
- 2024至2030年中国兽用化学药品行业深度调研与投资趋势分析报告.docx
- 2024至2030年中国新型农业机械行业深度调研与投资战略咨询报告.docx
- 2024至2030年中国酞菁颜料市场前景及投资发展战略研究报告.docx
- 废锡项目申请报告.docx
- 2024至2030年中国美沙酮中间体行业发展预测及投资策略报告.docx
- 2024至2030年中国软水、净水剂用聚合硫酸铁行业深度调研及发展预测报告.docx
- 2024至2030年中国轻质碳酸钙行业发展预测及投资策略报告.docx
- 2024至2030年中国余热发电市场.docx
文档评论(0)